Continuous monitoring of top-k queries over sliding windows

ABSTRACT

Given a dataset P and a preference function f, a top-k query retrieves the k tuples in P with the highest scores according to f. Even though the problem is well-studied in conventional databases, the existing methods are inapplicable to highly dynamic environments involving numerous long-running queries. This paper studies continuous monitoring of top-k queries over a fixed-size window W of the most recent data. The window size can be expressed either in terms of the number of active tuples or time units. We propose a general methodology for top-k monitoring that restricts processing to the sub-domains of the workspace that influence the result of some query. To cope with high stream rates and provide fast answers in an on-line fashion, the data in W reside in main memory. The valid records are indexed by a grid structure, which also maintains book-keeping information. We present two processing techniques: the first one computes the new answer of a query whenever some of the current top-k points expire; the second one partially pre-computes the future changes in the result, achieving better running time at the expense of slightly higher space requirements. We analyze the performance of both algorithms and evaluate their efficiency through extensive experiments. Finally, we extend the proposed framework to other query types and a different data stream model.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 3: [3] W.-T. Balke, U. Güntzer, and J. X. Zheng. Efficient distributed skylining for web information systems. In EDBT, pages 256-273, 2004.
• 4: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 5: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 6: [6] Y. Cai, K. A. Hua, and G. Cao. Processing range-monitoring queries on heterogeneous mobile objects. In MDM, pages 27-38, 2004.
• 7: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 8: Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.391-402, May 15-18, 2000, Dallas, Texas, United States
• 9: Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004 [doi>10.1109/TKDE.2004.30]
• 10: A Sampling-Based Estimator for Top-k Query, Proceedings of the 18th International Conference on Data Engineering, p.617, February 26-March 01, 2002
• 11: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 12: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 13: [13] B. Gedik and L. Liu. MobiEyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In EDBT, pages 67-87, 2004.
• 14: Vagelis Hristidis , Yannis Papakonstantinou, Algorithms and applications for answering ranked queries using ranked views, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.1, p.49-70, January 2004 [doi>10.1007/s00778-003-0099-8]
• 15: [15] I. F. Ilyas, W. G. Aref, and A. K. Elmagarmid. Joining ranked inputs in practice. In VLDB, pages 950-961, 2002.
• 16: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 17: Ihab F. Ilyas , Rahul Shah , Walid G. Aref , Jeffrey Scott Vitter , Ahmed K. Elmagarmid, Rank-aware query optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007593]
• 18: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch, Main Memory Evaluation of Monitoring Queries Over Moving Objects, Distributed and Parallel Databases, v.15 n.2, p.117-135, March 2004 [doi>10.1023/B:DAPD.0000013068.25976.88]
• 19: [19] N. Koudas, B. C. Ooi, K.-L. Tan, and R. Zhang. Approximate NN queries on streams with guaranteed error/performance bounds. In VLDB, pages 804-815, 2004.
• 20: Xuemin Lin , Yidong Yuan , Wei Wang , Hongjun Lu, Stabbing the Sky: Efficient Skyline Computation over Sliding Windows, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.502-513, April 05-08, 2005 [doi>10.1109/ICDE.2005.137]
• 21: Amélie Marian , Nicolas Bruno , Luis Gravano, Evaluating top-k queries over web-accessible databases, ACM Transactions on Database Systems (TODS), v.29 n.2, p.319-362, June 2004 [doi>10.1145/1005566.1005569]
• 22: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 23: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 24: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 25: Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002 [doi>10.1109/TC.2002.1039840 ]
• 26: Yufei Tao , Dimitris Papadias, Maintaining Sliding Window Skylines on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.18 n.3, p.377-391, March 2006 [doi>10.1109/TKDE.2006.48]
• 27: [27] M. Theobald, G. Weikum, and R. Schenkel. Top-k query evaluation with probabilistic guarantees. In VLDB, pages 648-659, 2004.
• 28: [28] P. Tsaparas, T. Palpanas, Y. Kotidis, N. Koudas, and D. Srivastava. Ranked join indices. In ICDE, 2003.
• 29: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 30: [30] K. Yi, H. Yu, J. Yang, G. Xia, and Y. Chen. Efficient maintenance of materialized top-k views. In ICDE, pages 189-200, 2003.
• 31: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
continuous queries, sliding windows, top-k processing