High Performance Density-Based Clustering on Massive Data
Junhao Gan · The University of Queensland · 2017
DBSCAN, a density-based clustering method for multi-dimensional points, was proposed in 1996. Since then, it has received extensive applications, while its computational hardness is still unsolved to this date. The original KDD’96 paper claimed an algorithm of O(n log n) “average run time complexity” (where n is the number of data points) without a rigorous proof. In 2013, a genuine O(n log n)- time algorithm was found in 2D space under the Euclidean distance. The hardness of dimensionality d ≥ 3 has remained open ever since.This thesis considers the problem of computing DBSCAN clusters from scratch (assuming no existing indexes) under the Euclidean distance. We prove that, for d ≥ 3, the problem requires Ω(n 4/3) time to solve, unless very significant breakthroughs—ones widely believed to be impossible—could be made in theoretical computer science. Motivated by this, we propose a relaxed version of the problem called ρ-approximate DBSCAN, which returns the same clusters as DBSCAN, unless the clusters are “unstable” (i.e., they change once the input parameters are slightly perturbed). The ρ- approximate problem can be settled in O(n) expected time regardless of the constant dimensionality d.The thesis also enhances the previous result on the exact DBSCAN problem in 2D space. We show that, if the n data points have been pre-sorted on each dimension (i.e., one sorted list per dimension), the problem can be settled in O(n) worst-case time. As a corollary, when all the coordinates are integers, the 2D DBSCAN problem can be solved in O(n log log n) time deterministically, improving the existing O(n log n) bound.Given the popular usage of density-based clustering approach in many applications demanding data updates, this thesis further investigates the algorithmic principles for dynamic clustering by DBSCAN. Surprisingly, we prove that the ρ-approximate version suffers from the very same hardness when the dataset is fully dynamic, namely, when both insertions and deletions are allowed. We also show that this issue goes away as soon as tiny further relaxation is applied, yet still ensuring the same quality of ρ-approximate DBSCAN. Our algorithms guarantee near-constant update processing, and outperform existing approaches by a factor over two orders of magnitude.The last part of the thesis targets the scenario that the dataset cannot fit in main memory. The core contribution of this part is to show that, for any d-dimensional grid graph with n vertices, we can always compute in O(sort(n)) I/Os—where sort(n) is the I/O complexity of sorting n elements—a multiway vertex separator that serves the same algorithmic purposes as the well-known separator of [Maheshwari and Zeh, SICOMP’08] for a planar graph. This finding leads to (i) an algorithm that performs L∞ density-based clustering (and hence, approximate Lp density-based clustering for any constant p > 0) with near-linear I/Os in any fixed dimensionality, and (ii) improved algorithms for several fundamental problems on 2D grid graphs: connected components (CC), single source shortest path (SSSP), and breadth-first search (BFS). In particular, the improvement on the CC problem owes also to disproving a common belief that 2D grid graphs were sparse under edge contractions.