Equidepth partitioning of a data set based on finding its medians

Aditya P. Gurajada; Jaideep Srivastava

doi:10.1109/SOAC.1991.143854

Equidepth partitioning of a data set based on finding its medians

Aditya P. Gurajada
, Jaideep Srivastava

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

One of the techniques to estimate selectivities of query predicates is by generating equidepth partitions for a relation and maintaining equidepth histograms. This paper presents a new technique to generate equidepth partitions for a secondary memory resident relation using a linear median find algorithm. A variation of this technique, which involves sorting of the individual blocks, is also proposed and extended to generate arbitrary number of partitions. The proposed techniques are compared with an external sorting based partitioning approach. Finally, an overall strategy to select the partitioning algorithm with possibly dynamic allocation of buffers is proposed.

Original language	English (US)
Title of host publication	Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	92-101
Number of pages	10
ISBN (Electronic)	0818621362, 9780818621369
DOIs	https://doi.org/10.1109/SOAC.1991.143854
State	Published - 1991
Event	1991 Symposium on Applied Computing, SOAC 1991 - Kansas City, United States Duration: Apr 3 1991 → Apr 5 1991

Publication series

Name	Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

Conference

Conference	1991 Symposium on Applied Computing, SOAC 1991
Country/Territory	United States
City	Kansas City
Period	4/3/91 → 4/5/91

Bibliographical note

Publisher Copyright:
© 1991 IEEE.

Publisher link

10.1109/SOAC.1991.143854

Find It

Find It at U of M Libraries

Cite this

Gurajada, A. P., & Srivastava, J. (1991). Equidepth partitioning of a data set based on finding its medians. In Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991 (pp. 92-101). Article 143854 (Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SOAC.1991.143854

Equidepth partitioning of a data set based on finding its medians. / Gurajada, Aditya P.; Srivastava, Jaideep.
Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991. Institute of Electrical and Electronics Engineers Inc., 1991. p. 92-101 143854 (Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gurajada, AP & Srivastava, J 1991, Equidepth partitioning of a data set based on finding its medians. in Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991., 143854, Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991, Institute of Electrical and Electronics Engineers Inc., pp. 92-101, 1991 Symposium on Applied Computing, SOAC 1991, Kansas City, United States, 4/3/91. https://doi.org/10.1109/SOAC.1991.143854

@inproceedings{9cf778e6adc74e61b16a42061431acab,

title = "Equidepth partitioning of a data set based on finding its medians",

abstract = "One of the techniques to estimate selectivities of query predicates is by generating equidepth partitions for a relation and maintaining equidepth histograms. This paper presents a new technique to generate equidepth partitions for a secondary memory resident relation using a linear median find algorithm. A variation of this technique, which involves sorting of the individual blocks, is also proposed and extended to generate arbitrary number of partitions. The proposed techniques are compared with an external sorting based partitioning approach. Finally, an overall strategy to select the partitioning algorithm with possibly dynamic allocation of buffers is proposed.",

author = "Gurajada, \{Aditya P.\} and Jaideep Srivastava",

note = "Publisher Copyright: {\textcopyright} 1991 IEEE.; 1991 Symposium on Applied Computing, SOAC 1991 ; Conference date: 03-04-1991 Through 05-04-1991",

year = "1991",

doi = "10.1109/SOAC.1991.143854",

language = "English (US)",

series = "Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "92--101",

booktitle = "Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991",

}

TY - GEN

T1 - Equidepth partitioning of a data set based on finding its medians

AU - Gurajada, Aditya P.

AU - Srivastava, Jaideep

PY - 1991

Y1 - 1991

N2 - One of the techniques to estimate selectivities of query predicates is by generating equidepth partitions for a relation and maintaining equidepth histograms. This paper presents a new technique to generate equidepth partitions for a secondary memory resident relation using a linear median find algorithm. A variation of this technique, which involves sorting of the individual blocks, is also proposed and extended to generate arbitrary number of partitions. The proposed techniques are compared with an external sorting based partitioning approach. Finally, an overall strategy to select the partitioning algorithm with possibly dynamic allocation of buffers is proposed.

AB - One of the techniques to estimate selectivities of query predicates is by generating equidepth partitions for a relation and maintaining equidepth histograms. This paper presents a new technique to generate equidepth partitions for a secondary memory resident relation using a linear median find algorithm. A variation of this technique, which involves sorting of the individual blocks, is also proposed and extended to generate arbitrary number of partitions. The proposed techniques are compared with an external sorting based partitioning approach. Finally, an overall strategy to select the partitioning algorithm with possibly dynamic allocation of buffers is proposed.

UR - https://www.scopus.com/pages/publications/85049913453

UR - https://www.scopus.com/pages/publications/85049913453#tab=citedBy

U2 - 10.1109/SOAC.1991.143854

DO - 10.1109/SOAC.1991.143854

M3 - Conference contribution

AN - SCOPUS:85049913453

T3 - Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

SP - 92

EP - 101

BT - Proceedings of the 1991 Symposium on Applied Computing, SOAC 1991

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1991 Symposium on Applied Computing, SOAC 1991

Y2 - 3 April 1991 through 5 April 1991

ER -

Equidepth partitioning of a data set based on finding its medians

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this