{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:48Z","timestamp":1779131208538,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372308"],"award-info":[{"award-number":["62372308"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62572326"],"award-info":[{"award-number":["62572326"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["23IAA00610"],"award-info":[{"award-number":["23IAA00610"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular unsupervised algorithm that identifies clusters as dense regions separated by sparse areas. It requires no preset number of clusters, can detect arbitrary shapes, and is robust to noise, making it widely adopted. However, exact DBSCAN suffers from efficiency issues, and existing approximate variants often trade accuracy for speed. To address this, we reformulate DBSCAN as a Minimum Connected Dominating Set (MCDS) problem and propose LDBS-KDE, a fast and accurate approximation algorithm. LDBS-KDE selects candidate points via lattice-based density-biased sampling, identifies core points using kernel density estimation, and constructs clusters by grouping cores and assigning remaining points. Extensive experiments on four real-world datasets demonstrate that LDBS -KDE achieves accuracy comparable to, and in some cases surpassing, state-of-the-art methods, while offering an improvement in efficiency by a factor of two up to two orders of magnitude.<\/jats:p>","DOI":"10.1145\/3802013","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7101-848X","authenticated-orcid":false,"given":"Jian","family":"Lin","sequence":"first","affiliation":[{"name":"College of Computer Science &amp;#38; Software Engineering, Shenzhen University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2932-2497","authenticated-orcid":false,"given":"Siyue","family":"Wu","sequence":"additional","affiliation":[{"name":"College of Computer Science &amp;#38; Software Engineering, Shenzhen University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7901-9876","authenticated-orcid":false,"given":"Dingming","family":"Wu","sequence":"additional","affiliation":[{"name":"College of Computer Science &amp;#38; Software Engineering, Shenzhen University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5851-7967","authenticated-orcid":false,"given":"Tsz Nam","family":"Chan","sequence":"additional","affiliation":[{"name":"College of Computer Science &amp;#38; Software Engineering, Shenzhen University, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2012. Household in UCI. https:\/\/archive.ics.uci.edu\/dataset\/235 individual+household+electric+power+consumption"},{"key":"e_1_2_1_2_1","unstructured":"2012. PAMAP2 Physical Activity Monitoring. https:\/\/archive.ics.uci.edu dataset\/231\/pamap2+physical+activity+monitoring"},{"key":"e_1_2_1_3_1","unstructured":"2014. BNG (Australian) Open Data. https:\/\/www.openml.org\/search type=data&status=active&id=1205&sort=runs"},{"key":"e_1_2_1_4_1","unstructured":"2014. SUSY. https:\/\/archive.ics.uci.edu\/dataset\/279\/susy"},{"key":"e_1_2_1_5_1","first-page":"15773","article-title":"Space and Time Efficient Kernel Density Estimation in High Dimensions","author":"Backurs Arturs","year":"2019","unstructured":"Arturs Backurs, Piotr Indyk, and Tal Wagner. 2019. Space and Time Efficient Kernel Density Estimation in High Dimensions. In NIPS. 15773-15782.","journal-title":"NIPS."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2787640"},{"key":"e_1_2_1_8_1","first-page":"172","article-title":"Kernel Density Estimation through Density Constrained Near Neighbor Search","author":"Charikar Moses","year":"2020","unstructured":"Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. 2020. Kernel Density Estimation through Density Constrained Near Neighbor Search. In FOCS. 172-183.","journal-title":"FOCS."},{"key":"e_1_2_1_9_1","first-page":"1032","article-title":"Hashing-Based-Estimators for Kernel Density in High Dimensions","author":"Charikar Moses","year":"2017","unstructured":"Moses Charikar and Paris Siminelakis. 2017. Hashing-Based-Estimators for Kernel Density in High Dimensions. In FOCS. 1032-1043.","journal-title":"FOCS."},{"key":"e_1_2_1_10_1","article-title":"KNN-DBSCAN: a DBSCAN in high dimensions","volume":"12","author":"Chen Youguang","year":"2025","unstructured":"Youguang Chen, William Ruys, and George Biros. 2025. KNN-DBSCAN: a DBSCAN in high dimensions. ACM Trans. Parallel Comput., Vol. 12, 1 (2025), 3:1-3:27.","journal-title":"ACM Trans. Parallel Comput."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2020.107624"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2019.2956527"},{"key":"e_1_2_1_13_1","volume-title":"Sloane","author":"Conway John H.","year":"1988","unstructured":"John H. Conway and Neil J. A. Sloane. 1988. Sphere Packings, Lattices and Groups. Vol. 290. Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.patrec.2017.11.011","article-title":"GRIDEN: An effective grid-based and density-based spatial clustering algorithm to support parallel computing","volume":"109","author":"Deng Chao","year":"2018","unstructured":"Chao Deng, Jinwei Song, Ruizhi Sun, Saihua Cai, and Yinxue Shi. 2018. GRIDEN: An effective grid-based and density-based spatial clustering algorithm to support parallel computing. Pattern Recognit. Lett., Vol. 109 (2018), 81-88.","journal-title":"Pattern Recognit. Lett."},{"key":"e_1_2_1_15_1","first-page":"3352","volume-title":"Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016","author":"Doran Gary","year":"2016","unstructured":"Gary Doran, David R. Thompson, and Tara A. Estlin. 2016. Precision Instrument Targeting via Image Registration for the Mars 2020 Rover. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016. 3352-3358."},{"key":"e_1_2_1_16_1","first-page":"226","article-title":"A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD. 226-231.","journal-title":"KDD."},{"key":"e_1_2_1_17_1","first-page":"160","article-title":"Fast Kernel Density Estimation with Density Matrices and Random Fourier Features","author":"Gallego Joseph Alejandro","year":"2022","unstructured":"Joseph Alejandro Gallego, Juan F. Osorio, and Fabio A. Gonz\u00e1lez. 2022. Fast Kernel Density Estimation with Density Matrices and Random Fourier Features. In IBERAMIA. 160-172.","journal-title":"IBERAMIA."},{"key":"e_1_2_1_18_1","first-page":"519","article-title":"DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation","author":"Gan Junhao","year":"2015","unstructured":"Junhao Gan and Yufei Tao. 2015. DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation. In SIGMOD. 519-530.","journal-title":"SIGMOD."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3083897"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_2_1_22_1","unstructured":"Felix Hausdorff. 1914. Grundz\u00fcge der Mengenlehre. Leipzig Viet."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_24_1","article-title":"Road Network Construction with Complex Intersections Based on Sparsely Sampled Private Car Trajectory Data","volume":"13","author":"Huang Yourong","year":"2019","unstructured":"Yourong Huang, Zhu Xiao, Xiaoyou Yu, Dong Wang, Vincent Havyarimana, and Jing Bai. 2019. Road Network Construction with Complex Intersections Based on Sparsely Sampled Private Car Trajectory Data. ACM Trans. Knowl. Discov. Data, Vol. 13 (2019), 35:1-35:28.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_2_1_25_1","first-page":"3019","article-title":"DBSCAN: Towards fast and scalable density clustering","author":"Jang Jennifer","year":"2019","unstructured":"Jennifer Jang and Heinrich Jiang. 2019. DBSCAN: Towards fast and scalable density clustering. In ICML. 3019-3029.","journal-title":"ICML."},{"key":"e_1_2_1_26_1","first-page":"22407","article-title":"Faster DBSCAN via subsampled similarity queries","author":"Jiang Heinrich","year":"2020","unstructured":"Heinrich Jiang, Jennifer Jang, and Jakub Lacki. 2020. Faster DBSCAN via subsampled similarity queries. In NeurIPS. 22407-22419.","journal-title":"NeurIPS."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_28_1","first-page":"3108","article-title":"DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search","author":"Karppa Matti","year":"2022","unstructured":"Matti Karppa, Martin Aum\u00fcller, and Rasmus Pagh. 2022. DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search. In AISTATS. 3108-3137.","journal-title":"AISTATS."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"128219","DOI":"10.1016\/j.eswa.2025.128219","article-title":"AD-RRT*: An RRT*-based global path planning approach for underwater gliders with alpha shapes and DBSCAN","volume":"291","author":"Li Yang","year":"2025","unstructured":"Yang Li, Rongshun Juan, Yatao Zhou, Tianshu Wang, Zezhong Li, Wei Guo, and Zhongke Gao. 2025. AD-RRT*: An RRT*-based global path planning approach for underwater gliders with alpha shapes and DBSCAN. Expert Syst. Appl., Vol. 291 (2025), 128219.","journal-title":"Expert Syst. Appl."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2025.122445"},{"key":"e_1_2_1_31_1","first-page":"35","article-title":"Using grid for accelerating density-based clustering","author":"Mahran Shaaban","year":"2008","unstructured":"Shaaban Mahran and Khaled Mahar. 2008. Using grid for accelerating density-based clustering. In IEEE CIT. 35-40.","journal-title":"IEEE CIT."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/1553374.1553511","article-title":"Information theoretic measures for clusterings comparison: is a correction for chance necessary?","author":"Nguyen Xuan Vinh","year":"2009","unstructured":"Xuan Vinh Nguyen, Julien Epps, and James Bailey. 2009. Information theoretic measures for clusterings comparison: is a correction for chance necessary?. In ICML. 1073-1080.","journal-title":"ICML."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177704472"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3227238.3227511"},{"key":"e_1_2_1_35_1","first-page":"1622","article-title":"\u03b5-Samples for Kernels","author":"Phillips Jeff M.","year":"2013","unstructured":"Jeff M. Phillips. 2013. \u03b5-Samples for Kernels. In SODA. 1622-1632.","journal-title":"SODA."},{"key":"e_1_2_1_36_1","first-page":"2718","article-title":"Improved Coresets for Kernel Density Estimates","author":"Phillips Jeff M.","year":"2018","unstructured":"Jeff M. Phillips and Wai Ming Tai. 2018. Improved Coresets for Kernel Density Estimates. In SODA. 2718-2727.","journal-title":"SODA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00134-6"},{"key":"e_1_2_1_38_1","first-page":"1177","article-title":"Random Features for Large-Scale Kernel Machines","author":"Rahimi Ali","year":"2007","unstructured":"Ali Rahimi and Benjamin Recht. 2007. Random Features for Large-Scale Kernel Machines. In NIPS. 1177-1184.","journal-title":"NIPS."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/1314\/1\/012177"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315140919"},{"key":"e_1_2_1_41_1","first-page":"5789","article-title":"Rehashing Kernel Evaluation in High Dimensions","author":"Siminelakis Paris","year":"2019","unstructured":"Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, and Philip Alexander Levis. 2019. Rehashing Kernel Evaluation in High Dimensions. In ICML. 5789-5798.","journal-title":"ICML."},{"key":"e_1_2_1_42_1","first-page":"1","article-title":"Optimal Coreset for Gaussian Kernel Density Estimation","volume":"63","author":"Tai Wai Ming","year":"2022","unstructured":"Wai Ming Tai. 2022. Optimal Coreset for Gaussian Kernel Density Estimation. In SoCG. 63:1-63:15.","journal-title":"SoCG."},{"key":"e_1_2_1_43_1","first-page":"27978","article-title":"Scalable DBSCAN with Random Projections","author":"Xu Haochuan","year":"2024","unstructured":"Haochuan Xu and Ninh Pham. 2024. Scalable DBSCAN with Random Projections. In NIPS. 27978-28008.","journal-title":"NIPS."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544829"},{"key":"e_1_2_1_45_1","first-page":"433","article-title":"Quality and efficiency for kernel density estimates in large data","author":"Zheng Yan","year":"2013","unstructured":"Yan Zheng, Jeffrey Jestes, Jeff M. Phillips, and Feifei Li. 2013a. Quality and efficiency for kernel density estimates in large data. In SIGMOD. 433-444.","journal-title":"SIGMOD."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:27:47Z","timestamp":1779128867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802013"],"URL":"https:\/\/doi.org\/10.1145\/3802013","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}