Please use this identifier to cite or link to this item:
Title: Efficient algorithm for path-based range query in spatial databases
Authors: Ng, H.K.
Leong, H.W. 
Ho, N.L.
Issue Date: 2004
Citation: Ng, H.K.,Leong, H.W.,Ho, N.L. (2004). Efficient algorithm for path-based range query in spatial databases. Proceedings of the International Database Engineering and Applications Symposium, IDEAS : 334-343. ScholarBank@NUS Repository.
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.
Source Title: Proceedings of the International Database Engineering and Applications Symposium, IDEAS
ISBN: 0769521681
ISSN: 10988068
DOI: 10.1109/IDEAS.2004.1319807
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.