Open Access Open Access  Restricted Access Subscription or Fee Access

A New Top-K Nearest Neighbor and Range Combined Query Processing for Spatial Data

C.R. Sakthivel, P. Kanchana


Nearest Neighbor queries and All Nearest Neighbor (ANN) operation is a commonly used primitive for analyzing large multi-dimensional datasets, ANN is very expensive. The traditional index-based methods use a pruning metric called MAXMAXDIST and a new ANN pruning metric called NXNDIST, it reduces the computation time. The existing system stores the bucket quad tree index structure, called  MBRQT. It is using extensive experimental evaluation to show that MBRQT index can significantly speed up the computation and efficiently answer the more general All-k-Nearest- Neighbor (AkNN) queries. Top-k spatial preference query retrieves the k best  data objects in road network with highest scores. The score of an object is defined by the quality of features in its spatial neighborhood.

 The wide range of location-based applications that rely on spatial preference queries. Range query are used to find the accurate results from the spatial location. The essential idea is to precompute some accurate information in top K queries. To propose a novel technique to speed up the performance of  top-k spatial preference queries with nearest neighbor query and range query. In proposed system,  determining a range query to evaluate a top-k query by exploiting the nearest neighbor algorithm. Top k nearest range query algorithm is used to assign the range values for each nearest neighbor queries at given query. After assign the range values to the query, calculating all nearest neighbor using the nearest neighbor algorithm. Then calculating the nearest neighbor query with range values, the top k queries are selected for query result. The result of proposed new Top k nearest neighbor and range combined query processing is compared with existing nearest neighbor query techniques. Finally the performance of top k nearest range query algorithm process produce more efficient result and retrieval efficiency of the resulting scheme is high.


Spatial Data, Nearest Neighbor, Range Query, All-Nearest-Neighbor (ANN).

Full Text:



Man Lung Yiu, Hua Lu, Nikos Mamoulis, and Michail Vaitis, “ Ranking Spatial Data by Quality Preferences”, 2011.

M. L. Yiu, X. Dai, N. Mamoulis, and M. Vaitis, “Top-k Spatial Preference Queries,” in ICDE, 2007.

N. Bruno, L. Gravano, and A. Marian, “Evaluating Top-k Queries over Web-accessible Databases,” in ICDE, 2002.

A.K. Jain, M.N. Murty, and P.J, Flynn, Data Clustering: A review,1999.

S.C. Johnson, Hierarchical Clustering schemes, 1967.

R. Nock, M. Sebban, and D. Bernard. A simple locally adaptive nearest neighbor rule with application to pollution forecasting. Internal journal of pattern recognition and Artificial Intelligence, 2003.

T. Xia, D. Zhang, E. Kanoulas, and Y. Du, “On Computing Top-t Most Influential Spatial Sites,” in VLDB, 2005.

F.Korn and S. Muthukrishnan Influence sets based on reverse nearest neighbour queries , 2000.

R. Fagin, A. Lotem, and M. Naor, “Optimal Aggregation Algorithms for Middleware,” in PODS, 2001.

Y. Chen and J. M. Patel, “Efficient Evaluation of All-Nearest-Neighbor Queries,” in ICDE, 2007.

G. R. Hjaltason and H. Samet, “Distance Browsing in Spatial Databases,” TODS, vol. 24(2), pp. 265–318, 1999.

K. S. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft, “When is “nearest neighbor” meaningful?” in ICDT, 1999.

N. Mamoulis, M. L. Yiu, K. H. Cheng, and D. W. Cheung, “Efficient Top-k Aggregation of Ranked Inputs,” ACM TODS, vol. 32, no. 3, p. 19, 2007.

S. Hong, B. Moon, and S. Lee, “Efficient Execution of Range Top-k Queries in Aggregate R-Trees,” IEICE Transactions, vol. 88-D, no. 11, pp. 2544–2554, 2005.

Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” in SIGMOD, 1984.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.