DBSCAN is a density based clustering algorithm that takes two parameters ϵ and minPts to determine what areas of the datasets are dense/sparse and finally to compute the clustering result. For every input point p, if the neighbourhood within radius ϵ contains at least minPts number of points, we call point p a core point.

Points that are not core points themselves but are density-reachable from any core point are called border points. A cluster defined by DBSCAN starts from a single core point and gradually adds all density-reachable points from any points in this cluster, which leads to a chain effect, and the cluster grows until it is finally complete. Points that are neither core points nor border points are called noise points and do not belong to any cluster.

Naive implementations of the DBSCAN algorithm (Ester et al., 1996) compute distances between all pairs of data points in the dataset in O ( n 2 ). A first proposed optimization uses a KD-Tree (Bentley, 1975) to reduce the number of distance calculations between data points.

At the centre of ADvaNCE is a grid-based optimization (Gunawan, 2013) of DBSCAN that further reduces the distance calculations. The grid used has the same dimensions as all points in the dataset. With this grid we can considerably reduce the number of distance calculations: given a point p, we only have to search in a fixed number of cells around p to find other points within distance ϵ of p. More precisely, given the centre cell c in which p is located, we only have to search the cells c ′ with dist ( c , c ′ ) < ϵ, i.e. the neighbouring cells N ( c ) (red in Fig. 1).

The grid uses uniform spacing of the cells in all dimensions, making assignment of points to cells and related calculations straightforward. With the grid, the algorithm has four distinct phases.

Grid construction: in the assignment phase the algorithm iterates over all points and maps each point to the grid cell that encloses it. To eventually reduce the number of distance calculations, we choose the grid cell width as ϵ D with D as the dimension, guaranteeing that all points within a cell are by definition within distance ϵ of each other and thereby form a cluster.

Determining core points: the goal of this phase is to determine core points. For this phase the choice of grid cell width used in the first phase is crucial. As mentioned previously, if the grid cell width in the first phase is set to ϵ D , then the diagonal of the cell is ϵ and consequently the distance between any two points in the same cell is at most ϵ. If a cell c contains more than minPts points, all the points inside cell c are consequently core points.

Merge clusters: most important in this phase is that we consider each non-empty cell as a small cluster. Further, if two core points in two different cells are within distance less than ϵ of each other, these two points belong to the same cluster and the clusters need to be merged.

To compute all clusters, the optimization generates a graph G = ( V , E ) where V represents all non-empty cells. Given two cells c 1 and c 2 , E contains an edge between c 1 and c 2 if there exist core points p 1 in c 1 and p 2 in c 2 with dist ( p 1 , p 2 ) < ϵ. The result of the merge cluster phase consequently is the connected components of graph G which represent the clusters.

Determine border points: given a non-core point p in cell c (by definition a cell with less than minPts), we check all core points in neighbouring cells N ( c ), and find the core point q with the minimum distance to p. Then p is a border point and belongs to the cluster of core point q. If there are no core points in N ( c ), then p is a noise point and does not belong to any cluster.

A considerable challenge of DBSCAN (and other clustering approaches) is the number of distance calculations and the time needed for them. Even for the optimized DBSCAN algorithm (Gunawan, 2013) the number of distance calculations is substantial. To make matters worse, the number grows rapidly with increasing dataset size.

We demonstrate this problem with a motivation experiment where we increase the size of the dataset from 0.125 millions to 1 million. The datasets used have five dimensions and are randomly generated (Gan and Tao, 2015). For DBSCAN we set the parameters to ϵ = 5000 and the minimum number of points to 100 (Gan and Tao, 2015). We repeat the experiment for each dataset three times and report the average.

As the results in Fig. 2 show, the share of the total time needed to execute distance calculations in DBSCAN starts with a few seconds for a very small dataset of 125’000 and grows rapidly to a substantial share of more than 60% for a dataset of 1 million. Clearly, the share of the overall time spent on distance calculations is substantial and grows rapidly. As we will show in the remainder of this paper, we speed up DBSCAN considerably and enable it to scale by using approximation in two respects. First, we use approximation to reduce the total number of distance calculations, and second, we use approximation to accelerate the remaining distance calculations. As we will show, only little precision has to be sacrificed using ADvaNCE to accelerate the clustering process considerably.

