Progressive skyline computation in database systems

ABSTRACT

The skyline of a d-dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.

REFERENCES

• 1: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Balke, W., Gunzer, U., and Zheng, J. 2004. Efficient distributed skylining for Web information systems. In Proceedings of the International Conference on Extending Database Technology (EDBT; Heraklio, Greece, Mar. 14--18). 256--273.
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 5: Christian Böhm , Hans-Peter Kriegel, Determining the Convex Hull in Large Multidimensional Databases, Proceedings of the Third International Conference on Data Warehousing and Knowledge Discovery, p.294-306, September 05-07, 2001
• 6: 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
• 7: C. Buchta, On the average number of maxima in a set of vectors, Information Processing Letters, v.33 n.2, p.63-65, Nov. 10, 1989 [doi>10.1016/0020-0190(89)90156-7]
• 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: Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with pre-sorting. In Proceedings of the IEEE International Conference on Data Engineering (ICDE; Bangalore, India, Mar. 5--8). 717--719.
• 10: 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]
• 11: Hakan Ferhatosmanoglu , Ioana Stanoi , Divyakant Agrawal , Amr El Abbadi, Constrained Nearest Neighbor Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.257-278, July 12-15, 2001
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999 [doi>10.1109/2.781635]
• 14: Henrich, A. 1994. A distance scan algorithm for spatial access structures. In Proceedings of the ACM Workshop on Geographic Information Systems (ACM GIS; Gaithersburg, MD, Dec.). 136--143.
• 15: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 16: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 17: Kossmann, D., Ramsak, F., and Rost, S. 2002. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the Very Large Data Bases Conference (VLDB; Hong Kong, China, Aug. 20--23). 275--286.
• 18: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 19: Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O]
• 20: Mclain, D. 1974. Drawing contours from arbitrary data points. Comput. J. 17, 4, 318--324.
• 21: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 22: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 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: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 25: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 26: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 27: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 28: Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999 [doi>10.1145/319806.319816]
• 29: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 30: Steuer, R. 1986. Multiple Criteria Optimization. Wiley, New York, NY.
• 31: 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
• 32: Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000 [doi>10.1109/69.842247]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
Skyline query, branch-and-bound algorithms, multidimensional access methods