A Generic Framework for Top-${\schmi k}$ Pairs and Top- ${\schmi k}$ Objects Queries over Sliding Windows
- 1 June 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 26 (6) , 1349-1366
Abstract
Top-k pairs and top-k objects queries have received significant attention by the research community. In this paper, we present the first approach to answer a broad class of top-k pairs and top-k objects queries over sliding windows. Our framework handles multiple top-k 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. Furthermore, the framework allows the users to define arbitrarily complex scoring functions and supports out-of-order data streams. For all the queries that use the same scoring function, we need to maintain only one K-skyband. We present efficient techniques for the K-skyband 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. For top-k pairs queries, we demonstrate the efficiency of our approach by comparing it with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost. For top-k objects queries, our experimental results demonstrate the superiority of our algorithm over the state-of-the-art algorithm.Keywords
This publication has 24 references indexed in Scilit:
- Loyalty-based selection2012
- Efficiently Monitoring Top-k Pairs over Sliding Windows2012
- Continuous Monitoring of Exclusive Closest Pairs2007
- 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
- Optimal aggregation algorithms for middlewareJournal of Computer and System Sciences, 2003
- The Skyline operator2002
- Closest pair queries in spatial databases2000
- Query processing issues in image (multimedia) databases1999