As discussed previously, searching in the neighbouring cells N ( c ) is crucial to the execution of grid-based DBSCAN (Gunawan, 2013) as it is an integral part of every step (except when constructing the grid). The number of cells in N ( c ), however, is growing uncontrollably with an increasing number of dimensions. The basic idea of our approximate algorithm is to find an approximate neighbour for each core point using locality sensitive hashing instead of searching in the potentially large number of cells in N ( c ). We consequently use the approximate neighbours to finish DBSCAN with a controllable precision.

In the context of ADvaNCE we use locality sensitive hashing (LSH, Andoni and Indyk (2008)) to approximate and reduce the neighbourhood that needs to be considered. The LSH functions H we use are random hyperplane projection functions. More precisely, given two points p , q in dimension D 1 (the dimension of the input data) we use H a set of random hyperplane distance functions to project p and q into dimension D 2 , thereby approximating the distance between them. With this, we can assert the following about the approximate distance between p and q:

With this we consequently can construct a new grid NG in D 2 with cellWidth = ϵ and assign each point to the corresponding cell. Given a point p, we define the cell c in the new grid NG that contains p as the approximate neighbour of p, denoted by AN ( p ) and all points in c will serve as approximate neighbour points of p. The algorithm is shown in pseudocode in Algorithm 1.

Given our approach to approximation, it is possible that points that are within the ϵ neighbour sphere B ( p , ϵ ) can not be found in a neighbour cell in NG due to the approximation. In the grid NG in D 2 space B ( p , ϵ ) may be split into two parts. We address this issue by iterating and accumulating the hashing results to obtain a good approximation of the true ϵ neighbours.

Using the approximate neighbours in NG generated based on locality sensitive hashing we propose ADvaNCE-LSH, our approximate grid-based DBSCAN algorithm using LSH as described in Andoni and Indyk (2008). The functions we use are hashing functions with a p-stable distribution (Andoni and Indyk, 2008). Independent of the dimensionality of the input data, we project to 8 dimensional space. An overview in pseudocode is given in Algorithm 2.

The Construct Grid and Determine Core Points functions are very similar to the functions explained for the basic grid-based DBSCAN implementation. In this version we only mark the points as core points when the cell contains more than minPts points and leave it to Determine Core Points Hash to determine which of the remaining points are core points.

The condition for the while loop in Algorithm 2 can be set to a fixed number of iterations. Alternatively, and to control the precision of the result better, we can use a heuristic termination condition that counts the number of core points or the number of clusters and stops when the accuracy no longer improves, i.e. when there is no more change between two iterations.

The function Determine Core Points Hash and Determine Border Points Hash are the approximate versions of Determine Core Points and Determine Border Points described previously. More precisely, in Determine Core Points Hash, for every non-core point p, we count the number of points in AN ( p ) within ϵ of point p. Although AN ( p ) is not equal to B ( p , ϵ ), we can converge to it through iterations. The accumulation of AN ( p ) in successive iterations will converge to B ( p , ϵ ) and we can gradually compute the full result. In Determine Border Points Hash we find the nearest core point for every non-core points p in AN ( p ) generated by LSH. This step can also be repeated several times to improve the accuracy.

The function Merge Clusters Hash is the approximate version of Merge Clusters discussed previously. If two core points p and q are in the same cell in NG and their distance is less than ϵ, the two small clusters that contain p and q are merged. The algorithm is illustrated in Algorithm 3.

In Algorithm 3 we merge the clusters in D 1 using the hashing result in D 2 space. Crucially, we add a break in the for-loop because we do not merge all possible clusters in one go but instead use a number of iterations to gradually merge the clusters and terminate when we meet the condition of the while loop in the main algorithm (Algorithm 2).

