A Two-Pass Exact Algorithm for Selection on Parallel Disk Systems.
Numerous OLAP queries process selection operations of "top N", median, "top 5%", in data warehousing applications. Selection is a well-studied problem that has numerous applications in the management of data and databases since, typically, any complex data query can be reduced to a series of basic operations such as sorting and selection. The parallel selection has also become an important fundamental operation, especially after parallel databases were introduced. In this paper, we present a deterministic algorithmRecursive Sampling Selection (RSS)to solve the exact out-of-core selection problem, which we show needs no more than (2 +ε) passes (εbeing a very small fraction). We have compared ourRSSalgorithm with two other algorithms in the literature, namely, theDeterministic Sampling SelectionandQuickSelecton the Parallel Disks Systems. Our analysis shows thatDSSis a (2 +ε)-pass algorithm when the total number of input elementsNis a polynomial in the memory sizeM(i.e.,N=Mcfor some constantc). While, our proposed algorithmRSSruns in (2 +ε) passes without any assumptions. Experimental results indicate that bothRSSandDSSoutperformQuickSelecton the Parallel Disks Systems. Especially, the proposed algorithmRSSis more scalable and robust to handle big data when the input size is far greater than the core memory size, including the case ofN≫Mc.
Department of Computer Science and Engineering, University of Connecticut, Storrs, USA.
Tian
T
Mi
Department of Computer Science and Engineering, University of Connecticut, Storrs, USA.
Sanguthevar
S
Rajasekaran
Median; OLAP queries; Parallel Disk System; Selection