Closest Pair Query on Spatial Data Sets without Index

In this work, we present an algorithm that finds the closest pair on two data sets, assuming that neither set has an index. A straightforward solution is to build the spatial index on the fly, and then apply algorithms that use such indexes. But if the sets are not used again these techniques are inefficient. Our algorithm considers two steps: First, each set is partitioned into a collection of subsets, or clusters, spatially defined by means of an MBR (Minimum Bounding Rectangle). The second step consists in processing the partitions using a family of metrics defined for the MBRs, as a filter for finding the closest pair. We experimentally compared our proposal with techniques that use indexes and techniques that do not. The results of our experiments shown that our algorithm overcome these techniques on several realist scenari