Abstract
In this paper, we will present a novel progressive algorithm for computing skyline queries. The algorithm is based on the depth-first search paradigm. It can be shown that the new algorithm is I/O optimal. Further, we can show that the algorithm takes a logarithmic memory space in 2D-space in the worst case if there are not many intersections in an adopted R-tree. Our experiment demonstrated that the new algorithm is more scalable and efficient than the existing techniques especially in a low dimensional space. The experiment also showed that the algorithm is progressive in a way sensitive to a user’s preference.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Borzsonyi, S., Kossmann, D., Stocker, K.: The Skyline Operator. In: International Conference on Data Engineering ICDE (2001)
Beckmann, N., Kriegel, H., Schneider, R., Seeger, B.: The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: SIGMOD (1990)
Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., Abbadi, A.: Constrained Nearest Neighbor Queries. In: SSTD (2001)
Gaede, V., Gunther, O.: Multidimentional Access Methods. Computing Surveys 30(2), 170–231 (1998)
Hjaltason, G., Samet, H.: Distance Browsing in Spatial Databases. ACM TODS 24(2), 265–318 (1999)
Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maximum of a set of vectors. Journal of the ACM 22(4), 469–476 (1975)
Kossmann, D., Ramsak, F., Rost, S.: Shooting Stars in the Sky: An Online Algorithm for Skyline Queries. In: VLDB 2002 (2002)
Hadjieleftheriou, M.: Spatial Index Library, http://www.cs.ucr.edu/marioh/spatialindex/index.html (2002)
Lu, H.X., Luo, Y., Lin, X.: An Optimal Divide-Conquer Algorithm for 2D Skyline. In: ADBIS (2003)
Luo, Y., Lu, H.X., Lin, X.: A Scalable and I/O Optimal Skyline Processing Algorithm (full paper) (2004)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1985)
Papadias, D., Tao, Y., Fu, G., Seeger, B.: An Optimal Progressive Alogrithm for Skyline Queries. In: SIGMOD (2003)
Roussopoulos, N., Kelly, S., Vincent, F.: Nearest Neighbor Queries. In: SIGMOD (1995)
Steuer, R.: Multiple Criteria Optimization. Wiley, New York (1986)
Tan, K.L., Eng, P.K., Ooi, B.C.: Efficient Progressive Skyline Computation. In: VLDB (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Luo, Y., Lu, HX., Lin, X. (2004). A Scalable and I/O Optimal Skyline Processing Algorithm. In: Li, Q., Wang, G., Feng, L. (eds) Advances in Web-Age Information Management. WAIM 2004. Lecture Notes in Computer Science, vol 3129. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27772-9_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-27772-9_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22418-1
Online ISBN: 978-3-540-27772-9
eBook Packages: Springer Book Archive