FB*: A Compact Index for Efficient and Exact Density-based Clustering

Density-based clustering is a fundamental technique for discovering arbitrarily shaped clusters and handling noise, without requiring the number of clusters to be specified in advance. However, existing methods often struggle with efficiency and accuracy across varying query parameters: distance threshold 𝜀 and size threshold 𝜇. In this paper, we propose a novel index-based algorithm for efficient and exact cluster extraction. We introduce FB, the first linear-size index that supports exact clustering with running time linear in the output size for any query 𝜀 and a fixed 𝜇, along with an empirically compact variant, FB * , for efficiently extracting density-based clusters. Due to the compactness of the index and the efficiency of the query algorithm, our index is well-suited for disk-based storage, enabling multiple versions of the index -one for each distinct 𝜇 -to support arbitrary (𝜀, 𝜇) queries. We provide formal analyses of time and space complexity. Extensive experiments on 23 real-world datasets demonstrate that our method significantly outperforms existing approaches while guaranteeing exact clustering results.