article

Fast k-Nearest Neighbor Searching in Static Objects

Author:

Jae Moon LeeAuthors Info & Claims

Wireless Personal Communications: An International Journal, Volume 93, Issue 1

Pages 147 - 160

https://doi.org/10.1007/s11277-016-3524-1

Published: 01 March 2017 Publication History

Abstract

The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static objects are known in advance and not changed, most of existing solutions build a kd-tree as a preprocessing and search the k- nearest neighbors by using it. We propose a completely different preprocessing with kd-trees. The core idea of this paper is to build in advance the k-nearest neighbors of each static object as a preprocessing. If a querying point q is given, the nearest object p of q is firstly searched and then the k-nearest neighbors of q are found by using the k-nearest neighbors of p. It is to use the feature that two objects may share many neighbors if they are spatially close to each other. In order to measure the performance of the proposed algorithm, we have a number of experiments. The results of experiments showed that the proposed algorithm is 2---3 times quicker than the method using kd-tree in the Point Cloud Library(PCL).

References

[1]

Lee, K. W., Choi, D. W., & Chung, C. W. (2014). DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases. Journal of Intelligent Information Systems,43(2), 349---377.

Digital Library

[2]

Califano, A., & Mohan, R. (1994). Multidimensional index for recognizing visual shapes. IEEE Transaction on Pattern Analysis and Machine Intelligence,16, 373---392.

Digital Library

[3]

Lampert, C. H., Blaschko, M. M. & Hofmann, T. (2008). Beyond sliding windows: Object localization by efficient subwindow search. In IEEE conference on computer vision and pattern recognition (CVPR), pp. 1---8.

[4]

Gotoh, Y. (2014). A simple routing method for reverse k-nearest neighbor queries in spatial networks. In 17th international conference on network-based information systems (NBiS), pp. 615---620.

Digital Library

[5]

Zhang, H., Reardon, C., & Parker, L. E. (2013). Real-time multiple human perception with color-depth cameras on a mobile robot. IEEE Transactions on Cybernetics B (TMSC-B),43(4), 1429---1441.

[6]

Caraway, N. M., McCreight, J. L., & Rajagopalan, B. (2014). Multisite stochastic weather generation using cluster analysis and k-nearest neighbor time series resampling. Journal of Hydrology,508(16), 197---213.

[7]

Steed, T. C., Treiber, J. M., Patel, K. S., Taich, Z., White, N. S., Treiber, M. L., et al. (2015). Iterative probabilistic voxel labeling: Automated segmentation for analysis of the cancer imaging archive glioblastoma images. American Society of Neuroradiology,36(4), 678---685.

[8]

Yue, J., Wang, Y., Li, Z., Zhang, Z., & Hou, J. (2014). A new image retrieval method based on k-nearest neighbor multistage and multiple features. Sensor Letters,12(3---5), 479---484.

[9]

Nguyen, Huy, Viennot, Simon, & Ikeda, Kokolo. (2015). Fast optimization of the pattern shapes in board games with simulated annealing. Advances in Intelligent Systems and Computing,326, 325---337.

[10]

Nakagawa, Y., Yamamoto, K., & Thawonmas, R. (2014). Online adjustment of the AI's strength in a fighting game using the k-nearest neighbor algorithm and a game simulator. In IEEE 3rd global conference on consumer electronics (GCCE), pp. 494---495.

[11]

Wan, Q., Li, Y., Li, C., & Pal, R. (2014). Gesture recognition for smart home applications using portable radar sensors. In 36th annual international conference of the IEEE engineering in medicine and biology society (EMBC), pp. 6414---6417.

[12]

Lee, Y., Wampler, K., Popović, J., & Popović, Z. (2014). Motion fields for interactive character locomotion. Communications of the ACM,57(6), 101---108.

Digital Library

[13]

Huang, Y. K., & He, Z Han. (2015). Processing continuous K-nearest skyline query with uncertainty in spatio-temporal databases. Journal of Intelligent Information Systems,45(2), 165---186.

Digital Library

[14]

Gu, Y., Yu, G., & Yu, X. (2014). An efficient method for k nearest neighbor searching in obstructed spatial databases. Journal of Information Science and Engineering,30, 1569---1583.

[15]

Zhong, R. et al. (2013). G-tree: An efficient index for knn search on road networks. In Proceedings of the 22nd ACM international conference on conference on information & knowledge management. ACM, pp. 39---48.

Digital Library

[16]

Yi, X., Paulet, R., Bertino, E., & Varadharajan, V. (2014). Practical k nearest neighbor queries with location privacy. In IEEE 30th international conference on data engineering (ICDE), pp. 640---651.

[17]

Qu, Y., Fang, J., & Zhang, S. (2012). Identifying neighbor and connectivity of wireless sensor networks with poisson point process. Wireless Personal Communications,64(4), 795---809.

Digital Library

[18]

Ranga, V., Dave, M., & Verma, A. K. (2013). Network partitioning recovery mechanisms in WSANs: A survey. Wireless Personal Communications,72(2), 857---917.

Digital Library

