A Distance Scan Algorithm for Spatial Access Structures.
Andreas Henrich · 1994
In geographic information systems it is often useful to select an object located closest to a given point or to scan the objects with respect to their distance to a given point in ascending order. An example for a query of this type would be to retrieve ten hotels with at least three stars lying closest to the venue of a conference. Various subtypes of similar queries exist. On the other hand, research in geometric access structures has concentrated mainly on range queries. We present an efficient algorithm for closest- and distance-scan-queries of various kinds. Our algorithm is based on the nearest neighbour algorithm for k-d-trees given by Friedman et al. [FBF77] and refined by Sproull [Spr91]. We adapt this algorithm to external access structures and extend it to process a broader class of queries. Furthermore we show that the algorithm can be applied to point objects as well as to non-point objects, and that it can be used with all spatial access structures using a hierarchical dir...