Efficient Top-k Retrieval on Massive Data
Authors:
- 27 April 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 27 (10) , 2687-2699
Abstract
In many applications, top-k query is an important operation to return a set of interesting points in a potentially huge data space. It is analyzed in this paper that the existing algorithms cannot process top-k query on massive data efficiently. This paper proposes a novel table-scan-based T2S algorithm to efficiently compute top-k results on massive data. T2S first constructs the presorted table, whose tuples are arranged in the order of the round-robin retrieval on the sorted lists. T2S maintains only fixed number of tuples to compute results. The early termination checking for T2S is presented in this paper, along with the analysis of scan depth. The selective retrieval is devised to skip the tuples in the presorted table which are not top-k results. The theoretical analysis proves that selective retrieval can reduce the number of the retrieved tuples significantly. The construction and incremental-update/batchprocessing methods for the used structures are proposed in this paper. The extensive experimental results, conducted on synthetic and real-life data sets, show that T2S has a significant advantage over the existing algorithms.Keywords
Funding Information
- National Basic Research (973) Program of China (2012CB316200)
- National Natural Science Foundation of China (61402130, 61272046, 61190115, 61173022, 61033015)
This publication has 13 references indexed in Scilit:
- Subspace top-k query processing using the hybrid-layer index with a tight boundData & Knowledge Engineering, 2013
- Efficient Skyline Computation on Big DataIEEE Transactions on Knowledge and Data Engineering, 2012
- Supporting early pruning in top-k query processing on massive dataInformation Processing Letters, 2011
- Efficient processing of exact top-k queries over disk-resident sorted listsThe VLDB Journal, 2009
- A survey of top- k query processing techniques in relational database systemsACM Computing Surveys, 2008
- Efficient top- k aggregation of ranked inputsACM Transactions on Database Systems, 2007
- Algorithms and applications for answering ranked queries using ranked viewsThe VLDB Journal, 2004
- Efficient similarity search and classification via rank aggregation2003
- Optimal aggregation algorithms for middleware2001
- The onion technique2000