Efficiently Monitoring Top-k Pairs over Sliding Windows
- 1 April 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 798-809
Abstract
Top-k pairs queries have received significant attention by the research community. k-closest pairs queries, k-furthest pairs queries and their variants are among the most well studied special cases of the top-k pairs queries. In this paper, we present the first approach to answer a broad class of top-k pairs queries over sliding windows. Our framework handles multiple top-k pairs queries and each query is allowed to use a different scoring function, a different value of k and a different size of the sliding window. Although the number of possible pairs in the sliding window is quadratic to the number of objects N in the sliding window, we efficiently answer the top-k pairs query by maintaining a small subset of pairs called K-sky band which is expected to consist of O(K log(N/K)) pairs. For all the queries that use the same scoring function, we need to maintain only one K-sky band. We present efficient techniques for the K-sky band maintenance and query answering. We conduct a detailed complexity analysis and show that the expected cost of our approach is reasonably close to the lower bound cost. We experimentally verify this by comparing our approach with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost.Keywords
This publication has 20 references indexed in Scilit:
- Probabilistic Skyline Operator over Sliding WindowsInternational Conference on Data Engineering, 2009
- Continuous Monitoring of Exclusive Closest Pairs2007
- Efficiently Processing Continuous k-NN Queries on Data Streams2007
- Close pair queries in moving object databases2005
- An approximate algorithm for top-k closest pairs join query in large high dimensional dataData & Knowledge Engineering, 2005
- Progressive skyline computation in database systemsACM Transactions on Database Systems, 2005
- Ranked join indices2004
- The Skyline operator2002
- Closest pair queries in spatial databases2000
- Time bounds for selectionJournal of Computer and System Sciences, 1973