Optimized k-Nearest Neighbor Search with Range Query
Abstract
K-Nearest Neighbor search is used extensively in fields like computer vision, DNA specification, object recognition and many more. Online map applications are also used tremendously due to the advances in Geographic Information System (GIS) data. These geospatial objects can be retrieved by using spatial range query. In our proposed work we find the nearest neighbors across any query point q, using an over estimated value of k. The Range Query calculated area is used to estimate the number of k neighbors. If the initial value of k doesn’t reveal all the nearest neighbors inside R, the value of k is multiplied with a constant factor epsilon. In this way all the nearest neighbors inside R are retrieved with in 1 or 2 iterations. The computational complexity of the proposed algorithm turns out to be O(n), compared to the complexity of Density Based Range Query algorithm i.e., O log(n2 + n). This makes our proposed algorithm a more optimized solution.References
Y. Tao, J. Zhang, D. Papadias and N. Mamoulis, "An Efficient cost
model for optimization of nearest neighbor search in low and
medium dimensional spaces", Journal of IEEE Transactions on
Knowledge and Data Engineering, vol. 16, no. 10, pp. 1169-1184,
K.A. Hawick, P.D. Coddington and H.A. James, "Distributed
frameworks and parallel algorithms for processing large scale
geographic data," Journal of Parallel Computing - Special issue:
High Performance Computing with Geographical Data, vol. 29, no.
, pp. 1297-1333, 2003.
W.D. Bae, S. Alkobaisi, S.H. Kim, S. Narayanappa and
C. Shahabi, "Web data retrieval: Solving spatial range queries
using k-Nearest neighbor searches", Geo Informatica , vol. 13, no.
, pp. 483-514, 2009.
G. Beskales, M.A. Soliman and I.F. Ilyas, "Efficient search for the
top-k probable nearest neighbors in uncerain databases",
Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 326-339,
August 2008.
B. Aydin, "Parallel algorithms on nearest neighbor search", Survey
Paper for Parallel Algorithms - Georgia State University, April
K. Katu and T. Hosino, "Solving k-nearest neighbor problem on
multiple graphics processor", Proceedings of the 10th IEEE/ACM
International Conference on Cluster, Cloud and Grid Computing,
pp. 769-773, 15 July, 2010.
T. W. P. Series, "Euclidean Distance, raw, normalized and doublescaled coefficients", Advanced Projects R&D, September 2005.
[Online]. Available: http://www.pbarrett.net/techpapers/euclid.pdf.
D. Liu, E.P. Lim and W.K Ng, "Efficient k nearest neighbor
queries on remote spatial databases using range estimation",
Procceedings of 14th International Conference on Scientific and
Statistical Database Management, pp.121-130, 26 July, 2002.
G.R. Hjaltason and H. Samet, "Distance browsing in spatial
databases", ACM Transactions on Database Systems, vol. 24, no.
, pp. 265-318, 1999.
P. Danziger, "Big O Notation", 2015. [Online]. Available:
http://www.wikipedia.org/w/wiki.phtml?title=Big_O_notation.
V. Garcia, E. Debreuve and M. Barlaud, “Fast k nearest neighbor
search using GPUâ€, IEEE Computer Society Conference on
Computer Vision and Pattern Recognition Workshops, Anchorage,
AK, 23-28, pp. 1-6, June 2008.