As ADvaNCE only approximates the DBSCAN result, it is of course crucial to analyse its accuracy. In the functions Determine CorePoints Hash and Merge Clusters Hash we use the approximate neighbours AN ( p ) based on locality sensitive hashing instead of the actual ϵ neighbours B ( p , ϵ ). This may lead to a decreased accuracy in the following scenarios:

In both scenarios, merging of clusters or identification of core points may not occur. Crucial to ADvaNCE, however, is that it merges clusters in multiple iterations. As the number of iterations grows ADvaNCE will gradually determine more core points and merge more clusters that need to be merged. The impact of these two scenarios on the accuracy will consequently decrease monotonically and the algorithm will converge depending on the stop criteria which is either a fixed number of iterations or no change (in clusters or core points) in the last iterations.

Also note that we still perform distance calculations for points in AN ( p ) to select the points that are truly in B ( p , ϵ ) and use these points to determine core points or merge clusters. We can therefore rule out the following two cases to occur in ADvaNCE:

In conclusion, the accuracy of ADvaNCE will increase monotonically with the number of iterations and an excessive number of iterations therefore cannot adversely affect the accuracy.

The most time consuming part of ADvaNCE is the iterations of hashing and merging. In the following we thus analyse the time complexity of each iteration of ADvaNCE. Since Determine Core Points Hash and Merge Clusters Hash perform a linear search in the approximate neighbourhood AN ( p ), the expected size of the AN, which is also the expected number of collisions for each query point in locality sensitive hashing, is the key to determining the running time of each iteration. We first discuss characteristics of level-i cells (number and distance between them) and the p-stable hashing functions used (probability of collision) before we reason about the time complexity.

Level- i cell characteristics: let P be the set of points in R d where d is a constant (dimensions) and we construct the original grid G for all points in P. We start by defining level-i cells.

An example of level-i cells in a 2D grid is shown in Fig. 4. Relative to the red cell, the yellow cells are level-0 cells, the green cells are level-1 cells, etc. The number of level-i cells N i is N i = ( 2 i + 3 ) d − ( 2 i + 1 ) d = O ( i d − 1 ) . For every point q in level-i cells, the minimum distance between q and p, M i is M i = i × cellWidth = i × ϵ d . The maximum number of points in level-i cell is a constant maxNum as we discussed in the context of the representative points approximation.

