Minimizing the communication cost for continuous skyline maintenance

ABSTRACT

Existing work in the skyline literature focuses on optimizing the processing cost. This paper aims at minimization of the communication overhead in client-server architectures, where a server continuously maintains the skyline of dynamic objects. Our first contribution is a Filter method that avoids transmission of updates from objects that cannot influence the skyline. Specifically, each object is assigned a filter so that it needs to issue an update only if it violates its filter. Filter achieves significant savings over the naive approach of transmitting all updates. Going one step further, we introduce the concept of frequent skyline query over a sliding window(FSQW). The motivation is that snapshot skylines are not very useful in streaming environments because they keep changing over time. Instead, FSQW reports the objects that appear in the skylines of at least θ ⋅ s of the s most recent timestamps (0 < θ ≤ 1). Filter can be easily adapted to FSQW processing, however, with potentially high overhead for large and frequently updated datasets. To further reduce the communication cost, we propose a Sampling method, which returns approximate FSQW results without computing each snapshot skyline. Finally, we integrate Filter and Sampling in a Hybrid approach that combines their individual advantages.

REFERENCES

• 1: 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]
• 2: W.-T. Balke, U. Güntzer, and J. X. Zheng. Efficient distributed skylining for web information systems. In EDBT, pages 256--273, 2004.
• 3: 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
• 4: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 5: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 6: Reynold Cheng , Ben Kao , Sunil Prabhakar , Alan Kwan , Yicheng Tu, Adaptive stream filters for entity-based queries with non-value tolerance, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In ICDE, pages 717--719, 2003.
• 8: Anindya Datta , Debra E. VanderMeer , Aslihan Celik , Vijay Kumar, Broadcast protocols to support efficient retrieval from databases by mobile users, ACM Transactions on Database Systems (TODS), v.24 n.1, p.1-79, March 1999 [doi>10.1145/310701.310710]
• 9: Evangelos Dellis , Bernhard Seeger, Efficient computation of reverse skyline queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: Parke Godfrey , Ryan Shipley , Jarek Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 11: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 12: Haibo Hu , Jianliang Xu , Dik Lun Lee, A generic framework for monitoring continuous spatial queries over moving objects, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066212]
• 13: Zhiyong Huang , Christian S. Jensen , Hua Lu , Beng Chin Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering, p.66, April 03-07, 2006 [doi>10.1109/ICDE.2006.142]
• 14: Ankur Jain , Edward Y. Chang , Yuan-Fang Wang, Adaptive stream resource management using Kalman Filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007573]
• 15: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 16: Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 17: 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, p.502-513, April 05-08, 2005 [doi>10.1109/ICDE.2005.137]
• 18: Michael Morse , Jignesh M. Patel , William I. Grosky, Efficient Continuous Skyline Computation, Proceedings of the 22nd International Conference on Data Engineering, p.108, April 03-07, 2006 [doi>10.1109/ICDE.2006.56]
• 19: Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: Kyriakos Mouratidis , Dimitris Papadias , Spiridon Bakiras , Yufei Tao, A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1451-1464, November 2005 [doi>10.1109/TKDE.2005.172]
• 21: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 22: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 23: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 24: 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]
• 25: Mehdi Sharifzadeh , Cyrus Shahabi, The spatial skyline queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 26: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 27: 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]
• 28: S. Wang, B.C. Ooi, A.K.H. Tung, and L. Xu. Efficient skyline query processing on peer-to-peer networks. In ICDE, pages 1126--1135, 2007.
• 29: P. Wu, D. Agrawal, Ö. Egecioglu, and A. E. Abbadi. Deltasky: Optimal maintenance of skyline deletions without exclusive dominance region generation. In ICDE, pages 486--495, 2007.
• 30: P. Wu, C. Zhang, Y. Feng, B.Y. Zhao, D. Agrawal, and A.E. Abbadi. Parallelizing skyline queries for scalable distribution. In EDBT, pages 112--130, 2006.
• 31: Tian Xia , Donghui Zhang, Refreshing the sky: the compressed skycube with efficient support for frequent updates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142529]
• 32: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Performance

Keywords:
communication, continuous query, skyline query