Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The problem of skyline computation has attracted considerable research attention. In the categorical domain the problem becomes more complicated, primarily due to the partially-ordered nature of the attributes of tuples.

In this paper, we initiate a study of streaming categorical skylines. We identify the limitations of existing work for offline categorical skyline computation and realize novel techniques for the problem of maintaining the skyline of categorical data in a streaming environment. In particular, we develop a lightweight data structure for indexing the tuples in the streaming buffer, that can gracefully adapt to tuples with many attributes and partially ordered domains of any size and complexity. Additionally, our study of the dominance relation in the dual space allows us to utilize geometric arrangements in order to index the categorical skyline and efficiently evaluate dominance queries. Lastly, a thorough experimental study evaluates the efficiency of the proposed techniques.

REFERENCES

• 1: P. K. Agarwal and M. Sharir. Arrangements and their applications. In Handbook of Computational Geometry, chapter 2, pages 49--119. Elsevier, 2000.
• 2: Mikhail J. Atallah , Susan Fox , Suzanne Lassandro, Algorithms and Theory of Computation Handbook, CRC Press, Inc., Boca Raton, FL, 1998
• 3: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 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: 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]
• 6: 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]
• 7: C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang. On high dimensional skylines. In EDBT, pages 478--495, 2006.
• 8: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In ICDE, pages 717--816, 2003.
• 9: Gautam Das , Dimitrios Gunopulos , Nick Koudas , Nikos Sarkas, Ad-hoc top-k query answering for data streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 11: Alan M. Frieze , Mark Jerrum, Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION, Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.1-13, May 29-31, 1995
• 12: 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
• 13: D. Halperin. Arrangements. In Handbook of Discrete and Computational Geometry, chapter 24, pages 529--562. CRC Press, 2004.
• 14: Ihab F. Ilyas , Volker Markl , Peter Haas , Paul Brown , Ashraf Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007641]
• 15: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 16: 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
• 17: Nick Koudas , Beng Chin Ooi , Kian-Lee Tan , Rui Zhang, Approximate NN queries on streams with guaranteed error/performance bounds, Proceedings of the Thirtieth international conference on Very large data bases, p.804-815, August 31-September 03, 2004, Toronto, Canada
• 18: 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
• 19: 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]
• 20: X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. Selecting stars: The k most representative skyline operator. In ICDE, pages 86--95, 2007.
• 21: 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]
• 22: Kyriakos Mouratidis , Spiridon Bakiras , Dimitris Papadias, Continuous monitoring of top-k queries over sliding windows, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142544]
• 23: 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]
• 24: 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
• 25: 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]
• 26: 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.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
categorical, data stream, partial order, skyline