DBSCAN是一种聚类算法,它可以报告任意形状的聚类和噪声,而无需将聚类的数量作为参数(例如,与其他聚类算法k -means不同)。 由于DBSCAN的运行时间具有二次增长顺序,即O(n 2),因此几十年来,有关提高其性能的研究受到了相当多的关注。 基于网格的DBSCAN是一种完善的算法,其复杂度在2D空间中提高到O(n log n),而在维数≥3时则需要(n 4/3)来求解。 但是,我们发现基于网格的DBSCAN存在两个问题:邻居爆炸和合并中的冗余,这使算法在高维空间中不可行。 在本文中,我们首先提出了一种称为GDCF的新颖算法,该算法利用位图索引来支持有效的邻居网格查询。 其次,基于联合查找算法的概念,我们设计了一个类似于簇的森林结构,以减轻合并中的冗余。 此外,我们发现以不同顺序运行集群林可能会导致在合并步骤中执行不同数量的合并操作。 我们建议以统一的随机顺序执行合并步骤,以优化合并操作的数量。 但是,对于高密度数据库,可能会出现瓶颈,我们进一步提出了以低密度优先的顺序来缓解该瓶颈。 在真实数据集和合成数据集上进行的实验表明,该算法优于最新的精确/近似DBSCAN,并具有良好的可