H.K. Ng and H.W. Leong (Singapore)
query processing, spatial range queries, algorithm
This paper revisits multi-point range query (MPRQ) for 2 d spatial database. In a previous paper, we introduced an efficient algorithm, PRQ, to answer the query for the case where database resides in main memory. This paper extends the algorithm to the general case in which the database is large and has to reside on disk. The MPRQ is defined as: Given a set of query points, P = {p1, p2, …, pn}, and a search distance d, report all points in the spatial database that are within a distance d of some point pi in P. The simple method of performing Repeated Range Query (RRQ), i.e. the standard range query for each query point pi (1 ≤ i ≤ n) and combining the results is inefficient as it involves multiple searches on the database. We show that PRQ-Disk still achieve better results and outperform RRQ-Disk, as in the case of main memory. Extensive experiments using various real-life datasets, different R tree variants (including bulk-loaded ones), over different query paths P, search distances d, and LRU buffering show that PRQ-Disk outperforms RRQ-Disk in terms of both query time and I/Os.
Important Links:
Go Back
