Equidepth partitioning of a data set based on finding its medians

Aditya P. Gurajada, Jaideep Srivastava

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 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 languageEnglish (US)
Title of host publicationProceedings of the 1991 Symposium on Applied Computing, SOAC 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages92-101
Number of pages10
ISBN (Electronic)0818621362, 9780818621369
DOIs
StatePublished - Jan 1 1991
Event1991 Symposium on Applied Computing, SOAC 1991 - Kansas City, United States
Duration: Apr 3 1991Apr 5 1991

Publication series

NameProceedings of the 1991 Symposium on Applied Computing, SOAC 1991

Conference

Conference1991 Symposium on Applied Computing, SOAC 1991
CountryUnited States
CityKansas City
Period4/3/914/5/91

Fingerprint Dive into the research topics of 'Equidepth partitioning of a data set based on finding its medians'. Together they form a unique fingerprint.

Cite this