Efficient Maximum Range Search on Remote Spatial Databases Using k-Nearest Neighbor Queries

摘要

Supporting aggregate range queries on remote spatial databases suffers from 1) huge and/or large numbers of databases, and 2) limited type of access interfaces. This paper applies the Regular Polygon based Search Algorithm (RPSA) to effectively addressing these problems. This algorithm requests a series of k-NN queries to obtain approximate aggregate range query results. The query point of a subsequent k-NN query is chosen from among the vertices of a regular polygon inscribed in a previously searched circle. Experimental results for maximum range query searches show that Precision is over 0.87 for a uniformly distributed dataset ,over 0.92 for a skew-distributed dataset ,and over 0.90 for a real dataset. Also, Number of Requests (NOR) ranges between 3.2 and 4.3, between 3.9 and 4.9, and between 3.0 and 4.2, respectively.