Efficient skyline computation in metric space

ABSTRACT

Given a set of n query points in a general metric space, a metric-space skyline (MSS) query asks what are the closest points to all these query points in the database. Here, consider for any point p, if there are no other points in the database which have less or equal distance to all the query points, then p is denoted as one of the closest points to the query points. This problem is a direct generalization of the recently proposed spatial-skyline query problem, where all the points are located in two or three dimensional Euclidean space. It is also closely related with the nearest neighbor (NN) query, the range query and the common skyline query problem. In this paper, we have developed new algorithms to aggressively prune non-skyline points from the search space. We also contribute two new optimization techniques to reduce the number of distance computations and dominance tests. Our experimental evaluation has shown the effectiveness and efficiency of our approach.

REFERENCES

• 1: Elke Achtert , Christian Böhm , Peer Kröger , Peter Kunath , Alexey Pryakhin , Matthias Renz, Efficient reverse k-nearest neighbor search in arbitrary metric spaces, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142531]
• 2: 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
• 3: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
• 4: Tolga Bozkaya , Meral Ozsoyoglu, Indexing large metric spaces for similarity search queries, ACM Transactions on Database Systems (TODS), v.24 n.3, p.361-404, Sept. 1999 [doi>10.1145/328939.328959]
• 5: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 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: Chee Yong Chan, H. V. Jagadish, Kian-Lee Tan, Anthony K. H. Tung, and Zhenjie Zhang. On high dimensional skylines. In EDBT, pages 478--495, 2006.
• 8: Lei Chen , Xiang Lian, Dynamic skyline queries in metric spaces, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353386]
• 9: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting, 2002.
• 10: Paolo Ciaccia and Marco Patella. Bulk loading the m-tree. In In 9th Australasian Database Conference (ADC'98, pages 15--26, 1998.
• 11: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 12: E. Erkut. The discrete p-dispersion problem. Eur. J. Opnl. Res., 46:48--60, 1990.
• 13: David Fuhry, Ruoming Jin, and Donghui Zhang. Efficient skyline computation in metric space. Technical report, Kent State University, April 2008.
• 14: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 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: 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]
• 17: D. H. McLain. Drawing contours from arbitrary data points. Comput. J., 17(4):318--324, 1974.
• 18: Daniel Miranker, Weijia Xu, and Rui Mao. Mobios: A metric-space dbms to support biological discovery. ssdbm, 00:241, 2003.
• 19: Gonzalo Navarro, Searching in Metric Spaces by Spatial Approximation, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.141, September 21-24, 1999
• 20: S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol, 48(3):443--53, 1970.
• 21: 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]
• 22: Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005 [doi>10.1145/1071610.1071616]
• 23: Jian Pei , Wen Jin , Martin Ester , Yufei Tao, Catching the best views of skyline: a semantic approach based on decisive subspaces, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: S. S. Ravi, D. J. Rosenkrantz, and G. K. Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299--310, 1994.
• 26: Parke Godfrey Ryan. Maximal vector computation in large data sets.
• 27: 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
• 28: R. Steuer. Multiple criteria optimization. Wiley, New York, NY, 1986.
• 29: 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
• 30: Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett., 40(4):175--179, 1991.
• 31: Grady Ward. Moby Word Lists. Project Gutenberg, 2002.
• 32: Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
• 33: 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