Open Access Open Access  Restricted Access Subscription or Fee Access

An Optimized Spatial Query Method for Nearest Neighbor-Candidate Identification in Time Variant Probabilistic Spatial Data

Md. Shafakhatullah Khan, A. Chandrashekar Sharma, Shaik Shah Nawaz


Spatial data is represented with X and Y coordinates (or latitude and longitude) which might be a fixed point in a map or the position of an object in a map. In this paper we are using vector model for representing spatial data. Probabilistic spatial data is one where the coordinates or the position of an object may be one of „n‟ different locations. If there are „m‟ such objects then finding the probabilistic nearest neighborhood of such objects is known as spatial query. Finding the nearest neighbor (NN) of probabilistic spatial data is quite challenging because from time to time the objects will not be in the same position. In this paper we propose a fast and efficient method for finding the NN with linear optimization of position vectors. The method first finds the probable objects whose any of the position is nearer to the query object and then optimized amongst obtained result set to find the precise NN-Candidate. Result shows significant closeness of the query object with the obtained NN-candidate.


Nearest Neighbor, Probabilistic Spatial Data, Linear Optimization.

Full Text:



Sze Man yuen, yufei Tao, Xiaokui Xiao, Jian Pei, Senior member, IEEE, and Donghui Zhang, “Superseding Nearest Neighbor Search on Uncertain Spatial Database” IEEE Transaction on Knowledge and Data Engineering, VOL. 22, NO. 7, pp 1041-1055, July 2010.

N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger, “The R*- Tree: An Efficient and Robust Access Method for Points and Rectangles,” Proc. ACM SIGMOD, pp. 322-331, 1990.

R. Cheng, J. Chen, M.F. Mokbel, and C.-Y. Chow, “Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data,” Proc. Int‟l Conf. Data Eng. (ICDE), pp. 973-982, 2008.

R. Cheng, D.V. Kalashnikov, and S. Prabhakar, “Querying Imprecise Data in Moving Object Environments,” IEEE TransKnowledge and Data Eng., vol. 16, no. 9, pp. 1112-1127, Sept. 2004.

X. Dai, M.L. Yiu, N. Mamoulis, Y. Tao, and M. Vaitis, “Probabilistic Spatial Queries on Existentially Uncertain Data,” Proc. Symp. Advances in Spatial and Temporal Databases (SSTD), pp. 400-417, 2005.

G.R. Hjaltason and H. Samet, “Distance Browsing in Spatial Databases,” ACM Trans. Database Systems, vol. 24, no. 2, pp. 265-318, 1999.

M. Hua, J. Pei, W. Zhang, and X. Lin, “Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach,” Proc. ACM SIGMOD, pp. 673-686, 2008.

H.V. Jagadish, B.C. Ooi, K.-L. Tan, C. Yu, and R. Zhang, “idistance: An Adaptive bþ-Tree Based Indexing Method for Nearest Neighbor Search,” ACM Trans. Database Systems, vol. 30, no. 2, pp. 364-397, 2005.

F. Korn and S. Muthukrishnan, “Influence Sets Based on Reverse Nearest Neighbor Queries,” Proc. ACM SIGMOD, pp. 201-212, 2000.

H.-P. Kriegel, P. Kunath, and M. Renz, “Probabilistic Nearest- Neighbor Query on Uncertain Objects,” Proc. Database Systems for Advanced Applications (DASFAA), pp. 337-348, 2007.

D. Papadias, Y. Tao, K. Mouratidis, and C.K. Hui, “Aggregate Nearest Neighbor Queries in Spatial Databases,” ACM Trans. Database Systems, vol. 30, no. 2, pp. 529-576, 2005.

N. Roussopoulos, S. Kelley, and F. Vincent, “Nearest Neighbor Queries,” Proc. ACM SIGMOD, pp. 71-79, 1995.

T. Seidl and H.-P. Kriegel, “Optimal Multi-Step k-Nearest Neighbor Search,” Proc. ACM SIGMOD, vol. 27, no. 2, pp. 154- 165, 1998.

M.A. Soliman, I.F. Ilyas, and K.C.-C. Chang, “Top-k Query Processing in Uncertain Databases,” Proc. Int‟l Conf. Data Eng. (ICDE), pp. 896-905, 2007.

Y. Tao, D. Papadias, and Q. Shen, “Continuous Nearest Neighbor Search,” Proc. Very Large Data Bases (VLDB), pp. 287-298, 2002.

R. Weber, H.-J. Schek, and S. Blott, “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces,” Proc. Very Large Data Bases (VLDB), pp. 194-205, 1998.

K. Yi, F. Li, G. Kollios, and D. Srivastava, “Efficient Processing of Top-k Queries in Uncertain Databases,” Proc. Int‟l Conf. Data Eng. (ICDE), pp 1406-1408, 2008.

G. Beskales, M.A. Soliman, and I.F. Ilyas, “Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases,” Proc,Very Large Data Bases (VLDB), vol. 1, no. 1, pp. 326-339, 2008.

Man Lung Yiu, Nikos Mamoulis, Xiangyuan Dai, Yufei Tao, and Michail Vaitis “Efficient Evaluation of Probabilistic Advanced Spatial Queries on Existentially Uncertain Data” IEEE Transactions on Knowledge and Data Engineering, Vol. 21, No.1, January 2009.


  • There are currently no refbacks.

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