2012 | OriginalPaper | Chapter
Multistep Search Algorithm for Sum k-Nearest Neighbor Queries on Remote Spatial Databases
Authors : Hideki Sato, Ryoichi Narita
Published in: Intelligent Interactive Multimedia: Systems and Services
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Processing
sum k
-Nearest Neighbor (NN) queries on remote spatial databases suffers from a large amount of communication. In this paper, we propose
RQP-M
search algorithm for efficiently searching
sum k
-NN query results to overcome the difficulty. It refines query results originally searched by
RQP-S
algorithm with subsequent
k
-NN queries, whose query points are chosen among vertices of a regular polygon inscribed in a before-searched circle. Experimental results show that
Precision
is over 0.99 for uniformly distributed data, over 0.95 for skew-distributed data, and over 0.97 for real data. Also,
NOR (Number of Requests)
ranges between 3.2 and 4.0, between 3.1 to 3.8, and between 2.9 and 3.5, respectively.
Precision
of
RQP-M
increases by 0.04-0.20 for uniformly distributed data, in comparison with that of
RQP-S
.