Optimized k-Nearest Neighbor Search with Range Query

Authors

  • M. Rehman Department of Computer Science and Engineering, University of Engineering and Technology, Lahore, Pakistan
  • T. Ahmad Department of Computer Science and Engineering, University of Engineering and Technology, Lahore, Pakistan

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.

Downloads

Published

30-04-2015

How to Cite

[1]
M. Rehman and T. Ahmad, “Optimized k-Nearest Neighbor Search with Range Query”, The Nucleus, vol. 52, no. 2, pp. 45–49, Apr. 2015.

Issue

Section

Articles