Abstract
To select representative objects from a large scale database is an important step to understand the database. A skyline query, which retrieves a set of non-dominated objects, is one of popular methods for selecting representative objects. In this paper, we have considered a distributed algorithm for computing a skyline query in order to handle “big data”. In conventional distributed algorithms for computing a skyline query, the values of each object of a local database have to be disclosed to another. Recently, we have to be aware of privacy in a database, in which such disclosures of privacy information in conventional distributed algorithms are not allowed. In this work, we propose a novel approach to compute the skyline in a multi-parties computing environment without disclosing individual values of objects to another party. Our method is designed to work in MapReduce framework − in Hadoop framework. Our experimental results confirm the effectiveness and scalability of the proposed secure skyline computation.
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
Similar content being viewed by others
References
Afrati, F.N., Koutris, P., Suciu, D., Ullman, J.D.: Parallel skyline queries. In: ICDT, pp. 274–284 (2012)
Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order preserving encryption for numeric data. In: ACM SIGMOD International Conference on Management of Data, pp. 563–574 (2004)
Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: ACM SIGMOD International Conference on Management of Data, pp. 439–450. ACM (2000)
Apache: Apache hadoop (2010). http://hadoop.apache.org
Arefin, M.S., Morimoto, Y.: Privacy aware parallel computation of skyline sets queries from distributed databases. In: 2013 International Conference on Computing, Networking and Communications (ICNC), pp. 186–192 (2011)
Balke, W.-T., Güntzer, U., Zheng, J.X.: Efficient distributed skylining for web information systems. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 256–273. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24741-8_16
Blanas, S., Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J., Tian, Y.: A comparison of join algorithms for log processing in MapReduce. In: SIGMOD, pp. 975–986 (2010)
Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of ICDE, pp. 421–430 (2001)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: Proceedings of ICDE, pp. 717–719 (2003)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 218–229. STOC 1987. ACM (1987)
Jiang, D., Tung, A.K.H., Chen, G.: Map-Join-Reduce: toward scalable and efficient data analysis on large clusters. In: IEEE TKDE, pp. 1299–1311 (2011)
Mullesgaard, K., Pedersen, H.L., Zhou, Y.: Efficient skyline computation in MapReduce. In: EDBT, pp. 37–48 (2014)
Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: an online algorithm for skyline queries. In: Proceedings of VLDB, pp. 275–286 (2002)
Lindell, Y., Pinkas, B.: Privacy preserving data mining. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 36–54. Springer, Heidelberg (2000). doi:10.1007/3-540-44598-6_3
Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30, 41–82 (2005)
Park, Y., Min, J.K., Shim, K.: Parallel computation of skyline and reverse skyline queries using MapReduce. Proc. VLDB Endow. 6(14), 2002–2013 (2013)
Rocha-Junior, J.B., Vlachou, A., Doulkeridis, C., Nørvåg, K.: AGiDS: a grid-based strategy for distributed skyline query processing. In: Hameurlain, A., Tjoa, A.M. (eds.) Globe 2009. LNCS, vol. 5697, pp. 12–23. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03715-3_2
Siddique, M.A., Tian, H., Morimoto, Y.: Distributed skyline computation of vertically splitted databases by using MapReduce. In: Han, W.-S., Lee, M.L., Muliantara, A., Sanjaya, N.A., Thalheim, B., Zhou, S. (eds.) DASFAA 2014. LNCS, vol. 8505, pp. 33–45. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43984-5_3
Siddique, M.A., Tian, H., Morimoto, Y.: k-dominant skyline query computation in MapReduce environment. IEICE Trans. Inf. Syst. 98, 1745–1361 (2015)
Tao, Y., Lin, W., Xiao, X.: Minimal MapReduce algorithm. In: Proceedings of SIGMOD, pp. 529–540 (2013)
Tian, H., Siddique, M.A., Morimoto, Y.: An efficient processing of k-dominant skyline query in MapReduce. In: Proceedings of ACM International Workshop on Bringing the Value of Big Data to Users (Data4U), pp. 29–35 (2014)
Vernica, R., Carey, M.J., Li, C.: Efficient parallel set-similarity joins using MapReduce. In: Proceedings of SIGMOD, pp. 495–506 (2010)
Wang, S., Ooi, B.C., Tung, A.K.H., Xu, L.: Efficient skyline query processing on peer-to-peer networks. In: 2007 IEEE 23rd International Conference on Data Engineering, pp. 1126–1135, April 2007
Williams, R.: A painless guide to CRC error detection algorithms (1996). ftp.rocksoft.com/papers/crc_v3.txt
Yao, A.C.: Protocols for secure computations. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 160–164 (1982)
Zhang, B., Zhou, S., Guan, J.: Adapting skyline computation to the MapReduce framework: algorithms and experiments. In: Xu, J., Yu, G., Zhou, S., Unland, R. (eds.) DASFAA 2011. LNCS, vol. 6637, pp. 403–414. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20244-5_39
Acknowledgment
This work is supported by KAKENHI (16K00155, 23500180, 25.03040) Japan. A. Zaman is supported by Japanese Government MEXT Scholarship. Annisa is supported by Indonesian Government DG-RSTHE scholarship.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Zaman, A., Siddique, M.A., Annisa, Morimoto, Y. (2016). Secure Computation of Skyline Query in MapReduce . In: Li, J., Li, X., Wang, S., Li, J., Sheng, Q. (eds) Advanced Data Mining and Applications. ADMA 2016. Lecture Notes in Computer Science(), vol 10086. Springer, Cham. https://doi.org/10.1007/978-3-319-49586-6_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-49586-6_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49585-9
Online ISBN: 978-3-319-49586-6
eBook Packages: Computer ScienceComputer Science (R0)