9 June 2024 in Natural Language Processing Journal
30 December 2022 in Pattern Recognition
23 June 2020 in IEEE Transactions on Knowledge and Data Engineering
Density Peaks Clustering (DPC), a novel density-based clustering approach, has received considerable attention of the research community primarily due to its simplicity and less parameter requirement. However, the clusters obtained using DPC are influenced by its sensitive parameter $d_c$ depending on data distribution and requirements of users. Besides, the original DPC algorithm requires visiting a large number of objects, making it slow. To this end, this paper investigates index-based solutions for DPC. Specifically, we propose two list-based indices: (i) a simple List Index and (ii) an advanced Cumulative Histogram Index. Efficient query algorithms are proposed for these indices which significantly avoids irrelevant comparisons at the cost of space. To remedy this for memory-constrained systems, we further introduce an approximate solution to the above indices allowing substantial reduction in the space cost, provided slight inaccuracies are admissible. Furthermore, owing to considerably lower memory requirements of existing tree-based index structures, we also present effective pruning techniques and efficient query algorithms to support DPC using Quadtree and R-tree indices. Finally, we evaluate all the above indices and present the findings and results, obtained from extensive experiments on six datasets. The experimental insights obtained help to guide in selecting the befitting index.