Supporting Sum Range Queries on Remote Spatial Databases Using k-Nearest Neighbor Search

Supporting aggregate range queries on remote spatial databases suffers from 1) huge and/or large number of databases, and 2) limited type of access interfaces. This paper proposes Regular Polygon based Search Algorithm (RPSA) to overcome these difficulties. RPSA 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 among vertices of a regular polygon inscribed in a before-searched circle. Experimental results on sum range query search show that Precision is over 0.99 for uniformly distributed dataset, over 0.97 for skew-distributed dataset, and over 0.97 for real dataset. Also, Number of Requests (NOR) ranges between 3.1 and 3.9, between 3.4 to 4.3, and between 2.7 and 3.7, respectively.