Open AccessEfficient Maximum Range Search on Remote Spatial Databases Using k-Nearest Neighbor Queries
Author(s) -
Hideki Sato,
Ryoichi Narita
Publication year - 2013
Publication title -
procedia computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.334
H-Index - 76
ISSN - 1877-0509
DOI - 10.1016/j.procs.2013.09.166
Subject(s) - computer science , skew , polygon (computer graphics) , k nearest neighbors algorithm , range (aeronautics) , aggregate (composite) , database , spatial query , spatial database , data mining , range query (database) , point (geometry) , series (stratigraphy) , query optimization , information retrieval , sargable , web search query , search engine , spatial analysis , mathematics , artificial intelligence , telecommunications , statistics , materials science , geometry , frame (networking) , composite material , paleontology , biology
upporting 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom