{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:12:23Z","timestamp":1771956743660,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"the National Key Research and Development Program of China","award":["2020YFB1707901"],"award-info":[{"award-number":["2020YFB1707901"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["Nos. U22A2025 62072088 62232007 61991404"],"award-info":[{"award-number":["Nos. U22A2025 62072088 62232007 61991404"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Natural Science Foundation of Liao Ning","award":["2022-MS-302 2022-MS-303 and 2022-BS-218"],"award-info":[{"award-number":["2022-MS-302 2022-MS-303 and 2022-BS-218"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>\n            k-closest pair (KCP for short) search is a fundamental problem in database research. Given a set of d-dimensional streaming data S, KCP search aims to retrieve k pairs with the shortest distances between them. While existing works have studied continuous 1-closest pair query (i.e., k=1) over dynamic data environments, which allow for object insertions\/deletions, they require high computational costs and cannot easily support KCP search with k&gt;1. This paper investigates the problem of KCP search over data stream, aiming to incrementally maintain as few pairs as possible to support KCP search with arbitrarily k. To achieve this, we introduce the concept of NNS (short for\n            <jats:underline>N<\/jats:underline>\n            earest\n            <jats:underline>N<\/jats:underline>\n            eighbour pair-\n            <jats:underline>S<\/jats:underline>\n            et), which consists of all the nearest neighbour pairs and allows us to support KCP search via only accessing O(k) objects. We further observe that in most cases, we only need to use a small portion of NNS to answer KCP search as typically k\u0142l n. Based on this observation, we propose TNNS (short for\n            <jats:underline>T<\/jats:underline>\n            hreshold-based\n            <jats:underline>NN<\/jats:underline>\n            pair\n            <jats:underline>S<\/jats:underline>\n            et), which contains a small number of high-quality NN pairs, and a partition named \u03c4-DLBP (short for \u03c4-\n            <jats:underline>D<\/jats:underline>\n            istance\n            <jats:underline>L<\/jats:underline>\n            ower-\n            <jats:underline>B<\/jats:underline>\n            ound based\n            <jats:underline>P<\/jats:underline>\n            artition) to organize objects, with \u03c4 being an integer significantly smaller than n. \u03c4-DLBP organizes objects using up to O(\u0142og n \/ \u03c4) partitions and is able to support the construction and update of TNNS efficiently.\n          <\/jats:p>","DOI":"10.1145\/3617326","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T22:28:39Z","timestamp":1699914519000},"page":"1-26","source":"Crossref","is-referenced-by-count":7,"title":["Closest Pairs Search Over Data Stream"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7033-8643","authenticated-orcid":false,"given":"Rui","family":"Zhu","sequence":"first","affiliation":[{"name":"Shenyang Aerospace University, Shenyang , China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2694-1023","authenticated-orcid":false,"given":"Bin","family":"Wang","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6184-4771","authenticated-orcid":false,"given":"Xiaochun","family":"Yang","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9792-9171","authenticated-orcid":false,"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50021-8"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976014.6"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.136"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009340"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794277718"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377181"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0383-4"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.351829"},{"key":"e_1_2_2_11_1","first-page":"331","volume-title":"VLDB","author":"Nanopoulos Alexandros","year":"2001","unstructured":"Alexandros Nanopoulos, Yannis Theodoridis, and Yannis Manolopoulos. C2 p: Clustering based on closest pairs. In VLDB 2001, September 11--14, 2001, Roma, Italy, pages 331--340. Morgan Kaufmann, 2001."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.47"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3118552"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435379"},{"key":"e_1_2_2_15_1","volume-title":"Continuous spatial query processing: A survey of safe region based techniques. ACM Comput. Surv., 51(3), may","author":"Qi Jianzhong","year":"2018","unstructured":"Jianzhong Qi, Rui Zhang, Christian S. Jensen, Kotagiri Ramamohanarao, and Jiayuan HE. Continuous spatial query processing: A survey of safe region based techniques. ACM Comput. Surv., 51(3), may 2018."},{"issue":"3","key":"e_1_2_2_16_1","first-page":"3059","article-title":"Secure your ride: Real-time matching success rate prediction for passenger-driver pairs","volume":"35","author":"Wang Yuandong","year":"2023","unstructured":"Yuandong Wang, Hongzhi Yin, Lian Wu, Tong Chen, and Chunyang Liu. Secure your ride: Real-time matching success rate prediction for passenger-driver pairs. IEEE Trans. Knowl. Data Eng., 35(3):3059--3071, 2023.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397245"},{"key":"e_1_2_2_18_1","first-page":"8","volume-title":"Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, BeyondMR@SIGMOD 2016","author":"Jeffrey","year":"2016","unstructured":"Jeffrey D. Ullman and Jonathan R. Ullman. Some pairs problems. In Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, BeyondMR@SIGMOD 2016, San Francisco, CA, USA, July 1, 2016, page 8. ACM, 2016."},{"key":"e_1_2_2_19_1","volume-title":"DASFAA 2021, Taipei, Taiwan, April 11--14, 2021, Proceedings, Part I","volume":"12681","author":"Wu Fangwei","year":"2021","unstructured":"Fangwei Wu, Xike Xie, and Jieming Shi. Top-k closest pair queries over spatial knowledge graph. In Database Systems for Advanced Applications - 26th International Conference, DASFAA 2021, Taipei, Taiwan, April 11--14, 2021, Proceedings, Part I, volume 12681 of Lecture Notes in Computer Science, pages 625--640. Springer, 2021."},{"key":"e_1_2_2_20_1","volume-title":"DASFAA 2019, Chiang Mai, Thailand, April 22--25, 2019, Proceedings, Part II","volume":"11447","author":"Wu Dingming","year":"2019","unstructured":"Dingming Wu, Yi Zhu, and Christian S. Jensen. In good company: Efficient retrieval of the top-k most relevant event-partner pairs. In Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Chiang Mai, Thailand, April 22--25, 2019, Proceedings, Part II, volume 11447 of Lecture Notes in Computer Science, pages 519--535. Springer, 2019."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00680-7"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/127787.127796"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259458"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2003.08.007"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00691-4"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534963"},{"key":"e_1_2_2_28_1","first-page":"1","volume-title":"37th International Symposium on Computational Geometry, SoCG 2021, June 7--11, 2021, Buffalo, NY, USA (Virtual Conference)","volume":"189","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. A parallel batch-dynamic data structure for the closest pair problem. In 37th International Symposium on Computational Geometry, SoCG 2021, June 7--11, 2021, Buffalo, NY, USA (Virtual Conference), volume 189 of LIPIcs, pages 60:1--60:16, 2021."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.89"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2304469"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.41"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3193835"},{"key":"e_1_2_2_33_1","first-page":"634","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Mouratidis Kyriakos","year":"2005","unstructured":"Kyriakos Mouratidis, Marios Hadjieleftheriou, and Dimitris Papadias. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14--16, 2005, pages 634--645. ACM, 2005."},{"key":"e_1_2_2_34_1","volume-title":"1st Annual International Conference on Mobile and Ubiquitous Systems (MobiQuitous 2004","author":"Zheng Baihua","year":"2004","unstructured":"Baihua Zheng, Wang-Chien Lee, and Dik Lun Lee. Search continuous nearest neighbors on the air. In 1st Annual International Conference on Mobile and Ubiquitous Systems (MobiQuitous 2004), Networking and Services, 22--25 August 2004, Cambridge, MA, USA, pages 236--245. IEEE Computer Society, 2004."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.1004"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2009.14"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2662236"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559906"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516378"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0200-z"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966387"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.172"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872812"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453973"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066212"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735473"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263671"},{"key":"e_1_2_2_48_1","unstructured":"https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record data.page."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617326","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:15Z","timestamp":1750178775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617326"],"URL":"https:\/\/doi.org\/10.1145\/3617326","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}