A Unified Framework for Answering k Closest Pairs Queries and Variants
Muhammad Aamir Cheema, Xuemin Lin, Haixun Wang, Jianmin Wang, Wenjie Zhang · IEEE Transactions on Knowledge and Data Engineering · 2014
Given a scoring function that computes the score of a pair of objects, a top-$k$pairs query returns$k$pairs with the smallest scores. In this paper, we present a unified framework for answering generic top-$k$pairs queries including$k$-closest pairs queries,$k$-furthest pairs queries and their variants. Note that$k$-closest pairs query is a special case of top-$k$pairs queries where the scoring function is the distance between the two objects in a pair. We are the first to present a unified framework to efficiently answer a broad class of top-$k$queries including the queries mentioned above. We present efficient algorithms and provide a detailed theoretical analysis that demonstrates that the expected performance of our proposed algorithms is optimal for two dimensional data sets. Furthermore, our framework does not require pre-built indexes, uses limited main memory and is easy to implement. We also extend our techniques to support top-$k$pairs queries on multi-valued (or uncertain) objects. We also demonstrate that our framework can handle exclusive top-$k$pairs queries. Our extensive experimental study demonstrates effectiveness and efficiency of our proposed techniques.