Efficient algorithm for path-based range query in spatial databases

Abstract

In this paper, we study the Path-based Range Query (PRQ) for 2-dimensional spatial database defined as fallows: Given a sequence of query points, P = {p1, p2, ..., pn}, and a search distance d, we want to report all paints in the spatial database that are within a distance d of some point pi in P. This query arises from traveler information systems where it is often a feature to report events that lie nearby a planned route. The simple method of performing Repeated Range Query (RRQ), i.e. the standard range query for each query point p,- (I ≤ i ≤ n) and combining the results is inefficient as it involves multiple searches on the database. We present an algorithm for the PRQ that uses only one pass of the R-tree while simultaneously process all the points in the query path P. We generalize pruning rules for the standard range query and also present new ones for efficient processing of PRQ. Extensive experiments on the PRQ and RRQ using various different datasets (real and randomly-generated), different R-tree variants (including bulk-loaded ones), over different query paths P, and search distances d. Experiments show that the algorithm for PRQ outperforms RRQ significantly and that this is consistent across the various problem parameters studied. Recently, we have also compared this basic PRQ algorithm with more refined techniques for the PRQ such as the sorted-path algorithm and the rectangle intersection method. Our simple algorithm performs well in comparison to these more sophisticated methods.