Constrained All-k-Nearest-Neighbor Search

Abstract:

All-k-Nearest-Neighbor (AkNN) operation is common in several applications, such as geographical information systems, data analysis, computer architecture, and so forth. However, in some real applications, users may consider AkNN search constrained to a specified region. Motivated by this, we introduce the Constrained All-k-Nearest-Neighbor (CAkNN) query that for every data in query data set A, retrieves its k NNs in data set B and located in the restricted region. In addition, we develop two efficient algorithms to answer CAkNN search, which utilize a conventional data-partitioning indexing structure (e.g., R-tree) on datasets and employ techniques includes group and plane-sweep to improve the efficiency of the search. Extensive experiments using both real and synthetic datasets demonstrate the efficiency and scalability of the proposed algorithms.

• Periodical: Applied Mechanics and Materials (Volumes 239-240)
• Pages: 1387-1394
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.239-240.1387
• Online since: December 2012
• Authors: Shu Long Li, Lu Chen, Qing Liu, Jian Zhang
• Keywords: All-K-Nearest-Neighbor, Constrained Region, R-Tree

References

[1] C. B¨ohm and F. Krebs: The k-nearest neighbor join: Turbo charging the KDD process. KAIS Vol. 6(6) (2004), p.728–749

DOI: 10.1007/s10115-003-0122-9

[2] M.M. Breunig, H.P. Kriegel, R. Ng and J. Sander: LOF: Identifying density-based local outliers. In: Proc. SIGMOD (2000)

DOI: 10.1145/335191.335388

[3] A. Nanopoulos, Y. Theodoridis and Y. Manolopoulos: C2P: Clustering based on Closest Pairs, In: VLDB (2001)

[4] K. Nakano and S. Olariu: An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh, with Applications. IEEE TPDS Vol. 8(9) (1997), p.930–990

DOI: 10.1109/71.615443

[5] D.G. Lowe: Object recognition from local scale-invariant features. In: Inter. Conf. on Computer Vision (1999), p.1150–1157

[6] N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger: The R*-tree: An efficient and robust access method for points and rectangles. In: Proc of ACM SIGMOD'90, NY (1990), pp.322-331

DOI: 10.1145/93605.98741

[7] G.R. Hjaltason and H. Samet: Distance Browsing in Spatial Databases. ACM TODS Vol. 24(2) (1999), p.265–318

DOI: 10.1145/320248.320255

[8] H. Ferhatosmanoglu, I. Stanoi, D. Agrawal and A.E. Abbadi: Constrained nearest neighbor queries. In: Proc of the 7th Int Symp on Advances in Spatial and Temporal Databases, Berlin: Springer (2001), pp.257-278

DOI: 10.1007/3-540-47724-1_14

[9] J. Zhang, N. Mamoulis, D. Papadias and Y. Tao: All-Nearest-Neighbors Queries in Spatial Databases. In: SSDBM (2004), p.297–306

DOI: 10.1109/ssdm.2004.1311221

[10] C. Xia, H. Lu, B. Chin and J. Hu: GORDER: An Efficient Method for KNN Join Processing. In: VLDB (2004), p.756–767

DOI: 10.1016/b978-012088469-8/50067-x

[11] H.L. Chen and Y.I. Chang: All-nearest-neighbors finding based on the Hilbert curve. Expert Systems with Applications Vol. 38(6) (2011), p.7462–7475

DOI: 10.1016/j.eswa.2010.12.077

[12] Y. Chen and J. Patel: Efficient Evaluation of All-Nearest-Neighbor Queries. In: ICDE (2007), p.1056–1065

[13] T. Emrich, F. Graf, H.P. Kriegel, M. Schubert and M. Thoma: Optimizing All-Nearest-Neighbor Queries with Trigonometric Pruning. In: SSDBM (2010), p.501–518

DOI: 10.1007/978-3-642-13818-8_35

[14] T. Brinkhoff, H.P. Kriegel and B. Seeger: Efficient Processing of Spatial Joins Using R-trees. In: SIGMOD (1993)

DOI: 10.1145/170036.170075

[15] C. Yu, B. Cui, S. Wang and J. Su: Efficient index-based KNN join processing for highdimensional data. Information and Software Technology Vol. 49(4) (2007), p.332–344

DOI: 10.1016/j.infsof.2006.05.006

[16] H. Shin, B. Moon and S. Lee: Adaptive Multi-Stage Distance Join Processing. In: SIGMOD (2000)

DOI: 10.1145/335191.335428