Hashing functions characteristics: if f p ( t ) is the probability density function of the absolute value of the p-stable distribution, then for two vectors v 1 , v 2 and with c = ‖ v 1 − v 2 ‖, the probability of collision p ( c ) is: p ( c ) = P r a , b [ h a , b ( v 1 ) = h a , b ( v 2 ) ] = ∫ 0 r 1 c f p ( t c ) ( 1 − t r ) d t where a, b and r are parameters for p-stable LSH functions. In order to get a desirable hash result, we can also concatenate k functions h in H and redefine the hash function as g ( v ) = h 1 ( v ) , h 2 ( v ) , … , h k ( v ). In this case, the probability of collision p ( c ) is as follows: p k ( c ) = 1 c k [ ∫ 0 r 1 c f p ( t c ) ( 1 − t r ) d t ] k . With p (the possibility function defined by a p-stable LSH) and k (the number of hash functions used) the number of collisions for a query point q then is: E [ # Collision ] = ∑ x ∈ D p k ( ‖ q − x ‖ ) where p k ( ‖ q − x ‖ ) is the possibility of collision if two points with distance ‖ q − x ‖ and D is the size of the dataset.

Time complexityanalysis: since we divide the whole dataset into cells of levels, we can redefine the number of collision by level-i cells. In order to determine an upper bound for the number of collisions, we can assume that all points in level-i cells have the distance  M i , which is the minimum distance they can have. E [ # Collision ] = ∑ x ∈ D p k ( ‖ q − x ‖ ) ⩽ ∑ i = 0 ∞ maxNum × N i × p k ( M i ) ⩽ ∑ i = 0 ∞ maxNum × O ( i d − 1 ) × p k ( i ϵ d ) ⩽ ∑ i = 0 ∞ maxNum × O ( i d − 1 ) × ( d i ϵ ) k = maxNum × ( d ϵ ) k × ∑ i = 0 ∞ 1 O ( i k − d + 1 ) .

The expected number of collisions is proportional to an infinite series of i. Given any d (the dimension of the input data) we can always find k ⩾ ( d + 1 ) and the infinite series of i will consequently converge to a constant regardless of how big i is. The expected number of collisions can be expressed by the following function, where C is a constant independent of the size of the dataset: = maxNum × ( d ϵ ) k × C .

The expected size of the approximate neighbour AN ( p ) therefore is O ( 1 ). In function Determine Core Point Hash and Merge Clusters Hash, we perform a linear search in AN for every point, making the time complexity O ( n ). Also, the hashing process itself is O ( n ) and so the time complexity of one whole iteration consequently is O ( n ).

The experiments are run on a Linux Ubuntu 2.6 machine equipped with Intel(R) Xeon(R) CPU E5-2640 0 CPUs running at 2.5 GHz, with 64 KB L1, 256 KB L2 and 12 MB L3 cache and 8 GB RAM at 1333 MHz. The storage consists of 2 SAS disks of 300 GB capacity each. Storage, however, is only used once to read the data into memory. In the following we discuss the software setup as well as the configuration details.

We compare our algorithm against the most recent approximate DBSCAN implementation, ρ-approximate DBSCAN available and set ρ to 0.001 as recommended (Gan and Tao, 2015). We use two different versions of our approach, the first using the hashing approximation only (ADvaNCE-LSH) and the second using the representative point reduction as well (ADvaNCE). Crucially, the stop criteria for ADvaNCE (for both versions) is set so that it achieves the same accuracy as ρ-approximate DBSCAN. Our approach is configured to use eight p-stable hashing functions and convergence stops once no more clusters are merged.

Each algorithm implemented uses a single CPU core to ensure a fair comparison. Our approach is written in C++ while we use the executable provided for Gan and Tao (2015). All implementations are compiled using g++ with -o3.

All experiments are repeated five times and the execution time is averaged.

We use the same synthetic datasets as in Gan and Tao (2015) defined with a dimensionality d, a restart probability ρ restart , a target cardinality and a noise percentage ρ noise . The datasets are generated using a random walk: the walk moves step by step a distance of r shift towards a random direction every c number of steps. In each step, with probability ρ restart , the walker restarts by jumping to a random location in the data space, resetting the step counter to c. No matter if a restart has happened, the walker produces a point uniformly at random in the ball centred at its current location with radius 100. We repeat a total of n × ( 1 − ρ noise ) steps generating the same number of points and add n × ρ noise uniformly distributed noise points. Put simply, we start to generate a cluster and in every step, with probability ρ restart , start to generate a new cluster.

We also use two real datasets (Bache and Lichman, 2013): the Household dataset in 7D as well as the KDD Cup ’99 dataset (after PCA on the attributes) in 9D. The Household dataset measures electric power consumption in one household with a one-minute sampling rate over a period of almost 4 years resulting in 2’049’280 data points. The KDD Cup ’99 dataset consists of 4’898’431 data points representing detected network intrusion events.

All data is normalized in a domain of [0, 10’000] in all dimensions.

To measure the accuracy of the approximate result we compare it to the exact result. We use the established omega-index to measure the quality of the clustering result (Collins and Dent, 1988; Murray et al., 2012). The omega-index assesses the similarity of two clustering results as the ratio of consistent pairs of points, i.e. a point p needs to be in the same clusters in both clustering results. We compare the exact result obtained with the grid-based DBSCAN algorithm with either version of ADvaNCE. A value of the omega-index of 100% consequently means ADvaNCE’s result is precise and all values below that indicate how much the approximate result deviates from the precise result.

The synthetic datasets we use are generated as described previously. The DBSCAN parameter minPts is set to 100 (Gan and Tao, 2015). maxNum for the representative points approximation is set to minPts × M where M is the maximum points per cell.

As a final litmus test of the overall execution time of ADvaNCE, we also compare it against ρ-approximate DBSCAN on real world data. More specifically, we execute ADvaNCE and ρ-approximate DBSCAN on the KDD cup ’99 dataset as well as on the Household dataset (Bache and Lichman, 2013). Given that the number of points per cell is very unbalanced in the real world datasets, we set maxNum for the representative approximation to A × M where M is the maximum number of points in a cell and A is the average number of points per cell.

As the results in Fig. 10 show, ADvaNCE generally outperforms ρ-approximate DBSCAN. As we have already seen on the synthetic data, the ADvaNCE version which also features the representative points approximation further improves the efficiency and in general improves execution time by a factor of 5×. Interestingly, for the KDD cup ’99 data the trend both versions of ADvaNCE exhibit is similar to ρ-approximate DBSCAN but ADvaNCE is still 10x faster. For the Household dataset both versions of ADvaNCE scale substantially better compared to ρ-approximate DBSCAN: the execution time of ρ-approximate DBSCAN grows very fast while ADvaNCE stays nearly flat.

In a next experiment we measure the execution time on the same real world datasets but we increase the size of the datasets. More precisely, we start with a tenth of the dataset and then increase it until we arrive at their full size.

As the results in Fig. 11 show, ADvaNCE also outperforms ρ-approximate DBSCAN by more than a factor of 10. The trends are similar, but for an increasing dataset size, ADvaNCE has an edge over ADvaNCE-LSH as the gap between the trends grows bigger.

As the dimension grows bigger, the maximum number of points and the average number of points in each cell is getting smaller (because the size of the cell is getting smaller: cellWidth = ϵ ( d ) and because there are more directions to spread the data). Fig. 12 confirms this by measuring the maximum as well as average number of points per cell for an increasing number of dimensions. Consequently, ADvaNCE will perform well for an increasing number of dimensions even if only ADvaNCE-LSH, the version which does not curb the number of points per cell, is used.

For an increasing ϵ the picture is different as Fig. 13 shows. In this experiment we measure the maximum (Max Num), the average (Avg Num) as well as the reduced number (Redu Num) of points ADvaNCE considers. The reduced number of points is determined based on the maximum number of points in a cell M and minPts as follows: minPts × M .

The results clearly show that as ϵ grows bigger, the size of cell grows and the number of points in each cell grows as well. The number of points in each cell, however, is unbalanced: some cells contain a very large number of points while others contain only few. The second optimization of ADvaNCE, representative points, effectively addresses this by reducing the number of points considered (while only sacrificing little accuracy).

To understand the behaviour of ADvaNCE, we analyse the performance of its major building blocks Determine Core Point LSH and Merge Clusters LSH in the main iteration of our algorithm. We analyse the behaviour for an increasing ϵ. As the results in Fig. 14 (left) show, if we only use ADvaNCE-LSH (i.e. ADvaNCE without the representative points approximation) as ϵ grows, the time for determining core points will increase considerably from less than 0.1 s to more than 100 s. This is because in this step, for every non-core point, we have to search for all points in the approximate neighbourhood to see if this point is a core point. As ϵ grows larger, the number of points in the approximate neighbourhood grows substantially and the time of this step will become the bottleneck. If we limit the number of points in each cell by the representative points approximation, however, the execution time is curbed.

As Fig. 14 (right) shows, as ϵ grows, if we only use the hashing algorithm but do not limit the number of points, the time for Merge Clusters LSH also increases. The increase, however, is moderate, going from less than 1 second to 10 seconds. This is because in this step we only find one core point in the approximate neighbourhood and then merge cells for every point. As ϵ grows bigger, the number of points in the approximate neighbourhood also grows, but the time of this step consequently does not change substantially. If we limit the number of points in each cell to the representative number of points, the execution time of this step remains the same.

Assessing the execution time of these two functions, we see that if we only use ADvaNCE-LSH, the execution time will increase as ϵ grows, mainly because of the time spent on Determine Core Points. The execution time of both optimizations we use in ADvaNCE, however, remains almost the same (growing slightly) for an increasing ϵ thanks to the representative points approximation.

Arguably the most renowned density based clustering approach is DBSCAN (Ester et al., 1996) itself. Given a set of points in typically high-dimensional space, it groups together points that are closely packed together (points with many nearby neighbours), marking as outliers points that lie alone in sparse regions. More formally, DBSCAN takes parameters ϵ, minPts and identifies core points (points with at least minPts within radius ϵ). DBSCAN then assigns core points within distance ϵ of each other (along with non-core points within distance ϵ) to a cluster. All other points are noise. DBSCAN can efficiently partition dense and sparse space but cannot deal well with varying density.

OPTICS (Ankerst et al., 1999; Breunig et al., 1999) addresses this issue of DBSCAN. Instead of using a fixed distance predicate, ϵ is only used as a maximum distance and the distance is set in different areas of the dataset such that clusters can also be identified in areas of varying densities.

More important to put our work in context, several approximate DBSCAN algorithms have also been devised in recent years.

ADBSCAN (Yeganeh et al., 2009) approaches the problem of accelerating the clustering of DBSCAN by reducing the number of region queries needed. The approach is based on the assumption that clusters are discovered by executing range queries on the dataset. It consequently tries to minimize the number of range queries. To do so, it defines skeletal points as the minimum number of points where range queries (with radius ϵ) need to be executed to capture all clusters. The problem of finding the skeletal points is NP-complete and the ADBSCAN thus essentially proposes how to approximate the set of skeletal points using a genetic algorithm. By approximating the skeletal points, of course, the result of the clustering computation is approximate as well.

IDBSCAN (Borah and Bhattacharyya, 2004) works similarly and approximates and thus accelerates DBSCAN by reducing the range or neighbourhood queries needed. Instead of executing a query for all points in the vicinity of a core point, IDBSCAN only samples the neighourbood and executes a query on a subset of the points. To do so, the neighbourhood of a core point is partitioned into quadrants and a range query is only executed for the points in quadrants randomly chosen. The speed up achieved reaches a factor of six for the datasets tested. However, no guarantees about the results can be made.

l-DBSCAN (Viswanath and Pinkesh, 2006) uses the concept of leaders to accelerate clustering. Leaders are a concise but approximate representation of the patterns in the dataset. l-DBSCAN on a first level clusters the leaders instead of the full dataset thereby accelerating the process. In a second step it replaces the leaders with the actual points from the dataset. With this process l-DBSCAN outperforms the precise version of DBSCAN by a factor of at most two.

ρ-approximate DBSCAN (Gan and Tao, 2015) guarantees the result of its clustering to be between the exact result of DBSCAN with ( ϵ , minPts) and ( ϵ × ( 1 + ρ ) , minPts). The approximation comes with a substantial speed up and scalability: ρ-approximate DBSCAN is proven to run in O ( n ). The approach accomplishes this by using a grid approach where data points are assigned to a grid with cell width ϵ d . For an exact result the algorithm has to connect/combine all pairs of cells c 1 , c 2 that (a) contain at least minPts and (b) contain two points ( p 1 ∈ c 1 and p 2 ∈ c 2 ) within the distance of each other ϵ. This problem is known as the biochromatic closest pair (BCP) and solving it precisely is exceedingly costly. However, solving BCP approximately (in ϵ × ( 1 + ρ )) can be accomplished in linear time. Clearly, the main benefit of this approach are the proven and firm theoretical bounds on error/approximation as well as the execution time.

Pardicle (Patwary et al., 2014) approximates DBSCAN in a supercomputing environment. It accelerates the basic DBSCAN approach by parallelization: after partitioning the multi-dimensional dataset into contiguous chunks, DBSCAN finds clusters in each chunk in parallel on different CPUs/cores of the supercomputing infrastructure. To account for clusters that span several chunks (analysed independently and in parallel on different cores), Pardicle replicates the border (of width ϵ) of a chunk and copies it to adjacent chunks, i.e. to cores in the supercomputer. Doing so in essence makes the chunks overlap but also ensures correctness of the result. To reduce the overhead in terms of replication and distance calculations, not the exact border is calculated but it is sampled. Doing so approximates the results: the result in each chunk is accurate, but merging of clusters between adjacent chunks may fail.