Abstract
One of the most representative and studied Distance-Based Queries in Spatial Databases is the K-Closest-Pairs Query (KCPQ). This query involves two spatial data sets and a distance function to measure the degree of closeness, along with a given number K of elements of the result. The output is a set of pairs of objects (with one object element from each set), with the K lowest distances. In this paper, we study the problem of processing KCPQs between RAM-based point sets, using Plane-Sweep (PS) algorithms. We utilize two improvements that can be applied to a PS algorithm and propose a new algorithm that minimizes the number of distance computations, in comparison to the classic PS algorithm. By extensive experimentation, using real and synthetic data sets, we highlight the most efficient improvement and show that the new PS algorithm outperforms the classic one, in most cases.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In: SIGMOD Conference, pp. 322–331 (1990)
Brinkhoff, T., Kriegel, H.P., Seeger, B.: Efficient Processing of Spatial Joins Using R-trees. In: SIGMOD Conference, pp. 237–246 (1993)
Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M.: Closest Pair Queries in Spatial Databases. In: SIGMOD Conference, pp. 189–200 (2000)
Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M.: Algorithms for Processing K-Closest-Pair Queries in Spatial Databases. Data & Knowledge Engineering 49(1), 67–104 (2004)
Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching. In: SIGMOD Conference, pp. 47–57 (1984)
Hinrichs, K., Nievergelt, J., Schorn, P.: Plane-Sweep Solves the Closest Pair Problem Elegantly. Information Processing Letters 26(5), 255–261 (1988)
Hjaltason, G.R., Samet, H.: Incremental Distance Join Algorithms for Spatial Databases. In: SIGMOD Conference, pp. 237–248 (1998)
Jacox, E.H., Samet, H.: Spatial Join Techniques. TODS 32(1), article 7, 1–44 (2007)
Kim, Y.J., Patel, J.: Performance Comparison of the R*-tree and the Quadtree for kNN and Distance Join Queries. IEEE TKDE 22(7), 1014–1027 (2010)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer (1985)
Rigaux, P., Scholl, M., Voisard, A.: Introduction to Spatial Databases: Applications to GIS. Morgan Kaufmann (2000)
Shin, H., Moon, B., Lee, S.: Adaptive and Incremental Processing for Distance Join Queries. IEEE TKDE 15(6), 1561–1578 (2003)
Zheng, K., Zhou, X., Fung, P.C., Xie, K.: Spatial query processing for fuzzy objects. VLDB Journal 21, 729–751 (2012)
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
Roumelis, G., Vassilakopoulos, M., Corral, A., Manolopoulos, Y. (2014). A New Plane-Sweep Algorithm for the K-Closest-Pairs Query. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds) SOFSEM 2014: Theory and Practice of Computer Science. SOFSEM 2014. Lecture Notes in Computer Science, vol 8327. Springer, Cham. https://doi.org/10.1007/978-3-319-04298-5_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-04298-5_42
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04297-8
Online ISBN: 978-3-319-04298-5
eBook Packages: Computer ScienceComputer Science (R0)