Advertisement
Published in:
2014 | OriginalPaper | Chapter
A New Plane-Sweep Algorithm for the K-Closest-Pairs Query
Authors : George Roumelis, Michael Vassilakopoulos, Antonio Corral, Yannis Manolopoulos
Published in: SOFSEM 2014: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
One of the most representative and studied Distance-Based Queries in Spatial Databases is the
K
-Closest-Pairs Query (
K
CPQ). 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
K
CPQs 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.