ADvaNCE – Efficient and Scalable Approximate Density-Based Clustering Based on Hashing

Article type: Research Article

Authors: Li, Tianrun¹ | Heinis, Thomas^{2; *} | Luk, Wayne²

Affiliations: [1] Tsinghua University, China | [2] Imperial College London, United Kingdom, e-mail: t.heinis@imperial.ac.uk

Correspondence: [*] Corresponding author.

Abstract: Analysing massive amounts of data and extracting value from it has become key across different disciplines. As the amounts of data grow rapidly, current approaches for data analysis are no longer efficient. This is particularly true for clustering algorithms where distance calculations between pairs of points dominate overall time: the more data points are in the dataset, the bigger the share of time needed for distance calculations. Crucial to the data analysis and clustering process, however, is that it is rarely straightforward: instead, parameters need to be determined and tuned first. Entirely accurate results are thus rarely needed and instead we can sacrifice little precision of the final result to accelerate the computation. In this paper we develop ADvaNCE, a new approach based on approximating DBSCAN. More specifically, we propose two measures to reduce distance calculation overhead and to consequently approximate DBSCAN: (1) locality sensitive hashing to approximate and speed up distance calculations and (2) representative point selection to reduce the number of distance calculations. The experiments show that the resulting clustering algorithm is more scalable than the state-of-the-art as the datasets become bigger. Compared with the most recent approximation technique for DBSCAN, our approach is in general one order of magnitude faster (at most 30× in our experiments) as the size of the datasets increase.

Keywords: analytics, clustering, high-dimensional data, approximate computing

Journal: Informatica, vol. 28, no. 1, pp. 105-130, 2017