Title: Approximate search algorithm for aggregate k-nearest neighbour queries on remote spatial databases

Authors: Hideki Sato; Ryoichi Narita

Addresses: School of Informatics, Daido University, 10-3 Takiharu-cho, Minami-ku, Nagoya 457-8530, Japan ' Aichi Toho University, 3-11 Heiwagaoka, Meito-ku, Nagoya 465-8515, Japan

Abstract: Searching Aggregate k-Nearest Neighbour (k-ANN) queries on remote spatial databases suffers from a large amount of communication. In order to overcome the difficulty, RQP-M algorithm for efficiently searching k-ANN query results is proposed in this paper. It refines query results originally searched by RQP-S with subsequent k-NN queries, whose query points are chosen among vertices of a regular polygon inscribed in a circle searched previously. Experimental results show that precision of sum k-NN query results is over 0.95 and Number of Requests (NOR) is at most 4.0. On the other hand, precision of max k-NN query results is over 0.95 and NOR is at most 5.6. RQP-M brings 0.04-0.20 increase in PRECISION of sum k-NN query results and over 0.40 increase in that of max k-NN query results, respectively, in comparison with RQP-S.

Keywords: aggregate k-nearest neighbour query; sum k-nearest neighbour query; max k-nearest neighbour query; RQP-S; representative query points; RQP-M; precision; NOR; number of requests; approximate search algorithm; remote spatial databases; information retrieval.

DOI: 10.1504/IJKWI.2013.052722

International Journal of Knowledge and Web Intelligence, 2013 Vol.4 No.1, pp.3 - 19

Published online: 18 Mar 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article