A Distributed Algorithm for Skyline Query Based on Pre-Clustering

Abstract:

With the increasing availability and mobile application of LBS (Location-Based Services), large scale spatial objects remind challenge in cloud environments. In order to retrieve a few data items within a very large structured data set, skyline queries are utilized to optimize a single respectively multiple criteria. In this paper, we develop a new pre-clustering-based skyline queries technique to address the skewed distribution problem. We also present distributed approaches that construct grid index and process skyline queries. We evaluate the effectiveness of our algorithms with extensive experiments using real data sets. The results demonstrate the efficiency and scalability of our skyline queries algorithms based on pre-clustering.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3982-3986
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3982
• Online since: September 2013
• Authors: Pei Qi Ruan, Chuan Wei Xu, Ji Ting Huang, Lun Ke Qing, Chang Qing Ji
• Keywords: MapReduce, Re-Clustering, Skyline

References

[1] Börzsönyi, S., Kossmann, D., Stocker, K.: The Skyline operator, In: Proceedings of ICDE, p.421–430 (2001).

[2] J. Dean and S. Ghemawat, Mapreduce: Simplified data processing on large clusters, Communications of the ACM, vol. 51, no. 1, p.107–113, (2008).

DOI: 10.1145/1327452.1327492

[3] Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting, In: Proceedings of International Conference on Data Engineering (ICDE), pp.717-816 (2003).

DOI: 10.1109/icde.2003.1260846

[4] Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries, In: Proceedings of International Conference on Management of Data (SIGMOD), pp.467-478 (2003).

DOI: 10.1145/872757.872814

[5] Balke, Wolf-Tilo, Ulrich Güntzer, and Jason Zheng. Efficient distributed skylining for web information systems, Advances in Database Technology-EDBT 2004 (2004): 573-574.

DOI: 10.1007/978-3-540-24741-8_16

[6] Wu, P. et al. Parallelizing skyline queries for scalable distribution, In: Proceedings of International Conference on Extending Database Technology (EDBT), pp.112-130 (2006).

DOI: 10.1007/11687238_10

[7] Wang, S., Ooi, B., Tung, A., Xu, L.: Efficient skyline query processing on peer-to-peer networks, In: Proceedings of International Conference on Data Engineering (ICDE), pp.1126-1135 (2007).

DOI: 10.1109/icde.2007.368971

[8] Hose, K., Lemke, C., Sattler, K.: Processing Relaxed Skylines in PDMS Using Distributed Data Summaries, In: Proceedings of International Conference on Information and Knowledge Management (CIKM), pp.425-434 (2006).

DOI: 10.1145/1183614.1183676

[9] Hose, Katja, and Akrivi Vlachou. A survey of skyline processing in highly distributed environments, The VLDB Journal—The International Journal on Very Large Data Bases 21. 3 (2012): 359-384.

DOI: 10.1007/s00778-011-0246-6

[10] D. Borthakur, The hadoop distributed file system: Architecture and design, Hadoop Project Website, vol. 11, p.21, (2007).

[11] Ji, C., Dong, T. et al. Inverted grid-based knn query processing with mapreduce, ChinaGrid, 2012 Seventh ChinaGrid Annual Conference on, p.25–33, IEEE.

DOI: 10.1109/chinagrid.2012.19