{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T22:37:16Z","timestamp":1792190236177,"version":"4.4.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["Y110278"],"award-info":[{"award-number":["Y110278"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NBNSF","award":["2010A610113"],"award-info":[{"award-number":["2010A610113"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61003049"],"award-info":[{"award-number":["61003049"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Central Universities","award":["2010QNA5051"],"award-info":[{"award-number":["2010QNA5051"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>\n            Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. Given a data set\n            <jats:italic>P<\/jats:italic>\n            , an obstacle set\n            <jats:italic>O<\/jats:italic>\n            , and a query line segment\n            <jats:italic>q<\/jats:italic>\n            , in a two-dimensional space, a CONN query retrieves the nearest neighbor\n            <jats:italic>p<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            of each point\n            <jats:italic>p\u2032<\/jats:italic>\n            on\n            <jats:italic>q<\/jats:italic>\n            according to the obstructed distance, the shortest path between\n            <jats:italic>p<\/jats:italic>\n            and\n            <jats:italic>p<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            without crossing any obstacle in\n            <jats:italic>O<\/jats:italic>\n            . We formalize CONN search, analyze its unique properties, and develop algorithms for exact CONN query-processing assuming that both\n            <jats:italic>P<\/jats:italic>\n            and\n            <jats:italic>O<\/jats:italic>\n            are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor (CO\n            <jats:italic>k<\/jats:italic>\n            NN) search which, based on obstructed distances, finds the\n            <jats:italic>k<\/jats:italic>\n            (\u2265 1) nearest neighbors (NNs) to every point along\n            <jats:italic>q<\/jats:italic>\n            ; and (2) trajectory obstructed\n            <jats:italic>k<\/jats:italic>\n            nearest-neighbor (TO\n            <jats:italic>k<\/jats:italic>\n            NN) search, which, according to obstructed distances, returns the\n            <jats:italic>k<\/jats:italic>\n            NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate CO\n            <jats:italic>k<\/jats:italic>\n            NN (ACO\n            <jats:italic>k<\/jats:italic>\n            NN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.\n          <\/jats:p>","DOI":"10.1145\/1966385.1966387","type":"journal-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:51:38Z","timestamp":1307361098000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Continuous nearest-neighbor search in the presence of obstacles"],"prefix":"10.1145","volume":"36","author":[{"given":"Yunjun","family":"Gao","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gang","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chun","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qing","family":"Li","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335432"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290596"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the International Conference on Very large Data Bases (VLDB). 865--876","author":"Cho H.-J."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining (TSDM). 133--146","author":"Estivill-Castro V."},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the International Conference on Virtual Systems and Multimedia (VSMM). 182--191","author":"Feng J."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559906"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.113"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516378"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.6"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the ACM Workshop on Advances in Geographic Information Systems (GIS). 136--143","author":"Henrich A.","year":"1994"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2009.01.001"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the International Conference on Very large Data Bases (VLDB). 512--523","author":"Iwerks G. S."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-005-4575-8"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335415"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/APWeb.2010.28"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/998688.1007113"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the International Conference on Database and Expert Systems Applications (DEXA). 264--276","author":"Liu F."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066230"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190604"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.172"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Conference on Very large Data Bases (VLDB). 43--54","author":"Mouratidis K."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 876--883","author":"Nutanong S."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453973"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0163-0"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 1024--1027","author":"Park S. H."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the International Conference on Very large Data Bases (VLDB). 507--518","author":"Sellis T."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). 422--432","author":"Sistla P."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). 79--96","author":"Song Z."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564730"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0168-2"},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the International Conference on Very large Data Bases (VLDB). 287--298","author":"Tao Y."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130333"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). 359--367","author":"Tung A. K. H."},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 405--419","author":"Tung A. K. H."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213005002053"},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery (PKDD). 446--458","author":"Wang X."},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). 1116--1125","author":"Wu W."},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the British National Conference on Databases (BNCOD). 203--215","author":"Xia C."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.128"},{"key":"e_1_2_2_49_1","volume-title":"Proceedings of the International Conference on Web-Age Information Management (WAIM). 333--344","author":"Xu H."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.92"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the International Database Engineering and Applications Symposium (IDEAS). 214--223","author":"Zaiane O. R."},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 366--384","author":"Zhang J."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872812"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966387","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1966385.1966387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:25Z","timestamp":1750245745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1966385.1966387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1966385.1966387"],"URL":"https:\/\/doi.org\/10.1145\/1966385.1966387","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}