Abstract
The trend towards in-memory analytics and CPUs with an increasing number of cores calls for new algorithms that can efficiently utilize the available resources. This need is particularly evident in the case of CPU-intensive query operators. One example of such a query with applicability in data analytics is the skyline query. In this paper, we present APS kyline, a new approach for multicore skyline query processing, which adheres to the partition-execute-merge framework. Contrary to existing research, we focus on the partitioning phase to achieve significant performance gains, an issue largely overlooked in previous work in multicore processing. In particular, APS kyline employs an angle-based partitioning approach, which increases the degree of pruning that can be achieved in the execute phase, thus significantly reducing the number of candidate points that need to be checked in the final merging phase. APS kyline is extremely efficient for hard cases of skyline processing, as in the cases of datasets with large skyline result sets, where it is meaningful to exploit multicore processing.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Afrati, F.N., Koutris, P., Suciu, D., Ullman, J.D.: Parallel skyline queries. In: Proc. of ICDT (2012)
Blanas, S., Li, Y., Patel, J.M.: Design and evaluation of main memory hash join algorithms for multi-core CPUs. In: Proc. of SIGMOD (2011)
Bøgh, K.S., Assent, I., Magnani, M.: Efficient GPU-based skyline computation. In: Proc. of DaMoN (2013)
Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proc. of ICDE (2001)
Chan, C.-Y., Jagadish, H.V., Tan, K.-L., Tung, A.K.H., Zhang, Z.: On high dimensional skylines. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Böhm, K., Kemper, A., Grust, T., Böhm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 478–495. Springer, Heidelberg (2006)
Chomicki, J., Ciaccia, P., Meneghetti, N.: Skyline queries, front and back. SIGMOD Record 42(3), 6–18 (2013)
Heller, S., Herlihy, M.P., Luchangco, V., Moir, M., Scherer III, W.N., Shavit, N.N.: A Lazy Concurrent List-Based Set Algorithm. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 3–16. Springer, Heidelberg (2006)
Hose, K., Vlachou, A.: A survey of skyline processing in highly distributed environments. VLDB J. 21(3), 359–384 (2012)
Im, H., Park, J., Park, S.: Parallel skyline computation on multicore architectures. Inf. Syst. 36(4), 808–823 (2011)
Morse, M., Patel, J.M., Jagadish, H.: Efficient skyline computation over low-cardinality domains. In: Proc. of VLDB (2007)
Park, S., Kim, T., Park, J., Kim, J., Im, H.: Parallel skyline computation on multicore architectures. In: Proc. of ICDE (2009)
Selke, J., Lofi, C., Balke, W.T.: Highly scalable multiprocessing algorithms for preference-based database retrieval. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds.) DASFAA 2010. LNCS, vol. 5982, pp. 246–260. Springer, Heidelberg (2010)
Shang, H., Kitsuregawa, M.: Skyline operator on anti-correlated distributions. PVLDB 6(9), 649–660 (2013)
Torlone, R., Ciaccia, P.: Finding the best when it’s a matter of preference. In: Proc. of SEBD (2002)
Vlachou, A., Doulkeridis, C., Kotidis, Y.: Angle-based space partitioning for efficient parallel skyline computation. In: Proc. of SIGMOD (2008)
Woods, L., Alonso, G., Teubner, J.: Parallel computation of skyline queries. In: Proc. of FCCM (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Liknes, S., Vlachou, A., Doulkeridis, C., Nørvåg, K. (2014). APSkyline: Improved Skyline Computation for Multicore Architectures. In: Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (eds) Database Systems for Advanced Applications. DASFAA 2014. Lecture Notes in Computer Science, vol 8421. Springer, Cham. https://doi.org/10.1007/978-3-319-05810-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-05810-8_21
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05809-2
Online ISBN: 978-3-319-05810-8
eBook Packages: Computer ScienceComputer Science (R0)