[19]

Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. ACM SIGMOD Rec,14(2), 47---57.

Digital Library

[20]

Rusu, R. B., & Cousins, S. (2011). 3D is here: Point cloud library (PCL). In IEEE international conference on robotics and automation (ICRA). Shanghai, China, pp. 1---4.

[21]

Wolfson, H. J., & Rigoutsos, I. (1997). Geometric hashing: An overview. IEEE Computational Science and Engineering,4, 10---21.

Digital Library

[22]

Yen, S. H., Shih, C. Y., Li, T. K., & Chang, H. W. (2010). Applying multiple KD-trees in high dimensional nearest neighbor searching. International Journal of Circuits, Systems and Signal Processing,4(4), 153---160.

[23]

Yu, X., Pu, K. Q., & Koudas, N. (2005). Monitoring k-nearest neighbor queries over moving objects. In 21st international conference on data engineering, pp. 631---642.

Digital Library

[24]

Bentley, J. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM,18, 509---517.

Digital Library

[25]

Boubou, S., & Suzuki, E. (2015). Classifying actions based on histogram of oriented velocity vectors. Journal of Intelligent Information Systems,44(1), 49---65.

Digital Library

[26]

Ku, W. S., Chen, Y., & Zimmermann, R. (2009). Privacy protected spatial query processing for advanced location based services. Wireless Personal Communications,51(1), 53---65.

[27]

Nguyen, V. G., Do, T. X., & Kim, Y. H. (2016). SDN and virtualization-based LTE mobile network architectures: A comprehensive survey. Wireless Personal Communications,86, 1401---1438.

Digital Library

[28]

Mouratidis, K., Hadjieleftheriou, M., & Papadias, D. (2005). Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In Proceedings of ACM SIGMOD international conference on management of data, pp. 634---645.

Digital Library

[29]

Ma, J., Song, W. G., Zhang, J., Lo, S. M., & Liao, G. X. (2010). k-nearest-neighbor interaction induced self-organized pedestrian counter flow. Physica A,389, 2101---2117.

[30]

Lee, J. M. (2010). An efficient algorithm to find k-nearest neighbors in flocking behavior. Information Processing Letters,110, 576---579.

Digital Library

[31]

Reynolds, C. W. (1987). Flocks, herds, and schools: A distributed behavioral model. SIGGRAPH,21(4), 25---34.

Digital Library

[32]

Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Transaction on Automatic Control,51(3), 401---420.

Cited By

Zhu RLi CZhang AZong CXia X(2023)Continuous Group Nearest Group Search over Streaming DataWeb and Big Data10.1007/978-981-97-2387-4_6(80-95)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-2387-4_6
Wang SPeng SHe J(2021)Simplification algorithm of denture point cloud based on feature preservingJournal of Computational Methods in Sciences and Engineering10.3233/JCM-21554121:6(2035-2048)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JCM-215541
Wang YLee KLee I(2018)DNA-chart visual tool for topological higher order information from spatio-temporal trajectory datasetExpert Systems with Applications: An International Journal10.1016/j.eswa.2018.04.036108:C(28-35)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1016/j.eswa.2018.04.036
Show More Cited By

Recommendations

K-Nearest Neighbor Finding Using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...
Evaluating continuous K-nearest neighbor query on moving objects with uncertainty

Continuous K-nearest neighbor (CKNN) query is one of the most fundamental queries in the field of spatio-temporal databases. Given a time interval [t"s,t"e], a CKNN query is to retrieve the K-nearest neighbors (KNNs) of a moving user at each time ...
Nearest neighbor searching in high dimensions using multiple KD-trees
ISCGAV'10: Proceedings of the 10th WSEAS international conference on Signal processing, computational geometry and artificial vision

Feature matching plays a key role in many image processing applications. The matching efficacy is crucially determined by the description of features. To be robust and distinctive, feature vectors usually have high dimensions. Thus accurately finding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Wireless Personal Communications: An International Journal

Wireless Personal Communications: An International Journal Volume 93, Issue 1

March 2017

274 pages

ISSN:0929-6212

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 March 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu RLi CZhang AZong CXia X(2023)Continuous Group Nearest Group Search over Streaming DataWeb and Big Data10.1007/978-981-97-2387-4_6(80-95)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-2387-4_6
Wang SPeng SHe J(2021)Simplification algorithm of denture point cloud based on feature preservingJournal of Computational Methods in Sciences and Engineering10.3233/JCM-21554121:6(2035-2048)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JCM-215541
Wang YLee KLee I(2018)DNA-chart visual tool for topological higher order information from spatio-temporal trajectory datasetExpert Systems with Applications: An International Journal10.1016/j.eswa.2018.04.036108:C(28-35)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1016/j.eswa.2018.04.036
Henshall GTeahan WCenydd L(2018)Virtual reality's effect on parameter optimisation for crowd-sourced procedural animationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1501-234:9(1255-1268)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s00371-018-1501-2
Rhyu SOh S(2017)ICT-Based Wireless Personal ComputingWireless Personal Communications: An International Journal10.1007/s11277-017-3955-393:1(1-5)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11277-017-3955-3

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents