DefinePK

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.