{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:12Z","timestamp":1777965732846,"version":"3.51.4"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p> We present a new algorithm for the widely used density-based clustering method\u00a0dbscan. For a set of [Formula: see text] points in [Formula: see text] our algorithm computes the dbscan-clustering in [Formula: see text] time, irrespective of the scale parameter\u00a0[Formula: see text] (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of [Formula: see text] than the original dbscan algorithm. We also present an [Formula: see text] randomized algorithm for hdbscan in the plane\u00a0\u2014 hdbscan is a hierarchical version of dbscan introduced recently\u00a0\u2014 and we show how to compute an approximate version of hdbscan in near-linear time in any fixed dimension. <\/jats:p>","DOI":"10.1142\/s0218195919400028","type":"journal-article","created":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T03:31:31Z","timestamp":1566271891000},"page":"21-47","source":"Crossref","is-referenced-by-count":8,"title":["Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces"],"prefix":"10.1142","volume":"29","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[{"name":"Department of Computing Science, TU Eindhoven, P. O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ade","family":"Gunawan","sequence":"additional","affiliation":[{"name":"Department of Computing Science, TU Eindhoven, P. O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1129-461X","authenticated-orcid":false,"given":"Marcel","family":"Roeloffzen","sequence":"additional","affiliation":[{"name":"Department of Computing Science, TU Eindhoven, P. O. Box 513, 5600 MB Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,8,20]]},"reference":[{"key":"S0218195919400028BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.21"},{"key":"S0218195919400028BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574698"},{"key":"S0218195919400028BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304187"},{"key":"S0218195919400028BIB004","first-page":"416","volume-title":"Proc. 30th Symp. Computational Geometry","author":"Arya S.","year":"2014"},{"key":"S0218195919400028BIB005","doi-asserted-by":"publisher","DOI":"10.1109\/ICISIP.2004.1287631"},{"key":"S0218195919400028BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"S0218195919400028BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37456-2_14"},{"key":"S0218195919400028BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001683"},{"key":"S0218195919400028BIB009","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S0218195919400028BIB010","first-page":"85","volume-title":"Proc. 7th Canadian Conf. Comput. Geom. (CCCG)","author":"Erickson J.","year":"1995"},{"key":"S0218195919400028BIB011","first-page":"226","volume-title":"Proc. 2nd Int. Conf. Knowledge Discovery and Data Mining (KDD)","author":"Ester M.","year":"1996"},{"key":"S0218195919400028BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737792"},{"key":"S0218195919400028BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00027-X"},{"key":"S0218195919400028BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLC.2006.258531"},{"key":"S0218195919400028BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/CIT.2008.4594646"},{"key":"S0218195919400028BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90006-E"},{"key":"S0218195919400028BIB018","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"S0218195919400028BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503255"},{"key":"S0218195919400028BIB020","volume-title":"Introduction to Data Mining","author":"Tan P.","year":"2006"},{"key":"S0218195919400028BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187718"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195919400028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T03:31:34Z","timestamp":1566271894000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195919400028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3]]},"references-count":20,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,8,20]]},"published-print":{"date-parts":[[2019,3]]}},"alternative-id":["10.1142\/S0218195919400028"],"URL":"https:\/\/doi.org\/10.1142\/s0218195919400028","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3]]}}}