{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T14:24:17Z","timestamp":1785594257104,"version":"3.56.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"AIP Acceleration Research","award":["JPMJCR23U2"],"award-info":[{"award-number":["JPMJCR23U2"]}]},{"name":"JST CREST","award":["JPMJCR21F2"],"award-info":[{"award-number":["JPMJCR21F2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            Clustering multi-dimensional points is a fundamental task in many fields, and density-based clustering supports many applications because it can discover clusters of arbitrary shapes. This article addresses the problem of Density-Peaks Clustering (DPC) in Euclidean space. DPC already has many applications, but its straightforward implementation incurs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time, where\n            <jats:italic>n<\/jats:italic>\n            is the number of points, thereby does not scale to large datasets. To enable DPC on large datasets, we first propose empirically efficient exact DPC algorithm, Ex-DPC. Although this algorithm is much faster than the straightforward implementation, it still suffers from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time theoretically. We hence propose a new exact algorithm, Ex-DPC++, that runs in\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time. We accelerate their efficiencies by leveraging multi-threading. Moreover, real-world datasets may have arbitrary updates (point insertions and deletions). It is hence important to support efficient cluster updates. To this end, we propose D-DPC for fully dynamic DPC. We conduct extensive experiments using real datasets, and our experimental results demonstrate that our algorithms are efficient and scalable.\n          <\/jats:p>","DOI":"10.1145\/3607873","type":"journal-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T11:54:22Z","timestamp":1688730862000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Density-peaks Clustering Algorithms on Static and Dynamic Data in Euclidean Space"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8571-4931","authenticated-orcid":false,"given":"Daichi","family":"Amagata","sequence":"first","affiliation":[{"name":"Osaka University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4807-3156","authenticated-orcid":false,"given":"Takahiro","family":"Hara","sequence":"additional","affiliation":[{"name":"Osaka University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"445","volume-title":"IEEE Big Data","author":"Amagata Daichi","year":"2022","unstructured":"Daichi Amagata. 2022. Scalable and accurate density-peaks clustering on fully dynamic data. In IEEE Big Data. 445\u2013454."},{"key":"e_1_3_2_3_2","first-page":"49","volume-title":"SIGMOD","author":"Amagata Daichi","year":"2021","unstructured":"Daichi Amagata and Takahiro Hara. 2021. Fast density-peaks clustering: Multicore-based parallelization approach. In SIGMOD. 49\u201361."},{"key":"e_1_3_2_4_2","article-title":"Fast density-peaks clustering: Multicore-based parallelization approach","author":"Amagata Daichi","year":"2022","unstructured":"Daichi Amagata and Takahiro Hara. 2022. Fast density-peaks clustering: Multicore-based parallelization approach. arXiv:2207.04649v2 (2022).","journal-title":"arXiv:2207.04649v2"},{"key":"e_1_3_2_5_2","first-page":"818","volume-title":"ICDE","author":"Amagata Daichi","year":"2019","unstructured":"Daichi Amagata, Takahiro Hara, and Chuan Xiao. 2019. Dynamic set kNN self-join. In ICDE. 818\u2013829."},{"key":"e_1_3_2_6_2","first-page":"36","volume-title":"SIGMOD","author":"Amagata Daichi","year":"2021","unstructured":"Daichi Amagata, Makoto Onizuka, and Takahiro Hara. 2021. Fast and exact outlier detection in metric spaces: A proximity graph-based approach. In SIGMOD. 36\u201348."},{"key":"e_1_3_2_7_2","first-page":"1","article-title":"Fast, exact, and parallel-friendly outlier detection algorithms with proximity graph in metric spaces","author":"Amagata Daichi","year":"2022","unstructured":"Daichi Amagata, Makoto Onizuka, and Takahiro Hara. 2022. Fast, exact, and parallel-friendly outlier detection algorithms with proximity graph in metric spaces. VLDB J 31, 4 (2022), 1\u201325.","journal-title":"VLDB J"},{"key":"e_1_3_2_8_2","first-page":"49","volume-title":"ACM SIGMOD Rec","author":"Ankerst Mihael","year":"1999","unstructured":"Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and J\u00f6rg Sander. 1999. OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Rec. 28, 2 (1999), 49\u201360."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.06.023"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/1143844.1143857","volume-title":"ICML","author":"Beygelzimer Alina","year":"2006","unstructured":"Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. In ICML. 97\u2013104."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00639-0"},{"issue":"1","key":"e_1_3_2_13_2","first-page":"5","article-title":"Hierarchical density estimates for data clustering, visualization, and outlier detection","volume":"10","author":"Campello Ricardo J. G. B.","year":"2015","unstructured":"Ricardo J. G. B. Campello, Davoud Moulavi, Arthur Zimek, and J\u00f6rg Sander. 2015. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Trans. Knowl. Discov. Data 10, 1 (2015), 5.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_3_2_14_2","first-page":"328","volume-title":"SDM","author":"Cao Feng","year":"2006","unstructured":"Feng Cao, Martin Estert, Weining Qian, and Aoying Zhou. 2006. Density-based clustering over an evolving data stream with noise. In SDM. 328\u2013339."},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1145\/3366423.3380183","volume-title":"WWW","author":"Chan Gromit Yeuk-Yin","year":"2020","unstructured":"Gromit Yeuk-Yin Chan, Fan Du, Ryan A. Rossi, Anup B. Rao, Eunyee Koh, Cl\u00e1udio T. Silva, and Juliana Freire. 2020. Real-time clustering for large sparse online visitor data. In WWW. 1049\u20131059."},{"key":"e_1_3_2_16_2","first-page":"579","volume-title":"WWW","author":"Chan T. H. Hubert","year":"2018","unstructured":"T. H. Hubert Chan, Arnaud Guerqin, and Mauro Sozio. 2018. Fully dynamic K-center clustering. In WWW. 579\u2013587."},{"issue":"8","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1621","DOI":"10.1007\/s10994-017-5693-x","article-title":"Local contrast as an effective means to robust clustering against varying densities","volume":"107","author":"Chen Bo","year":"2018","unstructured":"Bo Chen, Kai Ming Ting, Takashi Washio, and Ye Zhu. 2018. Local contrast as an effective means to robust clustering against varying densities. Mach. Learn. 107, 8 (2018), 1621\u20131645.","journal-title":"Mach. Learn."},{"key":"e_1_3_2_18_2","first-page":"133","volume-title":"KDD","author":"Chen Yixin","year":"2007","unstructured":"Yixin Chen and Li Tu. 2007. Density-based clustering for real-time stream data. In KDD. 133\u2013142."},{"key":"e_1_3_2_19_2","first-page":"328","volume-title":"ICDE","author":"Chen Zengjian","year":"2019","unstructured":"Zengjian Chen, Jiayi Liu, Yihe Deng, Kun He, and John E. Hopcroft. 2019. Adaptive wavelet clustering for highly noisy data. In ICDE. 328\u2013337."},{"key":"e_1_3_2_20_2","first-page":"226","volume-title":"KDD","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\u2013231."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-018-1238-7"},{"key":"e_1_3_2_22_2","first-page":"519","volume-title":"SIGMOD","author":"Gan Junhao","year":"2015","unstructured":"Junhao Gan and Yufei Tao. 2015. DBSCAN revisited: Mis-claim, un-fixability, and approximation. In SIGMOD. 519\u2013530."},{"key":"e_1_3_2_23_2","first-page":"1493","volume-title":"SIGMOD","author":"Gan Junhao","year":"2017","unstructured":"Junhao Gan and Yufei Tao. 2017. Dynamic density based clustering. In SIGMOD. 1493\u20131507."},{"issue":"3","key":"e_1_3_2_24_2","first-page":"14","article-title":"On the hardness and approximation of euclidean DBSCAN","volume":"42","author":"Gan Junhao","year":"2017","unstructured":"Junhao Gan and Yufei Tao. 2017. On the hardness and approximation of euclidean DBSCAN. ACM Trans. Datab. Syst. 42, 3 (2017), 14.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_3_2_25_2","first-page":"1067","volume-title":"SIGMOD","author":"Gan Junhao","year":"2018","unstructured":"Junhao Gan and Yufei Tao. 2018. Fast Euclidean optics with bounded precision in low dimensional space. In SIGMOD. 1067\u20131082."},{"issue":"4","key":"e_1_3_2_26_2","first-page":"393","article-title":"Clustering stream data by exploring the evolution of density mountain","volume":"11","author":"Gong Shufeng","year":"2017","unstructured":"Shufeng Gong, Yanfeng Zhang, and Ge Yu. 2017. Clustering stream data by exploring the evolution of density mountain. PVLDB 11, 4 (2017), 393\u2013405.","journal-title":"PVLDB"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2522412"},{"key":"e_1_3_2_28_2","first-page":"70","volume-title":"IDA","author":"Hinneburg Alexander","year":"2007","unstructured":"Alexander Hinneburg and Hans-Henning Gabriel. 2007. DENCLUE 2.0: Fast clustering based on kernel density estimation. In IDA. 70\u201380."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-003-0086-9"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2020.107554"},{"issue":"3","key":"e_1_3_2_31_2","first-page":"33","article-title":"Co-locating style-defining elements on 3D shapes","volume":"36","author":"Hu Ruizhen","year":"2017","unstructured":"Ruizhen Hu, Wenchao Li, Oliver Van Kaick, Hui Huang, Melinos Averkiou, Daniel Cohen-Or, and Hao Zhang. 2017. Co-locating style-defining elements on 3D shapes. ACM Trans. Graph. 36, 3 (2017), 33.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_32_2","first-page":"1162","volume-title":"ICML","author":"Izbicki Mike","year":"2015","unstructured":"Mike Izbicki and Christian Shelton. 2015. Faster cover trees. In ICML. 1162\u20131170."},{"key":"e_1_3_2_33_2","first-page":"828","volume-title":"ICDE","author":"Kim Bogyeong","year":"2021","unstructured":"Bogyeong Kim, Kyoseung Koo, Juhun Kim, and Bongki Moon. 2021. DISC: Density-based incremental clustering by striding over streaming data. In ICDE. 828\u2013839."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/widm.30"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3034611"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1038\/srep45602"},{"key":"e_1_3_2_37_2","first-page":"571","volume-title":"SIGMOD","author":"Qiao Miao","year":"2016","unstructured":"Miao Qiao, Junhao Gan, and Yufei Tao. 2016. Range thresholding on streams. In SIGMOD. 571\u2013582."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3004221"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1242072"},{"key":"e_1_3_2_40_2","first-page":"1173","volume-title":"SIGMOD","author":"Song Hwanjun","year":"2018","unstructured":"Hwanjun Song and Jae-Gil Lee. 2018. RP-DBSCAN: A superfast parallel DBSCAN algorithm based on random partitioning. In SIGMOD. 1173\u20131187."},{"key":"e_1_3_2_41_2","first-page":"1","volume-title":"SDM","author":"Ulanova Liudmila","year":"2016","unstructured":"Liudmila Ulanova, Nurjahan Begum, Mohammad Shokoohi-Yekta, and Eamonn Keogh. 2016. Clustering in the face of fast changing streams. In SDM. 1\u20139."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1552303.1552307"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2535209"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2819173"},{"issue":"2","key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s00778-018-0529-2","article-title":"Leveraging set relations in exact and dynamic set similarity join","volume":"28","author":"Wang Xubo","year":"2019","unstructured":"Xubo Wang, Lu Qin, Xuemin Lin, Ying Zhang, and Lijun Chang. 2019. Leveraging set relations in exact and dynamic set similarity join. VLDB J. 28, 2 (2019), 267\u2013292.","journal-title":"VLDB J."},{"key":"e_1_3_2_46_2","first-page":"2555","volume-title":"SIGMOD","author":"Wang Yiqiu","year":"2020","unstructured":"Yiqiu Wang, Yan Gu, and Julian Shun. 2020. Theoretically-efficient and practical parallel DBSCAN. In SIGMOD. 2555\u20132571."},{"key":"e_1_3_2_47_2","first-page":"1982","volume-title":"SIGMOD","author":"Wang Yiqiu","year":"2021","unstructured":"Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. Fast parallel algorithms for euclidean minimum spanning tree and hierarchical spatial clustering. In SIGMOD. 1982\u20131995."},{"key":"e_1_3_2_48_2","first-page":"49","volume-title":"CIKM","author":"Yang Shuai","year":"2019","unstructured":"Shuai Yang, Xipeng Shen, and Min Chi. 2019. Streamline density peak clustering for practical adoptions. In CIKM. 49\u201358."},{"key":"e_1_3_2_49_2","first-page":"316","volume-title":"SIGKDD","author":"Yuan Jing","year":"2011","unstructured":"Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. 2011. Driving with knowledge from the physical world. In SIGKDD. 316\u2013324."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2609423"},{"key":"e_1_3_2_51_2","first-page":"449","volume-title":"ICDE","author":"Zhang Yu","year":"2017","unstructured":"Yu Zhang, Kanat Tangwongsan, and Srikanta Tirthapura. 2017. Streaming k-means clustering with fast queries. In ICDE. 449\u2013460."},{"key":"e_1_3_2_52_2","first-page":"1262","volume-title":"NAACL-HLT","author":"Zhang Yang","year":"2015","unstructured":"Yang Zhang, Yunqing Xia, Yi Liu, and Wenmin Wang. 2015. Clustering sentences with density peaks for multi-document summarization. In NAACL-HLT. 1262\u20131267."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-020-09874-x"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607873","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:06Z","timestamp":1750178226000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3607873"],"URL":"https:\/\/doi.org\/10.1145\/3607873","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"assertion":[{"value":"2023-01-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}