A New Quadtree-Based Skyline Query Algorithm

Abstract:

In this paper, the index structure, PR-quadtree for spatial data, is used to store data for a database. The properties of the quadtree are studied. With the properties prunning rules are set up for searching the Skyline set of the data stored in the quadtree. Through detailed analysis for the tree the method of finding some approximate skyline points is designed, by which a new skyline searching algorithm is given. The new algorithm is more effective.

• Periodical: Advanced Materials Research (Volume 981)
• Pages: 175-178
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.981.175
• Online since: July 2014
• Authors: Run Tao Liu, Yuan Jing Chen*, Da Yong Cao, De Yu Liu
• Keywords: Domination, PR-Quadtree, Skyline Query

References

[1] BORZSONYI, S., KOSSMANN, D., AND STOCKER, K. The skyline operator. In Proceedings of the International Conference on Data Engineering (ICDE'2001). 421–430.

[2] KOSSMANN, D., RAMSAK, F., AND ROST, S. Shooting stars in the sky: An online algorithmfor skyline queries. In Proceedings of the International Conference on Very Large Databases(VLDB'2002). 275–286.

DOI: 10.1016/b978-155860869-6/50032-9

[3] CHOMICKI, J., GODFREY, P., GRYZ, J., AND LIANG, D. Skyline with presorting. In Proceedings of the International Conference on Data Engineering (ICDE'2003). IEEE Computer Society, 717–816.

DOI: 10.1109/icde.2003.1260846

[4] LIN, X., YUAN, Y., WANG, W., AND LU, H. Stabbing the sky: Efficient skyline computation over sliding windows. In Proceedings of the International Conference on Data Engineering (ICDE'2005). IEEE Computer Society, 502–513.

DOI: 10.1109/icde.2005.137

[5] HUANG, Z., JENSEN,C. S., LU, H., ANDOOI,B.C. Skyline queries against mobile lightweight devices in MANETs. In Proceedings of the International Conference on Data Engineering (ICDE'2006). IEEE Computer Society.

DOI: 10.1109/icde.2006.142

[6] PAPADIAS D, TAO Y, FU G, SEEGER B. An Optimal and Progressive Algorithm for Skyline Queries[C]. In Proceedings of the ACM SIMGOD International Conference on Management of Data, 2003, 467-478.

DOI: 10.1145/872757.872814

[7] PAPADIAS D, TAO Y, FU G, SEEGER B. Progressive Skyline Computation in Database Systems[J]. ACM Transactions on Database Systems, 2005, 30(1): 41-82.

DOI: 10.1145/1061318.1061320

[8] YANG J, QU B, LI C P, CHEN H. DC-Tree: An Algorithm for Skyline Query on Data Streams[M], In Advanced Data Mining and Applications, 2008, 644-651.

DOI: 10.1007/978-3-540-88192-6_67

[9] Wu Y X, Yang Q, Li C P, Chen H. DC-Tree：a kind of Skyline Query on Data Streams[J]. Computer Science, 2007, 34(10), 33-35.

[10] Guo W, Guo J and Hu Z Y. Index Techniques of Spatial Database[M]. Shanghai Jiao Tong University Press, 2006, 100-103.