{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:49Z","timestamp":1750220509520,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,12,8]],"date-time":"2020-12-08T00:00:00Z","timestamp":1607385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation for Post-Doctoral Scientists of China under Grant","award":["2018M643307"],"award-info":[{"award-number":["2018M643307"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61902438"],"award-info":[{"award-number":["61902438"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100021171","name":"Guangdong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["2019B1515130001"],"award-info":[{"award-number":["2019B1515130001"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Guangdong Province under Grant","award":["2019A1515011704"],"award-info":[{"award-number":["2019A1515011704"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            With the emergence and growing popularity of and location-based service (LBS) technologies, the continuous\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor (CO\n            <jats:italic>k<\/jats:italic>\n            NN) query in obstructed space is becoming a very important service. In this article, we study the CO\n            <jats:italic>k<\/jats:italic>\n            NN in obstructed space, which retrieves\n            <jats:italic>k<\/jats:italic>\n            <jats:italic>obstructed nearest neighbors (ONNs)<\/jats:italic>\n            for every point on a query segment\n            <jats:italic>q\u0304<\/jats:italic>\n            . The state-of-the-art approach, called &lt;monospace&gt;Euclidean based CONN (E-CONN)&lt;\/monospace&gt;, exploits an R-tree to traverse the dataset\n            <jats:italic>P<\/jats:italic>\n            in ascending order of their Euclidean distances to\n            <jats:italic>q\u0304<\/jats:italic>\n            . Taking a different point of view, in this article, we explore the idea of Voronoi diagram to define the notion of\n            <jats:italic>obstructed Voronoi diagram (OVD)<\/jats:italic>\n            . The Voronoi cells with obstacles are divided into\n            <jats:italic>visible<\/jats:italic>\n            and\n            <jats:italic>invisible regions<\/jats:italic>\n            for quickly answering nearest neighbor queries. To facilitate efficient retrieval of Voronoi cells and processing of continuous nearest neighbor (CONN) queries, we propose a new grid-based index, called\n            <jats:italic>Voronoi diagram with Obstacles in Grid (VO-Grid)<\/jats:italic>\n            , which indexes Voronoi cells and associated obstacle information with a grid file. Based on VO-Grid, we propose an efficient algorithm, called &lt;monospace&gt;CONN with VO-Grid Acceleration (CONN-VOA)&lt;\/monospace&gt;, to accelerate the CONN query processing. Moreover, we extend &lt;monospace&gt;CONN-VOA&lt;\/monospace&gt; to the CO\n            <jats:italic>k<\/jats:italic>\n            NN query, which also explores effective filtering and early termination for reducing redundant access of data objects. A comprehensive performance evaluation using both real and synthetic datasets is conducted to validate the proposed ideas and demonstrate the efficiency of our algorithms. The experimental results show that the &lt;monospace&gt;CONN-VOA&lt;\/monospace&gt; algorithm substantially outperforms &lt;monospace&gt;E-CONN&lt;\/monospace&gt; algorithm.\n          <\/jats:p>","DOI":"10.1145\/3425955","type":"journal-article","created":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:44:45Z","timestamp":1607553885000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Processing Continuous\n            <i>k<\/i>\n            Nearest Neighbor Queries in Obstructed Space with Voronoi Diagrams"],"prefix":"10.1145","volume":"7","author":[{"given":"Huaijie","family":"Zhu","sequence":"first","affiliation":[{"name":"Sun Yat-Sen University and Northeastern University, China"}]},{"given":"Xiaochun","family":"Yang","sequence":"additional","affiliation":[{"name":"The Department of Computer Science at Northeastern University, China"}]},{"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"The Department of Computer Science at Northeastern University, China"}]},{"given":"Wang-Chien","family":"Lee","sequence":"additional","affiliation":[{"name":"The Computer Science and Engineering, Penn State University"}]},{"given":"Jian","family":"Yin","sequence":"additional","affiliation":[{"name":"Sun Yat-Sen University, China"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"The Department of Computer Science, Hong Kong Baptist University, China"}]}],"member":"320","published-online":{"date-parts":[[2020,12,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Retrieved from http:\/\/www.chorochronos.org.  [n.d.]. Retrieved from http:\/\/www.chorochronos.org."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"N. Beckmann H.-P. Kriegel R. Schneider and B. Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. ACM SIGMOD (1990) 322--331.  N. Beckmann H.-P. Kriegel R. Schneider and B. Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. ACM SIGMOD (1990) 322--331.","DOI":"10.1145\/93605.98741"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009474"},{"key":"e_1_2_1_4_1","volume-title":"International Conference on Very Large Data Bases","author":"Cho H.-J.","year":"2005","unstructured":"H.-J. Cho and C.-W. Chung . 2005 . An efficient and scalable approach to CNN queries in a road network . International Conference on Very Large Data Bases (2005), 865--876. H.-J. Cho and C.-W. Chung. 2005. An efficient and scalable approach to CNN queries in a road network. International Conference on Very Large Data Bases (2005), 865--876."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_6_1","unstructured":"J. Feng and T. Watanabe. 2002. A fast method for continuous nearest target objects query on road network. VSMM (2002) 182--191.  J. Feng and T. Watanabe. 2002. A fast method for continuous nearest target objects query on road network. VSMM (2002) 182--191."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559906"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966387"},{"key":"e_1_2_1_10_1","volume-title":"IEEE International Conference on Data Engineering","author":"Gao Y.","year":"2009","unstructured":"Y. Gao , B. Zheng , G. Chen , W.-C. Lee , Ken C. K. Lee , and Q. Li . 2009. Visible reverse nearest neighbor queries . IEEE International Conference on Data Engineering ( 2009 ), 1203--1206. Y. Gao, B. Zheng, G. Chen, W.-C. Lee, Ken C. K. Lee, and Q. Li. 2009. Visible reverse nearest neighbor queries. IEEE International Conference on Data Engineering (2009), 1203--1206."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516378"},{"key":"e_1_2_1_12_1","first-page":"1569","article-title":"An efficient method for k nearest neighbor searching in obstructed spatial databases","volume":"30","author":"Gu Yu","year":"2014","unstructured":"Yu Gu , Ge Yu , and Xiaonan Yu . 2014 . An efficient method for k nearest neighbor searching in obstructed spatial databases . Journal of Information Science and Engineering 30 (2014), 1569 -- 1583 . Yu Gu, Ge Yu, and Xiaonan Yu. 2014. An efficient method for k nearest neighbor searching in obstructed spatial databases. Journal of Information Science and Engineering 30 (2014), 1569--1583.","journal-title":"Journal of Information Science and Engineering"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/NSYSS2.2017.8267783"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066212"},{"key":"e_1_2_1_15_1","volume-title":"International Conference on Very Large Data Bases","author":"Kolahdouzan M.","year":"2004","unstructured":"M. Kolahdouzan and C. Shahabi . 2004. Voronoi-based k nearest neighbor search for spatial network databases . International Conference on Very Large Data Bases ( 2004 ), 840--851. M. Kolahdouzan and C. Shahabi. 2004. Voronoi-based k nearest neighbor search for spatial network databases. International Conference on Very Large Data Bases (2004), 840--851."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-005-4575-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1109\/TC.1982.1676031","article-title":"On k-nearest neighbor Voronoi diagrams in the plane","volume":"100","author":"Lee Der-Tsai","year":"1982","unstructured":"Der-Tsai Lee . 1982 . On k-nearest neighbor Voronoi diagrams in the plane . IEEE Transactions on Computers 100 , 6 (1982), 478 -- 487 . Der-Tsai Lee. 1982. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Transactions on Computers 100, 6 (1982), 478--487.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735473"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.03.008"},{"volume-title":"International Conference on Intelligent Robots and Systems. IEEE, 2953--2958","author":"Luo Ren C.","key":"e_1_2_1_20_1","unstructured":"Ren C. Luo , Chung T. Liao , Kuo Lan Su , and Kuei C. Lin . 2005. Automatic docking and recharging system for autonomous security robot . International Conference on Intelligent Robots and Systems. IEEE, 2953--2958 . Ren C. Luo, Chung T. Liao, Kuo Lan Su, and Kuei C. Lin. 2005. Automatic docking and recharging system for autonomous security robot. International Conference on Intelligent Robots and Systems. IEEE, 2953--2958."},{"volume-title":"2010 5th International Conference on Systems and Networks Communications. 243--248","author":"Lv W.","key":"e_1_2_1_21_1","unstructured":"W. Lv , F. Wang , T. Zhu , and Y. Zhang . 2010. Continuous nearest neighbor queries in weight changing road networks . 2010 5th International Conference on Systems and Networks Communications. 243--248 . W. Lv, F. Wang, T. Zhu, and Y. Zhang. 2010. Continuous nearest neighbor queries in weight changing road networks. 2010 5th International Conference on Systems and Networks Communications. 243--248."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2019.2911950"},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Very Large Data Bases","author":"Mouratidis K.","year":"2006","unstructured":"K. Mouratidis , M. Yiu , D. Papadias , and N. Mamoulis . 2006. Continuous nearest neighbor monitoring in road networks . International Conference on Very Large Data Bases ( 2006 ), 43--54. K. Mouratidis, M. Yiu, D. Papadias, and N. Mamoulis. 2006. Continuous nearest neighbor monitoring in road networks. International Conference on Very Large Data Bases (2006), 43--54."},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Very Large Data Bases","author":"Nutanong S.","year":"2008","unstructured":"S. Nutanong , E. Tanin , and L. Kulik . 2008. The v*diagram: A query dependent approach to moving knn queries . International Conference on Very Large Data Bases ( 2008 ), 1095--1106. S. Nutanong, E. Tanin, and L. Kulik. 2008. The v*diagram: A query dependent approach to moving knn queries. International Conference on Very Large Data Bases (2008), 1095--1106."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"S. Nutanong E. Tanin and R. Zhang. 2007. Visible nearest neighbor queries. DASFAA (2007) 876--883.  S. Nutanong E. Tanin and R. Zhang. 2007. Visible nearest neighbor queries. DASFAA (2007) 876--883.","DOI":"10.1007\/978-3-540-71703-4_73"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0163-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"A. Okabe B. Boots K. Sugihara and S. N. Chiu. 2000. Spatial Tessellations Concepts and Applications of Voronoi Diagrams. John Wiley and Sons Ltd. 2nd edition.  A. Okabe B. Boots K. Sugihara and S. N. Chiu. 2000. Spatial Tessellations Concepts and Applications of Voronoi Diagrams. John Wiley and Sons Ltd. 2nd edition.","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_1_28_1","volume-title":"10th International Conference on Geographic Information Science (GIScience","author":"Saha Rudra Ranajee","year":"2018","unstructured":"Rudra Ranajee Saha , Tanzima Hashem , Tasmia Shahriar , and Lars Kulik . 2018 . Continuous obstructed detour queries . 10th International Conference on Geographic Information Science (GIScience 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Rudra Ranajee Saha, Tanzima Hashem, Tasmia Shahriar, and Lars Kulik. 2018. Continuous obstructed detour queries. 10th International Conference on Geographic Information Science (GIScience 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"M. Sharifzadeh and C. Shahabi. 2010. VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries. VLDB (2010) 1231--1242.  M. Sharifzadeh and C. Shahabi. 2010. VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries. VLDB (2010) 1231--1242.","DOI":"10.14778\/1920841.1920994"},{"key":"e_1_2_1_30_1","volume-title":"IEEE International Conference on Robotics and Automation","volume":"1","author":"Silverman Milo C.","unstructured":"Milo C. Silverman , Dan Nies , Boyoon Jung , and Gaurav S. Sukhatme . 2002. Staying alive: A docking station for autonomous robot recharging . IEEE International Conference on Robotics and Automation , Vol. 1 . IEEE, 1050--1055. Milo C. Silverman, Dan Nies, Boyoon Jung, and Gaurav S. Sukhatme. 2002. Staying alive: A docking station for autonomous robot recharging. IEEE International Conference on Robotics and Automation, Vol. 1. IEEE, 1050--1055."},{"key":"e_1_2_1_31_1","volume-title":"IEEE International Conference on Data Engineering","author":"Sistla P.","year":"1997","unstructured":"P. Sistla , O. Wolfson , S. Chamberlain , and S. Dao . 1997. Modeling and querying moving objects . IEEE International Conference on Data Engineering ( 1997 ), 422--432. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. 1997. Modeling and querying moving objects. IEEE International Conference on Data Engineering (1997), 422--432."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Z. Song and N. Roussopoulos. 2001. K-nearest neighbor search for moving query point. SSTD (2001) 79--96.  Z. Song and N. Roussopoulos. 2001. K-nearest neighbor search for moving query point. SSTD (2001) 79--96.","DOI":"10.1007\/3-540-47724-1_5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666484"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.04.003"},{"key":"e_1_2_1_35_1","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Tao Y.","year":"2002","unstructured":"Y. Tao and D. Papadias . 2002. Time parameterized queries in spatio-temporal databases . ACM SIGMOD International Conference on Management of Data ( 2002 ), 334--345. Y. Tao and D. Papadias. 2002. Time parameterized queries in spatio-temporal databases. ACM SIGMOD International Conference on Management of Data (2002), 334--345."},{"key":"e_1_2_1_36_1","volume-title":"Continuous nearest neighbor search. VLDB","author":"Tao Yufei","year":"2002","unstructured":"Yufei Tao , Dimitris Papadias , and Qiongmao Shen . 2002. Continuous nearest neighbor search. VLDB ( 2002 ), 287--298. Yufei Tao, Dimitris Papadias, and Qiongmao Shen. 2002. Continuous nearest neighbor search. VLDB (2002), 287--298."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213005002053"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/WICOM.2007.753"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/TC.1987.1676904","article-title":"Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles","volume":"100","author":"\u00a0al Ying-Fung","year":"1987","unstructured":"Ying-Fung Wu et \u00a0al . 1987 . Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles . IEEE Transactions on Computers 100 , 3 (1987), 321 -- 331 . Ying-Fung Wu et\u00a0al. 1987. Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computers 100, 3 (1987), 321--331.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"C. Xia D. Hsu and H. Tung. 2004. A fast filter for obstructed nearest neighbor queries. BNCOD (November 2004) 203--215.  C. Xia D. Hsu and H. Tung. 2004. A fast filter for obstructed nearest neighbor queries. BNCOD (November 2004) 203--215.","DOI":"10.1007\/978-3-540-27811-5_19"},{"key":"e_1_2_1_41_1","volume-title":"International Conference on Extending Database Technology","author":"Zhang J.","year":"2004","unstructured":"J. Zhang , D. Papadias , K. Mouratidis , and M. Zhu . 2004. Spatial queries in the presence of obstacles . International Conference on Extending Database Technology ( 2004 ), 366--384. J. Zhang, D. Papadias, K. Mouratidis, and M. Zhu. 2004. Spatial queries in the presence of obstacles. International Conference on Extending Database Technology (2004), 366--384."},{"key":"e_1_2_1_42_1","volume-title":"Faster and more robust mesh-based algorithms for obstacle k-nearest neighbour. arXiv preprint arXiv:1808.04043","author":"Zhao Shizhe","year":"2018","unstructured":"Shizhe Zhao , Daniel D. Harabor , and David Taniar . 2018. Faster and more robust mesh-based algorithms for obstacle k-nearest neighbour. arXiv preprint arXiv:1808.04043 ( 2018 ). Shizhe Zhao, Daniel D. Harabor, and David Taniar. 2018. Faster and more robust mesh-based algorithms for obstacle k-nearest neighbour. arXiv preprint arXiv:1808.04043 (2018)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915234"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2779487"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3425955","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3425955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:24Z","timestamp":1750195464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3425955"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,8]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3425955"],"URL":"https:\/\/doi.org\/10.1145\/3425955","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2020,12,8]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}