{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:32:25Z","timestamp":1756312345590,"version":"3.37.3"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"9","funder":[{"name":"Shaanxi Science and Technology Association Youth Talent Support Program","award":["20230115"],"award-info":[{"award-number":["20230115"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61802311"],"award-info":[{"award-number":["61802311"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Key Research and Development Program of Shaanxi Province","award":["2019SF-272"],"award-info":[{"award-number":["2019SF-272"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,10,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The development of 3D scanning technology has enabled the acquisition of massive point cloud models with diverse structures and large scales, thereby presenting significant challenges in point cloud processing. Fast neighboring points search is one of the most common problems, which is frequently used in model reconstruction, classification, retrieval and feature visualization. Hash function is well known for its high-speed and accurate performance in searching high-dimensional data, which is also the core of the proposed 2L-LSH. Specifically, the 2L-LSH algorithm adopts a two-step hash function strategy, in which the popular step divides the bounding box of the point cloud model and the second step constructs a generalized table-based data structure. The proposed 2L-LSH offers a highly efficient and accurate solution for fast neighboring points search in large-scale 3D point cloud models, making it a promising technique for various applications in the field. The proposed algorithm is compared with the well-known methods including Kd-tree and Octree; the obtained results demonstrated that the proposed method outperforms Kd-tree and Octree in terms of speed, i.e. the time consumption of kNN search can be 51.111% and 94.159% lower than Kd-tree and Octree, respectively. And the RN search time can be 54.519% and 41.840% lower than Kd-tree and Octree, respectively.<\/jats:p>","DOI":"10.1093\/comjnl\/bxae047","type":"journal-article","created":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T14:48:16Z","timestamp":1727275696000},"page":"2809-2818","source":"Crossref","is-referenced-by-count":1,"title":["2L-LSH: A Locality-Sensitive Hash Function-Based Method For Rapid Point Cloud Indexing"],"prefix":"10.1093","volume":"67","author":[{"given":"Shurui","family":"Wang","sequence":"first","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]},{"given":"Yuhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]},{"given":"Ruizhe","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]},{"given":"Yaning","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]},{"given":"Yifei","family":"Xie","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]},{"given":"Xinyu","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Northwest University , Xi\u2019an,","place":["PR China"]}]}],"member":"286","published-online":{"date-parts":[[2024,9,25]]},"reference":[{"key":"2024101206304841500_ref1","doi-asserted-by":"crossref","first-page":"1907","DOI":"10.1109\/CVPR.2017.691","article-title":"Multi-view 3d object detection network for autonomous driving","volume-title":"2017 IEEE conference on computer vision and pattern recognition (CVPR)","author":"Chen","year":"2017"},{"key":"2024101206304841500_ref2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2300000035","article-title":"A review of point cloud registration algorithms for mobile robotics","volume":"4","author":"Pomerleau","year":"2015","journal-title":"Found. Trends Robotics"},{"key":"2024101206304841500_ref3","doi-asserted-by":"crossref","first-page":"2403","DOI":"10.1109\/TVCG.2018.2887262","article-title":"H-cnn: spatial hashing based cnn for 3d shape analysis","volume":"26","author":"Shao","year":"2018","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"2024101206304841500_ref4","doi-asserted-by":"crossref","first-page":"129029","DOI":"10.1109\/ACCESS.2019.2939684","article-title":"A novel simplification method for 3d geometric point cloud based on the importance of point","volume":"7","author":"Ji","year":"2019","journal-title":"IEEE Access"},{"key":"2024101206304841500_ref5","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1109\/TSIPN.2021.3100302","article-title":"Improving j-divergence of brain connectivity states by graph laplacian denoising","volume":"7","author":"Cattai","year":"2021","journal-title":"IEEE Trans. Signal Inf. Process. Networks"},{"key":"2024101206304841500_ref6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1111\/cgf.14715","article-title":"HDRNet: high-dimensional regression network for point cloud registration","volume":"42","author":"Gao","year":"2023","journal-title":"Comput. Graphics Forum"},{"key":"2024101206304841500_ref7","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1109\/TPAMI.2006.148","article-title":"Rapid object indexing using locality sensitive hashing and joint 3d-signature space estimation","volume":"28","author":"Matei","year":"2006","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2024101206304841500_ref8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.isprsjprs.2015.01.011","article-title":"Octree-based region growing for point cloud segmentation","volume":"104","author":"Vo","year":"2015","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"2024101206304841500_ref9","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1109\/HPCA47549.2020.00024","article-title":"Quicknn: memory and performance optimization of kd tree based nearest neighbor search for 3d point clouds","volume-title":"2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)","author":"Pinkham","year":"2020"},{"key":"2024101206304841500_ref10","doi-asserted-by":"crossref","first-page":"9409","DOI":"10.1016\/j.eswa.2008.12.062","article-title":"Information-theoretic hashing of 3d objects using spectral graph theory","volume":"36","author":"Tarmissi","year":"2009","journal-title":"Expert Syst. Appl."},{"key":"2024101206304841500_ref11","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.cageo.2017.06.013","article-title":"Lshsim: a locality sensitive hashing based method for multiple-point geostatistics","volume":"107","author":"Moura","year":"2017","journal-title":"Comput. Geosci."},{"key":"2024101206304841500_ref12","doi-asserted-by":"crossref","first-page":"643","DOI":"10.14778\/3377369.3377374","article-title":"Pm-lsh: a fast and accurate lsh framework for high-dimensional approximate nn search","volume":"13","author":"Zheng","year":"2020","journal-title":"Proc. VLDB Endow."},{"key":"2024101206304841500_ref13","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.1016\/j.sigpro.2009.05.024","article-title":"A secure and robust hash-based scheme for image authentication","volume":"90","author":"Ahmed","year":"2010","journal-title":"Signal Process."},{"key":"2024101206304841500_ref14","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1109\/TCSVT.2008.920739","article-title":"Robust video fingerprinting for content-based video identification","volume":"18","author":"Lee","year":"2008","journal-title":"IEEE Trans. Circuits Syst. Video Technol."},{"key":"2024101206304841500_ref15","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1016\/j.dsp.2012.04.015","article-title":"Robust 3d mesh model hashing based on feature object","volume":"22","author":"Lee","year":"2012","journal-title":"Digit. Signal Process."},{"key":"2024101206304841500_ref16","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/276698.276876","article-title":"Approximate nearest neighbors: towards removing the curse of dimensionality","volume-title":"Proceedings of the thirtieth annual ACM symposium on Theory of computing","author":"Indyk","year":"1998"},{"key":"2024101206304841500_ref17","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/2020408.2020578","article-title":"Fast locality-sensitive hashing","volume-title":"Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining","author":"Dasgupta","year":"2011"},{"key":"2024101206304841500_ref18","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-030-32047-8_1","article-title":"Fast locality-sensitive hashing frameworks for approximate near neighbor search","volume-title":"Similarity Search and Applications: 12th International Conference, SISAP 2019","author":"Christiani","year":"2019"},{"key":"2024101206304841500_ref19","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1109\/FOCS.2017.67","article-title":"Fast similarity sketching","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Dahlgaard","year":"2017"},{"key":"2024101206304841500_ref20","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","article-title":"Approximate nearest neighbor: towards removing the curse of dimensionality","volume":"8","author":"Indyk","year":"2012","journal-title":"Theory Comput."},{"key":"2024101206304841500_ref21","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1109\/ICDE.2012.40","article-title":"Bi-level locality sensitive hashing for k-nearest neighbor computation","volume-title":"2012 IEEE 28th International Conference on Data Engineering","author":"Pan","year":"2012"},{"key":"2024101206304841500_ref22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13677-016-0060-1","article-title":"Dynamic multidimensional index for large-scale cloud data","volume":"5","author":"He","year":"2016","journal-title":"J. Cloud Comput."},{"key":"2024101206304841500_ref23","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.imavis.2012.05.001","article-title":"Robust sparse bounding sphere for 3d face recognition","volume":"30","author":"Ming","year":"2012","journal-title":"Image Vision Comput."},{"key":"2024101206304841500_ref24","doi-asserted-by":"crossref","first-page":"29538","DOI":"10.1109\/ACCESS.2020.2972317","article-title":"Intersection detection algorithm based on hybrid bounding box for geological modeling with faults","volume":"8","author":"Wang","year":"2020","journal-title":"IEEE Access"},{"key":"2024101206304841500_ref25","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1080\/07468342.1996.11973744","article-title":"A singularly valuable decomposition: the svd of a matrix","volume":"27","author":"Kalman","year":"1996","journal-title":"The college mathematics journal"},{"key":"2024101206304841500_ref26","doi-asserted-by":"crossref","first-page":"3625","DOI":"10.1109\/ICRA.2015.7139702","article-title":"Efficient radius neighbor search in three-dimensional point clouds","volume-title":"2015 IEEE International Conference on Robotics and Automation (ICRA)","author":"Behley","year":"2015"},{"key":"2024101206304841500_ref27","first-page":"1912","article-title":"3d shapenets: A deep representation for volumetric shapes","volume-title":"Proceedings of the IEEE conference on computer vision and pattern recognition","author":"Wu","year":"2015"},{"key":"2024101206304841500_ref28","first-page":"9601","article-title":"Abc: A big cad model dataset for geometric deep learning","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition","author":"Koch","year":"2019"},{"key":"2024101206304841500_ref29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cageo.2011.05.005","article-title":"Development of a hashing-based data structure for the fast retrieval of 3d terrestrial laser scanned data","volume":"39","author":"Han","year":"2012","journal-title":"Comput. Geosci."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/9\/2809\/59719722\/bxae047.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/9\/2809\/59719722\/bxae047.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,12]],"date-time":"2024-10-12T06:31:26Z","timestamp":1728714686000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/9\/2809\/7774503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2024,9,25]]},"published-print":{"date-parts":[[2024,10,9]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxae047","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2024,9]]},"published":{"date-parts":[[2024,9]]}}}