Please use this identifier to cite or link to this item: https://doi.org/10.1109/IDEAS.2004.1319807
Title: Efficient algorithm for path-based range query in spatial databases
Authors: Ng, H.K.
Leong, H.W. 
Ho, N.L.
Issue Date: 2004
Source: 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. https://doi.org/10.1109/IDEAS.2004.1319807
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
URI: http://scholarbank.nus.edu.sg/handle/10635/41091
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.

SCOPUSTM   
Citations

3
checked on Dec 13, 2017

Page view(s)

62
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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