A Unified Framework for Answering k Closest Pairs Queries and Variants

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 - lso 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.