{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T01:53:34Z","timestamp":1781488414420,"version":"3.54.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,9,30]]},"abstract":"<jats:p>DBSCAN is a method proposed in 1996 for clustering multi-dimensional points, and has received extensive applications. Its computational hardness is still unsolved to this date. The original KDD\u201a96 paper claimed an algorithm of<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) \u201daverage runtime complexity\u201e (where<jats:italic>n<\/jats:italic>is the number of data points) without a rigorous proof. In 2013, a genuine<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>)-time algorithm was found in 2D space under Euclidean distance. The hardness of dimensionality<jats:italic>d<\/jats:italic>\u22653 has remained open ever since.<\/jats:p><jats:p>This article considers the problem of computing DBSCAN clusters from scratch (assuming no existing indexes) under Euclidean distance. We prove that, for<jats:italic>d<\/jats:italic>\u22653, the problem requires \u03c9(<jats:italic>n<\/jats:italic><jats:sup>4\/3<\/jats:sup>) time to solve, unless very significant breakthroughs\u2014ones widely believed to be impossible\u2014could be made in theoretical computer science. Motivated by this, we propose a relaxed version of the problem called \u03c1-<jats:italic>approximate DBSCAN<\/jats:italic>, which returns the same clusters as DBSCAN, unless the clusters are \u201dunstable\u201e (i.e., they change once the input parameters are slightly perturbed). The \u03c1-approximate problem can be settled in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) expected time regardless of the constant dimensionality<jats:italic>d<\/jats:italic>.<\/jats:p><jats:p>The article also enhances the previous result on the exact DBSCAN problem in 2D space. We show that, if the<jats:italic>n<\/jats:italic>data points have been pre-sorted on each dimension (i.e., one sorted list per dimension), the problem can be settled in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) worst-case time. As a corollary, when all the coordinates are integers, the 2D DBSCAN problem can be solved in<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log log<jats:italic>n<\/jats:italic>) time deterministically, improving the existing<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>) bound.<\/jats:p>","DOI":"10.1145\/3083897","type":"journal-article","created":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T19:20:44Z","timestamp":1501615244000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["On the Hardness and Approximation of Euclidean DBSCAN"],"prefix":"10.1145","volume":"42","author":[{"given":"Junhao","family":"Gan","sequence":"first","affiliation":[{"name":"University of Queensland, St Lucia, Brisbane, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Sha Tin, New Territories, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,7,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574698"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304187"},{"key":"e_1_2_1_4_1","first-page":"3","article-title":"Approximate range searching","volume":"17","author":"Arya Sunil","year":"2000","unstructured":"Sunil Arya and David M. Mount . 2000 . Approximate range searching . Computational Geometry 17 , 3 -- 4 (2000), 135--152. Sunil Arya and David M. Mount. 2000. Approximate range searching. Computational Geometry 17, 3--4 (2000), 135--152.","journal-title":"Computational Geometry"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch85"},{"key":"e_1_2_1_6_1","unstructured":"K. Bache and M. Lichman. 2013. UCI Machine Learning Repository. Retrieved from http:\/\/archive.ics.uci.edu\/ml. K. Bache and M. Lichman. 2013. UCI Machine Learning Repository. Retrieved from http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007620"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICISIP.2004.1287631"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.03.006"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.73"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Mark de Berg Constantinos Tsirogiannis and B. T. Wilkinson. 2015. Fast computation of categorical richness on raster data sets and related problems. 18:1--18:10 . Mark de Berg Constantinos Tsirogiannis and B. T. Wilkinson. 2015. Fast computation of categorical richness on raster data sets and related problems. 18:1--18:10 .","DOI":"10.1145\/2820783.2820825"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Canadian Conference on Computational Geometry (CCCG). 85--90","author":"Erickson Jeff","year":"1995","unstructured":"Jeff Erickson . 1995 . On the relative complexities of some geometric problems . In Proceedings of the Canadian Conference on Computational Geometry (CCCG). 85--90 . Jeff Erickson. 1995. On the relative complexities of some geometric problems. In Proceedings of the Canadian Conference on Computational Geometry (CCCG). 85--90."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712875"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Martin Ester. 2013. Density-based clustering. In Data Clustering: Algorithms and Applications. 111--126. Martin Ester. 2013. Density-based clustering. In Data Clustering: Algorithms and Applications. 111--126.","DOI":"10.1201\/9781315373515-5"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of ACM Knowledge Discovery and Data Mining (SIGKDD). 226--231","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 Proceedings of ACM Knowledge Discovery and Data Mining (SIGKDD). 226--231 . 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 Proceedings of ACM Knowledge Discovery and Data Mining (SIGKDD). 226--231."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737792"},{"key":"e_1_2_1_18_1","volume-title":"A Faster Algorithm for DBSCAN. Master&lsquor;s thesis","author":"Gunawan Ade","unstructured":"Ade Gunawan . 2013. A Faster Algorithm for DBSCAN. Master&lsquor;s thesis . Technische University Eindhoven . Ade Gunawan. 2013. A Faster Algorithm for DBSCAN. Master&lsquor;s thesis. Technische University Eindhoven."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1428-6_3752"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 135--144","author":"Han Yijie","year":"2002","unstructured":"Yijie Han and Mikkel Thorup . 2002 . Integer sorting in 0(n sqrt (log log n)) expected time and linear space . In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 135--144 . Yijie Han and Mikkel Thorup. 2002. Integer sorting in 0(n sqrt (log log n)) expected time and linear space. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS). 135--144."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90023-3"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI). 485--490","author":"Klusch Matthias","year":"2003","unstructured":"Matthias Klusch , Stefano Lodi , and Gianluca Moro . 2003 . Distributed clustering based on sampling local density estimates . In Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI). 485--490 . Matthias Klusch, Stefano Lodi, and Gianluca Moro. 2003. Distributed clustering based on sampling local density estimates. In Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI). 485--490."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920934"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLC.2006.258531"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.155"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIT.2008.4594646"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573972"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2002.1183915"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.96"},{"key":"e_1_2_1_31_1","volume-title":"Conference on High Performance Computing Networking, Storage and Analysis. 62 .","unstructured":"Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, and Alok N. Choudhary. 2012. A new scalable parallel DBSCAN algorithm using the disjoint-set data structure . In Conference on High Performance Computing Networking, Storage and Analysis. 62 . Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, and Alok N. Choudhary. 2012. A new scalable parallel DBSCAN algorithm using the disjoint-set data structure. In Conference on High Performance Computing Networking, Storage and Analysis. 62 ."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810500399654"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISWC.2012.13"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604655_59"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050009"},{"key":"e_1_2_1_36_1","unstructured":"Pang-Ning Tan Michael Steinbach and Vipin Kumar. 2006. Introduction to Data Mining. Pearson. Pang-Ning Tan Michael Steinbach and Vipin Kumar. 2006. Introduction to Data Mining. Pearson."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90042-4"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of International Conference on Multimedia Systems and Signal Processing. 231--236","author":"Tsai Cheng-Fa","year":"2009","unstructured":"Cheng-Fa Tsai and Chien-Tsung Wu . 2009 . GF-DBSCAN: A new efficient and effective data clustering technique for large databases . In Proceedings of International Conference on Multimedia Systems and Signal Processing. 231--236 . Cheng-Fa Tsai and Chien-Tsung Wu. 2009. GF-DBSCAN: A new efficient and effective data clustering technique for large databases. In Proceedings of International Conference on Multimedia Systems and Signal Processing. 231--236."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2003.1211534"},{"key":"e_1_2_1_40_1","volume-title":"Muntz","author":"Wang Wei","year":"1997","unstructured":"Wei Wang , Jiong Yang , and Richard R . Muntz . 1997 . STING : A statistical information grid approach to spatial data mining. In Proceedings of Very Large Data Bases (VLDB) . 186--195. Wei Wang, Jiong Yang, and Richard R. Muntz. 1997. STING: A statistical information grid approach to spatial data mining. In Proceedings of Very Large Data Bases (VLDB). 186--195."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/503104.503108"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3083897","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3083897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T19:50:19Z","timestamp":1750794619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3083897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9,30]]}},"alternative-id":["10.1145\/3083897"],"URL":"https:\/\/doi.org\/10.1145\/3083897","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2016-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}