A unified approach for computing top-k pairs in multidimensional space
- 1 April 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 1031-1042
Abstract
Top-k pairs queries have many real applications. k closest pairs queries, k furthest pairs queries and their bichromatic variants are some of the examples of the top-k pairs queries that rank the pairs on distance functions. While these queries have received significant research attention, there does not exist a unified approach that can efficiently answer all these queries. Moreover, there is no existing work that supports top-k pairs queries based on generic scoring functions. In this paper, we present a unified approach that supports a broad class of top-k pairs queries including the queries mentioned above. Our proposed approach allows the users to define a local scoring function for each attribute involved in the query and a global scoring function that computes the final score of each pair by combining its scores on different attributes. We propose efficient internal and external memory algorithms and our theoretical analysis shows that the expected performance of the algorithms is optimal when two or less attributes are involved. Our approach does not require any pre-built indexes, is easy to implement and has low memory requirement. We conduct extensive experiments to demonstrate the efficiency of our proposed approach.Keywords
This publication has 17 references indexed in Scilit:
- 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
- Continuous monitoring of top-k queries over sliding windows2006
- Progressive skyline computation in database systemsACM Transactions on Database Systems, 2005
- Optimal aggregation algorithms for middlewareJournal of Computer and System Sciences, 2003
- On Spatial-Range Closest-Pair Query2003
- Minimal probing2002
- External memory algorithms and data structuresACM Computing Surveys, 2001
- Closest pair queries in spatial databases2000
- Combining Fuzzy Information from Multiple SystemsJournal of Computer and System Sciences, 1999