# Scalable Density-based Clustering with Random Projections

Haochuan Xu<EMAIL_ADDRESS>University of AucklandAucklandNew
Zealand and  Ninh Pham<EMAIL_ADDRESS>University of
AucklandAucklandNew Zealand

###### Abstract.

We present sDBSCAN, a scalable density-based clustering algorithm in high
dimensions with cosine distance. Utilizing the neighborhood-preserving
property of random projections, sDBSCAN can quickly identify core points and
their neighborhoods, the primary hurdle of density-based clustering.
Theoretically, sDBSCAN outputs a clustering structure similar to DBSCAN under
mild conditions with high probability. To further facilitate sDBSCAN, we
present sOPTICS, a scalable OPTICS for interactive exploration of the
intrinsic clustering structure. We also extend sDBSCAN and sOPTICS to L2, L1,
$\chi^{2}$, and Jensen-Shannon distances via random kernel features.
Empirically, sDBSCAN is significantly faster and provides higher accuracy than
many other clustering algorithms on real-world million-point data sets. On
these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-
learn’s counterparts demand several hours or cannot run due to memory
constraints.

##  1\. Introduction

DBSCAN (Ester et al., 1996) is one of the most fundamental clustering
algorithms with many applications in data mining and machine learning
(Campello et al., 2020). It has been featured in several data analysis tool
kits, including scikit-learn in Python, ELKI in Java, and CRAN in R. In
principle, DBSCAN connects neighboring points from nearby high-density areas
to form a cluster where the high density is decided by a sufficiently large
number of points in the neighborhood. DBSCAN is parameterized by
$(\varepsilon,minPts)$ where $\varepsilon$ is the distance threshold to govern
the neighborhood of a point and connect nearby areas, and $minPts$ is the
density threshold to identify high-density areas.

Apart from other popular clustering algorithms, including $k$-means variants
(Arthur and Vassilvitskii, 2007; Dhillon et al., 2004) and spectral clustering
(Shi and Malik, 2000), DBSCAN is non-parametric. It can find the number of
clusters, detect arbitrary shapes and sizes, and work on any arbitrary
distance measure.

Given a distance measure, DBSCAN has two primary steps, including (1) finding
the $\varepsilon$-neighborhood (i.e. points within a radius $\varepsilon$) for
every point to discover the density areas surrounding the point and (2)
forming the cluster by connecting neighboring points. The first step is the
primary bottleneck as finding $\varepsilon$-neighborhood for every point
requires a worst-case $O(n^{2})$ time for a data set of $n$ points in high-
dimensional space (Gan and Tao, 2017; Schubert et al., 2017). This limits the
applications of DBSCAN on modern data sets with millions of points.

Another hurdle of $(\varepsilon,minPts)$-DBSCAN is the choice of
$(\varepsilon,minPts)$, which highly depends on the data distribution and
distance measure. When measuring the clustering accuracy regarding the ground
truth (i.e. class labels) using cosine distance, we observe that changing
$\varepsilon$ by just 0.005 can diminish the clustering accuracy by 10% on
some data sets. Therefore, it is essential to not only develop scalable
versions of DBSCAN but also to provide feasible tools to guide the parameter
setting for such algorithms on large data sets.

Prior arts on scaling up DBSCAN. Due to the quadratic time bottleneck of
DBSCAN in high-dimensional space, researchers study efficient solutions to
scale up the process of identifying the neighborhood for each point. These
works can be classified into two groups, including balled-based approaches for
scaling up exact DBSCAN, and index-based and sampling-based approaches for
scaling up approximate DBSCAN.

Ball-based approaches (Mai et al., 2016; Huang and Ma, 2023; Kumar and Reddy,
2016) partition the data set into several subsets and extract clusters from
these subsets. These approaches iteratively refine the extracted clustering
structures by performing additional $\varepsilon$-neighborhood queries on a
small set of important points to obtain the same results as DBSCAN. However,
these approaches still have worst-case quadratic time.

Grid-based indexing (Gan and Tao, 2017; de Berg et al., 2019) efficiently
identifies neighborhood areas by confining the neighbor search exclusively to
neighboring grids. Unfortunately, these approaches only work well on low-
dimensional Euclidean space as its complexity grows exponentially to the
dimension. Random projections (Esfandiari et al., 2021; Schneider and Vlachos,
2017) have been used to build grid-based or tree-based indexes for faster
approximate $\varepsilon$-neighborhoods. These randomized approaches only work
on Euclidean distance and do not offer theoretical guarantees on the
clustering accuracy compared to the DBSCAN’s result.

Instead of finding the $\varepsilon$-neighborhood for every point, sampling
approaches (Jang and Jiang, 2019; Jiang et al., 2020; Viswanath and Babu,
2009) discover the neighborhood for a subset of sampled points and run DBSCAN
on this subset to reduce the running time. DBSCAN++ (Jang and Jiang, 2019)
finds the exact $\varepsilon$-neighborhoods for a subset of random points
chosen through either uniform sampling or $k$-center sampling. In contrast,
sngDBSCAN (Jiang et al., 2020) approximates the $\varepsilon$-neighborhood for
every point by computing the distance between the point to a subset of random
points. Though sampling-based DBSCAN variants are simple and efficient, they
offer statistical guarantees on the clustering accuracy via level set
estimation (Jiang, 2017) that requires many strong assumptions on the data
distribution. Moreover, selecting suitable parameter values for sampling-based
approaches is challenging due to the nature of sampling.

Prior arts on selecting parameter values for DBSCAN. A common approach to
select parameter values for $(\varepsilon,minPts)$-DBSCAN is fixing $minPts$
first to smooth the density estimate (Schubert et al., 2017). While $minPts$
is easier to set, $\varepsilon$ is much harder as it depends on the distance
measure and data distribution. OPTICS (Ankerst et al., 1999) attempts to
mitigate the problem of selecting relevant $\varepsilon$ by linearly ordering
the data points such that close points become neighbors in the ordering.
Besides the cluster ordering, OPTICS also computes a reachability distance for
each point. The dendrogram provided by OPTICS visualizes the density-based
clustering results corresponding to a broad range of $\varepsilon$, which
indicates a relevant range of $\varepsilon$ for DBSCAN.

Similar to DBSCAN, OPTICS requires the $\varepsilon$-neighborhood for every
point and hence inherits a quadratic time complexity in high-dimensional
space. Even worse, ones often need a large $\varepsilon$ to discover
clustering structures on a wide range of $\varepsilon$. Such large
$\varepsilon$ settings need $O(n^{2})$ memory as the
$\varepsilon$-neighborhood of one point might need $O(n)$ space. The memory
constraint is the primary hurdle that limits the visual tool OPTICS on large
data sets.

Contribution. Inspired by sampling approaches, we observe that the exact
$\varepsilon$-neighborhood for every point is not necessary to form and
visualize the density-based clustering results. We leverage the neighborhood-
preserving property of random projections (Pham, 2021) to select high-quality
candidates for the discovery of $\varepsilon$-neighborhoods with cosine
distance. Our approach called sDBSCAN first builds random projection-based
indexing with a sufficiently large number of projection vectors. The
asymptotic property of the concomitant of extreme order statistics (David and
Galambos, 1974) enables us to quickly estimate $\varepsilon$-neighborhoods and
form density-based clustering. Theoretically, sDBSCAN outputs a clustering
structure similar to DBSCAN on cosine distance under mild conditions with high
probability. Empirically, sDBSCAN runs significantly faster than other
competitive DBSCAN variants while still achieving similar DBSCAN clustering
accuracy on million-point data sets.

To further facilitate sDBSCAN, we propose sOPTICS, a scalable OPTICS derived
from the random projection-based indexing, to guide the parameter setting. We
also extend sDBSCAN and sOPTICS to other popular distance measures, including
L2, L1, $\chi^{2}$, and Jensen-Shannon (JS), that allow random kernel features
(Rahimi and Recht, 2007; Vedaldi and Zisserman, 2012).

Scalability. Both sDBSCAN and sOPTICS are scalable and multi-thread friendly.
Multi-threading sOPTICS takes a few minutes to visualize clustering structures
for million-point data sets while the scikit-learn counterpart cannot run due
to memory constraints. Compared to the ground truth on Mnist8m with 8.1
million points, multi-threading sDBSCAN gives 38% accuracy (measuring by the
normalized mutual information NMI) and runs in 15 minutes on a single machine
of 2.2GHz 32-core (64 threads) AMD processor with 128GB of DRAM. In contrast,
kernel $k$-means (Wang et al., 2019) achieves 41% accuracy with Spark, running
in 15 minutes on a supercomputer with 32 nodes, each of which has two 2.3GHz
16-core (32 threads) Haswell processors and 128GB of DRAM.

##  2\. Preliminary

This section introduces the background of DBSCAN (Ester et al., 1996; Schubert
et al., 2017) and its computational challenges in high dimensions. We also
describe OPTICS (Ankerst et al., 1999), a DBSCAN-based approach to visualize
the clustering structure and select appropriate DBSCAN parameters. We then
elaborate on the connection between range search and approximate nearest
neighbor search (ANNS) on executing DBSCAN and OPTICS. We present a recent
advanced random projection method (Pham, 2021; Pham and Liu, 2022) for ANNS on
the extreme setting where the number of random projection vectors is
sufficiently large. The data structures inspired by these approaches can scale
up DBSCAN and OPTICS on million-point data sets.

###  2.1. DBSCAN

DBSCAN is a density-based approach that links nearby dense areas to form the
cluster. For a distance measure $dist(\cdot,\cdot)$, DBSCAN has two parameters
$\varepsilon$ and $minPts$. Given the data set $\mathbf{X}$, for each point
$\mathbf{q}\in\mathbf{X}$, DBSCAN executes a range reporting query
$B_{\varepsilon}{(\mathbf{q})}$ that finds all points
$\mathbf{x}\in\mathbf{X}$ within the $\varepsilon$-neighborhood of
$\mathbf{q}$, i.e.
$B_{\varepsilon}{(\mathbf{q})}=\\{\mathbf{x}\in\mathbf{X}\,|\,dist(\mathbf{x},\mathbf{q})\leq\varepsilon\\}$.
Based on the size of the range query result, DBSCAN determines $\mathbf{q}$ as
core if $|B_{\varepsilon}{(\mathbf{q})}|\geq minPts$; otherwise, non-core
points. We will call the $\varepsilon$-neighborhood
$B_{\varepsilon}{(\mathbf{q})}$ as the neighborhood of $\mathbf{q}$ for short.

DBSCAN forms density-based clusters by connecting core points and their
neighborhoods where two core points $\mathbf{q}_{1}$ and $\mathbf{q}_{2}$ are
connected if $\mathbf{q}_{1}\in B_{\varepsilon}{(\mathbf{q}_{2})}$ or
$\mathbf{q}_{2}\in B_{\varepsilon}{(\mathbf{q}_{1})}$. A non-core point
$\mathbf{x}$ belonging to a core point $\mathbf{q}$’s neighborhood (i.e.,
$\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$) will be considered as a border
point and will share the same cluster label as $\mathbf{q}$111As a non-core
point $\mathbf{x}$ might belong to several core points’ neighborhood, DBSCAN
uses the label of the first identified core point whose neighborhood contains
$\mathbf{x}$.. Non-core points not belonging to any core point’s neighborhood
will be classified as noisy points.

Alternatively, we can see that DBSCAN forms a connected graph $G$ that
connects $n$ points together (Schubert et al., 2017; Jang and Jiang, 2019).
$G$ will have several connected components corresponding to the cluster
structure. Each connected component of $G$ contains connected core points and
their neighborhoods. Algorithm 1 shows how DBSCAN works after finding all core
points and their neighborhoods.

Algorithm 1 DBSCAN

1: Inputs: $\mathbf{X},\varepsilon,minPts$, the set
$C=\\{(\mathbf{q},B_{\varepsilon}{(\mathbf{q})})\,|\,\mathbf{q}\text{ is
core}\\}$

2: $G\leftarrow$ initialize empty graph

3: for each $\mathbf{q}\in C$ do

4: Add an edge (and possibly a vertex or vertices) in $G$ from $\mathbf{q}$ to
all core points in $B_{\varepsilon}{(\mathbf{q})}$

5: Add an edge (and possibly a vertex) in $G$ from $\mathbf{q}$ to non-core
points $\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ if $\mathbf{x}$ is not
connected

6: return connected components of $G$

###  2.2. Challenges of DBSCAN in High Dimensions

Since we study DBSCAN on $\mathbf{X}\in\mathbb{R}^{d}$ of $n$ points, we will
elaborate on the challenges of applying DBSCAN to large-scale high-dimensional
data sets, including its time complexity and parameter sensitivity.

DBSCAN’s complexity on L2. The running time of DBSCAN is dominated by the cost
of executing $n$ range reporting queries $B_{\varepsilon}{(\mathbf{q})}$ for
$n$ points $\mathbf{q}\in\mathbf{X}$, which is $O(n^{2})$ for the exact
solution. On low-dimensional Euclidean space, i.e., $d$ is a constant, Gan and
Tao (Gan and Tao, 2017) establish the connection between DBSCAN and the unit-
spherical emptiness checking (USEC) problem. This work shows a conditional
lower bound $\Omega(n^{4/3})$ for the worst-case running time of DBSCAN based
on the notion of Hopcroft hard (Erickson, 1995).

In high-dimensional Euclidean space where $d$ is large, it is challenging to
answer $k$-nearest neighbor ($k$NN) exactly in sublinear time in $n$. If there
exists an algorithm using polynomial indexing space $d^{O(1)}n^{O(1)}$ and
solving exact $k$NN in truly sublinear time, the Strong Exponential Time
Hypothesis (SETH) (Impagliazzo et al., 2001), a fundamental conjecture in
computational complexity theory, is wrong (Andoni et al., 2018; Williams and
Yu, 2014). Hence, we conjecture that solving an exact range reporting query in
truly sublinear time requires the space exponential in $d$ since we can use
$k$NN queries with various $k$ values to answer a range reporting query.
Indeed, several theoretical works (Matousek, 1994; Chazelle et al., 2008; Arya
et al., 2010; Ahle et al., 2017) seek efficient solutions for answering range
reporting queries approximately. Therefore, solving DBSCAN exactly in
subquadratic time in high-dimensional Euclidean space seems hard.

DBSCAN’s parameter settings. DBSCAN has two parameters $\varepsilon$ and
$minPts$ to estimate the empirical density of the point via its neighborhood.
While $minPts$ is easier to set for smoothing the density estimate, the
clustering structure provided by DBSCAN is susceptible to $\varepsilon$. An
incorrect value of $\varepsilon$ will degrade the whole cluster structure.
This is more crucial in high dimensional data sets where the range of
$\varepsilon$ is very sensitive. For instance, when applying DBSCAN with
cosine distance on the Pamap2 data set, by varying $\varepsilon$ by just 0.1,
there exists $\mathbf{q}$ such that
$B_{\varepsilon}{(\mathbf{q})}\approx\mathbf{X}$, and therefore, the entire
data set becomes a single cluster. To handle this issue, OPTICS (Ankerst et
al., 1999) has been proposed to visualize connected components provided by
DBSCAN over a wide range of $\varepsilon$. Hence, one can select relevant
values for $\varepsilon$ to obtain meaningful clustering results.

###  2.3. OPTICS

OPTICS (Ankerst et al., 1999) attempts to mitigate the problem of selecting
relevant $\varepsilon$ by linearly ordering the data points such that close
points become neighbors in the ordering. For each point
$\mathbf{x}\in\mathbf{X}$, OPTICS computes a reachability distance from its
closest core point. Each point’s cluster ordering and reachability distance
are used to construct a reachability-plot dendrogram that visualizes the
density-based clustering results corresponding to a broad range of
$\varepsilon$. Valleys in the reachability-plot are considered as clustering
indicators.

In principle, given a pair $(\varepsilon,minPts)$, OPTICS first identifies the
core points, their neighborhoods, and their core distances. Then, OPTICS
iterates $\mathbf{X}$, and for each $\mathbf{x}\in\mathbf{X}$, computes the
smallest reachability distance, called $\mathbf{x}.reach$, between
$\mathbf{x}$ and the processed core points so far. The point with the minimum
reachability distance will be processed first and inserted into the cluster
ordering $O$.

The core distance, coreDist for short, and reachability distance, reachDist
for short, are defined as follows.

$\displaystyle coreDist(\mathbf{q})$
$\displaystyle=\begin{cases}\infty&\text{if $\mathbf{q}$ is non-core,}\\\
minPts-\text{NN distance}&\text{otherwise.}\end{cases}$ $\displaystyle
reachDist(\mathbf{x},\mathbf{q})$ $\displaystyle=\begin{cases}\infty&\text{if
$\mathbf{q}$ is non-core,}\\\
max(coreDist(\mathbf{q}),dist(\mathbf{x},\mathbf{q}))&\text{otherwise.}\end{cases}$

For a core point $\mathbf{q}$, $reachDist(\mathbf{x},\mathbf{q})$ is
$dist(\mathbf{x},\mathbf{q})$ if $\mathbf{x}$ is not belonging to $minPts-$NN
of $\mathbf{q}$. Among several core points whose neighborhood contains
$\mathbf{x}$, OPTICS seeks the smallest reachability distance
$\mathbf{x}.reach$ for $\mathbf{x}$ from these core points. In other words,
$\mathbf{x}.reach=\min_{\mathbf{q}_{i}}{\left(reachDist(\mathbf{x},\mathbf{q}_{i})\,|\,\mathbf{q}_{i}\text{
is core and }\mathbf{x}\in B_{\varepsilon}{(\mathbf{q}_{i})}\right)}$.

OPTICS can be implemented as a nested loop as shown in Algorithm 2. In the
outer loop (Line 4), a random $\mathbf{q}\in\mathbf{X}$ is selected and
inserted into an empty cluster ordering $O$. If $\mathbf{q}$ is core, each
point $\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ is inserted into a
priority queue $Q$ with $reachDist(\mathbf{x},\mathbf{q})$ as the key value.
An inner loop (Line 12) that successively pops $\mathbf{q}^{\prime}$ from $Q$
until $Q$ is empty. We can see that the priority of $\mathbf{q}^{\prime}\in Q$
is determined by their smallest reachability distance w.r.t. current core
points processed so far. The point with the smallest reachability distance in
$Q$ is always popped first (due to the priority queue) and inserted into the
ordering $O$.

We note that our presented OPTICS in Algorithm 2 is slightly different from
the original version (Ankerst et al., 1999). Since we do not know how to
implement decrease-key operation efficiently on the priority queue 222C++ STL
priority queue does not support decrease-key function., we propose a “lazy
deletion” where we keep adding $\mathbf{x}$ into $Q$ with the new key. Though
$\mathbf{x}$ might be duplicated on $Q$, by checking whether or not
$\mathbf{x}$ is processed (Lines 16–18), we can process each point exactly
once and output it into the cluster ordering $O$. When a point $\mathbf{x}$ is
inserted into the ordering $O$, $\mathbf{x}.reach$ at the time it was popped
out of $Q$ is recorded. Therefore, by setting $\varepsilon$ large enough,
OPTICS outputs a cluster ordering that can be used as a visualization to
extract clustering structure for smaller values of $\varepsilon$.

Time and space complexity. Similar to DBSCAN, the running time of OPTICS is
$O(n^{2})$ makes it impractical on large-scale data sets. Fast implementations
of OPTICS with large values of $\varepsilon$ will require $O(n^{2})$ memory to
store the matrix distance between the core points and its neighborhood points.
Such implementations are infeasible for large $n$.

Algorithm 2 OPTICS

1: Inputs: $\mathbf{X},\varepsilon,minPts$, the set
$C=\\{(\mathbf{q},B_{\varepsilon}{(\mathbf{q})},coreDist(\mathbf{q}),$
$\\{dist(\mathbf{x},\mathbf{q})\text{ for each }\mathbf{x}\in
B_{\varepsilon}{(\mathbf{q})}\\})\,|\,\mathbf{q}\text{ is core}\\}$

2: Initialize an empty cluster ordering $O$

3: $\mathbf{q}.reach\leftarrow\infty$ for each $\mathbf{q}\in\mathbf{X}$

4: for each unprocessed $\mathbf{q}\in\mathbf{X}$ do

5: Mark $\mathbf{q}$ as processed, and insert $\mathbf{q}$ into $O$

6: if $\mathbf{q}$ is core then

7: Seeds $\leftarrow$ empty priority queue $Q$

8: for each $\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ do

9: if $\mathbf{x}$ is unprocessed then

10: $\mathbf{x}.reach\leftarrow
min(\mathbf{x}.reach,reachDist(\mathbf{x},\mathbf{q}))$

11: Insert $(\mathbf{x},\mathbf{x}.reach)$ into $Q$

12: while $Q$ is not empty do

13: $\mathbf{q}^{\prime}\leftarrow Q.pop()$

14: if $\mathbf{q}^{\prime}$ is processed then

15: continue

16: Mark $\mathbf{q}^{\prime}$ as processed, and insert $\mathbf{q}^{\prime}$
into $O$

17: if $\mathbf{q}^{\prime}$ is core then

18: for each unprocessed $\mathbf{x}\in
B_{\varepsilon}{(\mathbf{q}^{\prime})}$ do

19: $\mathbf{x}.reach\leftarrow
min(\mathbf{x}.reach,reachDist(\mathbf{x},\mathbf{q}^{\prime}))$

20: Insert $(\mathbf{x},\mathbf{x}.reach)$ into $Q$

21: return Cluster ordering $O$

###  2.4. Random projection-based ANNS

Since the primary bottleneck of DBSCAN is to find core points and their
neighborhoods, reducing the running time of this step will significantly
improve the performance. Indeed, most of the techniques in the literature
build indexing data structures to speed up the process of finding core points
and their neighborhoods.

We will elaborate on recent works (Pham, 2021; Pham and Liu, 2022) that study
extreme order statistics properties of random projection methods for ANNS. The
extreme behavior of random projections is first studied on approximate maximum
inner product search, called CEOs (Pham, 2021). It is later combined with a
cross-polytope LSH family (Andoni et al., 2015) to improve the ANNS solvers on
cosine distance (Pham and Liu, 2022).

Given $D$ random vectors $\mathbf{r}_{i}\in\mathbb{R}^{d}$, $i\in[D]$, whose
coordinates are randomly selected from the standard normal distribution
$N(0,1)$, and the sign function $\texttt{sgn}(\cdot)$. CEOs randomly projects
$\mathbf{X}$ and the query $\mathbf{q}$ onto these $D$ Gaussian random
vectors. It considers the projection values on specific random vectors that
are closest or furthest to $\mathbf{q}$, e.g.,
$\operatorname*{arg\,max}_{\mathbf{r}_{i}}{|\mathbf{q}^{\top}\mathbf{r}_{i}|}$.
Given a sufficiently large $D$, the following lemma states that the projection
values on the closest/furthest random vector to $\mathbf{q}$ preserve the
inner product approximately.

###### Lemma 2.1.

(Pham, 2021) For two points $\mathbf{x},\mathbf{q}\in\mathcal{S}^{d-1}$ and
significantly large $D$ random vectors $\mathbf{r}_{i}$, w.l.o.g. we assume
that
$\mathbf{r}_{1}=\operatorname*{arg\,max}_{\mathbf{r}_{i}}{|\mathbf{q}^{\top}\mathbf{r}_{i}|}$.
Then, we have

(1) $\displaystyle\mathbf{x}^{\top}\mathbf{r}_{1}\sim
N\left(\mathtt{sgn}(\mathbf{q}^{\top}\mathbf{r}_{1})\cdot\mathbf{x}^{\top}\mathbf{q}\,\sqrt{2\ln{(D)}}\,,1-(\mathbf{x}^{\top}\mathbf{q})^{2}\right)\,.$

As a geometric intuition, we can see that, for significantly large $D$ random
vectors, if $\mathbf{r}_{1}$ is closest or furthest to $\mathbf{q}$, the
projection values of all points in $\mathbf{X}$ onto $\mathbf{r}_{1}$ tend to
preserve their inner product order with $\mathbf{q}$. Importantly, given a
constant $k>0$, Lemma 2.1 also holds for the top-$k$ closest/furthest vectors
to $\mathbf{q}$ due to the asymptotic property of extreme normal order
statistics (David and Galambos, 1974; Pham, 2021). Therefore, by maintaining a
few points that are closest/furthest to random vectors, we can answer ANNS
accurately and efficiently. In the next section, we will utilize this
observation to significantly reduce the cost of identifying core points and,
hence, the running time of DBSCAN and OPTICS in high dimensions.

Algorithm 3 Preprocessing

1: Inputs: $\mathbf{X}\subset\mathcal{S}^{d-1}$, $D$ random vectors
$\mathbf{r}_{i}$, $k,m=O(minPts)$

2: for each $\mathbf{q}\in\mathbf{X}$, compute and store top-$k$ closest and
top-$k$ furthest vectors $\mathbf{r}_{i}$ to $\mathbf{q}$.

3: for each random vector $\mathbf{r}_{i}$, compute and store top-$m$ closest
and top-$m$ furthest points to $\mathbf{r}_{i}$.

##  3\. Random projection-based methods

While previous works leverage the extreme behavior of random projections to
improve ANNS solvers, we utilize it to find the core points and their
neighborhoods. We first present novel scalable DBSCAN and OPTICS versions,
called sDBSCAN and sOPTICS, with the cosine distance on the unit sphere. We
then leverage well-known random feature embeddings (Rahimi and Recht, 2007;
Vedaldi and Zisserman, 2012) to extend our proposed sDBSCAN and sOPTICS to
other popular distance measures, including L1 and L2 metrics, and widely used
similarity measures for image data, including $\chi^{2}$ and Jensen-Shannon
(JS).

###  3.1. Preprocessing and finding core points

The primary execution of DBSCAN is to identify core points and their
neighborhoods to form connected cluster components. In particular,
$(\varepsilon,minPts)$-DBSCAN identifies $\mathbf{q}\in\mathbf{X}$ as a core
point if $|B_{\varepsilon}{(\mathbf{q})}|\geq minPts$. We present how random
projections can speed up the identification of core points and approximate
their neighborhoods with cosine distance.

For each point $\mathbf{q}\in\mathbf{X}\subset\mathcal{S}^{d-1}$, we compute
$D$ random projection values $\mathbf{q}^{\top}\mathbf{r}_{i}$ where
$i\in[D]$. W.l.o.g., we assume that
$\mathbf{r}_{1}=\operatorname*{arg\,max}_{\mathbf{r}_{i}}{|\mathbf{q}^{\top}\mathbf{r}_{i}|}=\operatorname*{arg\,max}_{\mathbf{r}_{i}}{\mathbf{q}^{\top}\mathbf{r}_{i}}$.
Lemma 2.1 indicates that, given a sufficiently large $D$, points closer to
$\mathbf{r}_{1}$ tend to have smaller distances to $\mathbf{q}$. Hence,
computing the distance between $\mathbf{q}$ to the top-$m$ points closest to
$\mathbf{r}_{1}$ where $m\geq minPts$ suffices to ensure whether or not
$\mathbf{q}$ is a core point.

As Lemma 2.1 holds for the top-$k$ closest and top-$k$ furthest random vectors
to $\mathbf{q}$, for each random vector $\mathbf{r}_{i}$, we maintain the
top-$m$ closest points and the top-$m$ furthest points to $\mathbf{r}_{i}$,
respectively. Given a point $\mathbf{q}$, we compute the distances between
$\mathbf{q}$ to the top-$m$ closest/furthest points corresponding to the
top-$k$ closest/furthest random vectors of $\mathbf{q}$. By considering these
$2k$ specific vectors and computing $2km$ distances, we can improve the
accuracy of identifying the core points and enrich their neighborhoods.

Preprocessing. Algorithm 3 shows how we preprocess the data set. For each
point $\mathbf{q}\in\mathbf{X}$, we keep top-$k$ closest/furthest random
vectors. For each random vector $\mathbf{r}_{i}$, we keep top-$m$
closest/furthest points. In practice, setting $m=O(minPts)$ suffices to
identify core points and approximate their neighborhoods to ensure the quality
of sDBSCAN and sOPTICS. In theory, we need to adjust $m$ depending on the data
distribution to guarantee the clustering quality.

Algorithm 4 Finding core points and their neighborhoods

1: Inputs: $\mathbf{X}\subset\mathcal{S}^{d-1}$, $D$ random vectors
$\mathbf{r}_{i}$, $k,\varepsilon,m=O(minPts)$

2: Initialize an empty set $\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ for
each $\mathbf{q}\in\mathbf{X}$

3: for each $\mathbf{q}\in\mathbf{X}$ do

4: for each $\mathbf{r}_{i}$ from top-$k$ closest random vectors of
$\mathbf{q}$ do

5: for each $\mathbf{x}$ from top-$m$ closest points of $\mathbf{r}_{i}$ do

6: if $dist(\mathbf{x},\mathbf{q})\leq\varepsilon$ then

7: Insert $\mathbf{x}$ into $\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ and
insert $\mathbf{q}$ into $\widetilde{B}_{\varepsilon}(\mathbf{x})$

8: for each $\mathbf{r}_{i}$ from top-$k$ furthest random vectors of
$\mathbf{q}$ do

9: for each $\mathbf{x}$ from top-$m$ furthest points of $\mathbf{r}_{i}$ do

10: if $dist(\mathbf{x},\mathbf{q})\leq\varepsilon$ then

11: Insert $\mathbf{x}$ into $\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ and
insert $\mathbf{q}$ into $\widetilde{B}_{\varepsilon}(\mathbf{x})$

12: for each $\mathbf{q}\in\mathbf{X}$ do

13: if $|\widetilde{B}_{\varepsilon}{(\mathbf{q})}|\geq minPts$ then

14: Identify $\mathbf{q}$ as the core point

15: Store $\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ as an approximate result
of $B_{\varepsilon}{(\mathbf{q})}$

16: Store $dist(\mathbf{x},\mathbf{q})$ for each
$\mathbf{x}\in\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ {Only for sOPTICS}

Finding core points and their neighborhoods. After preprocessing, we run
Algorithm 4 to identify core points and approximate their neighborhoods using
$D$ random vectors. Given $m=O(minPts)$, for each point
$\mathbf{q}\in\mathbf{X}$, we only compute the distances to the $O(k\cdot
minPts)$ points 333Due to duplicates, $2k\cdot m$ is the maximum number of
distances for each point. from the top-$k$ closest/furthest random vectors to
$\mathbf{q}$. For a small constant $k$, we only need $O(d\cdot minPts)$ time,
compared to $O(dn)$ of the exact solution, to identify a core point
$\mathbf{q}$ and its neighborhood subset
$\widetilde{B}_{\varepsilon}{(\mathbf{q})}\subseteq
B_{\varepsilon}{(\mathbf{q})}$. Though we might miss a few core points and
points in their neighborhoods, our theoretical analysis shows that the
identified core points and their neighborhood subsets can recover the DBSCAN’s
clustering structure under common assumptions.

###  3.2. sDBSCAN and sOPTICS

After identifying core points and their approximate neighborhoods, we form the
density-based clustering, as shown in Algorithm 5. Two core points
$\mathbf{q}_{1},\mathbf{q}_{2}$ are connected to each other if
$\mathbf{q}_{1}\in\widetilde{B}_{\varepsilon}(\mathbf{q}_{2})$ or
$\mathbf{q}_{2}\in\widetilde{B}_{\varepsilon}(\mathbf{q}_{1})$. Though
$\widetilde{B}_{\varepsilon}{(\mathbf{q})}\subseteq
B_{\varepsilon}{(\mathbf{q})}$, we will show that sDBSCAN can output the
DBSCAN’s result under common assumptions.

To guide DBSCAN’s parameter setting, Algorithm 6 presents sOPTICS, an OPTICS
variant with the identified core points and their neighborhood subsets
provided by Algorithm 4. Given the identified core point $\mathbf{q}$ and
$\widetilde{B}_{\varepsilon}{(\mathbf{q})}$, we store the set
$\\{dist(\mathbf{x},\mathbf{q})\text{ for each
}\mathbf{x}\in\widetilde{B}_{\varepsilon}{(\mathbf{q})}\\}$ (Line 16 of Alg.
4). Using this set, we can estimate $coreDist(\mathbf{q})$ as the $minPts$-NN
distance between $\mathbf{q}$ and $\widetilde{B}_{\varepsilon}{(\mathbf{q})}$.
Though such estimation is an upper bound of $coreDist(\mathbf{q})$, the
tightness of the upper bound and the accurate neighborhood approximation make
the reachability-plot provided by sOPTICS nearly identical to the original
OPTICS with the same valley areas. Therefore, sOPTICS is a fast and reliable
tool to guide DBSCAN and sDBSCAN parameter settings and to visualize the
clustering structure.

Algorithm 5 sDBSCAN

1: Inputs: $\mathbf{X}\subset\mathcal{S}^{d-1}$, $D$ random vectors
$\mathbf{r}_{i}$, $\varepsilon$, $minPts$

2: Call Algorithm 3 for preprocessing with $m=O(minPts)$

3: Call Algorithm 4 to find the set
$C=\\{(\mathbf{q},\widetilde{B}_{\varepsilon}{(\mathbf{q})})\,|\,\mathbf{q}\text{
is identified as core}\\}$

4: Call DBSCAN (Alg. 1) given the output $C$ from Algorithm 4

Multi-threading. Like DBSCAN and OPTICS, the main computational bottlenecks of
both sDBSCAN and sOPTICS are identifying core points and approximating their
neighborhood. Fortunately, Algorithm 3 and 4 are fast and parallel-friendly.
We only need to add #pragma omp parallel directive on the for loops to run in
multi-threads. This enables sDBSCAN and sOPTICS to deal with million-point
data sets in minutes while the scikit-learn counterparts need hours or even
cannot finish.

##  4\. Theoretical analysis

We first prove sDBSCAN can identify any core point with high probability. We
then show how to set $m$ adaptively to the data distribution to ensure sDBSCAN
recovers the clustering result of DBSCAN under common assumptions. We also
discuss practical settings and heuristic improvements for sDBSCAN and sOPTICS.

###  4.1. Identify core points

For each point $\mathbf{x}\in\mathbf{X}\subset\mathcal{S}^{d-1}$, we compute
$D$ random projection values $\mathbf{x}^{\top}\mathbf{r}_{i}$ where
$i\in[D]$. These random projection values are used to identify the core points
in $\mathbf{X}$ and approximate their neighborhoods. For simplicity, we
analyze a single point $\mathbf{q}\in\mathbf{X}$ with the cosine distance.

For a sufficiently large $D$, Lemma 2.1 holds for top-$k$ closest/furthest
random vectors. We assume that
$\mathbf{r}_{1}=\operatorname*{arg\,max}_{\mathbf{r}_{i}}{|\mathbf{q}^{\top}\mathbf{r}_{i}|}=\operatorname*{arg\,max}_{\mathbf{r}_{i}}{\mathbf{q}^{\top}\mathbf{r}_{i}}$
w.l.o.g.. We denote by $\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ and
$\mathbf{y}\in\mathbf{X}\setminus B_{\varepsilon}{(\mathbf{q})}$ any close and
far away points to $\mathbf{q}$ regarding the distance threshold
$\varepsilon$. Defining random variables
$X=\mathbf{x}^{\top}\mathbf{r}_{1},Y=\mathbf{y}^{\top}\mathbf{r}_{1}$, from
Eq.(1), we have

$\displaystyle X\sim
N\left(\mathbf{x}^{\top}\mathbf{q}\,\sqrt{2\ln{(D)}}\,,1-(\mathbf{x}^{\top}\mathbf{q})^{2}\right)\,,\,Y\sim
N\left(\mathbf{y}^{\top}\mathbf{q}\,\sqrt{2\ln{(D)}}\,,1-(\mathbf{y}^{\top}\mathbf{q})^{2}\right)$

Let
$\alpha_{\mathbf{x}}=\left(\mathbf{x}^{\top}\mathbf{q}-\mathbf{y}^{\top}\mathbf{q}\right)/\left(\sqrt{1-\left(\mathbf{x}^{\top}\mathbf{q}\right)^{2}}+\sqrt{1-\left(\mathbf{y}^{\top}\mathbf{q}\right)^{2}}\right)$.
From the Chernoff bound (Wainwright, 2019) for the Gaussian variable $Y-X$, we
have

(2) $\displaystyle\textrm{\bf Pr}\left[Y\geq X\right]$ $\displaystyle\leq
D^{-\left(\mathbf{x}^{\top}\mathbf{q}-\mathbf{y}^{\top}\mathbf{q}\right)^{2}/\left(\sqrt{1-\left(\mathbf{x}^{\top}\mathbf{q}\right)^{2}}+\sqrt{1-\left(\mathbf{y}^{\top}\mathbf{q}\right)^{2}}\right)^{2}}=D^{-\alpha_{\mathbf{x}}^{2}}.$

We can see that the order of projection values onto $\mathbf{r}_{1}$ between
$\mathbf{x}$ and $\mathbf{y}$, i.e.,
$\mathbf{x}^{\top}\mathbf{r}_{1}\geq\mathbf{y}^{\top}\mathbf{r}_{1}$,
preserves their inner product order, i.e.,
$\mathbf{x}^{\top}\mathbf{q}\geq\mathbf{y}^{\top}\mathbf{q}$, with high
probability when $D$ is sufficiently large. To estimate
$B_{\varepsilon}{(\mathbf{q})}$, we sort $n$ projection values onto
$\mathbf{r}_{1}$, and consider the top-$m$ points closest to $\mathbf{r}_{1}$
as the top-$m$ candidates where $m\geq minPts$. Among these $m$ candidates, if
$minPts$ points are within $\varepsilon$ to $\mathbf{q}$, we safely conclude
that $\mathbf{q}$ is the core point. The following lemma justifies that
$m=minPts$ suffices to identify any core point.

###### Lemma 4.1.

Given a sufficiently large $D$, for a given core point
$\mathbf{q}\in\mathbf{X}\subset\mathcal{S}^{d-1}$ where
$|B_{\varepsilon}{(\mathbf{q})}|\geq minPts$ and its closest random vector
$\mathbf{r}_{1}$, the top-$minPts$ points with largest projection values onto
$\mathbf{r}_{1}$ are a subset of $B_{\varepsilon}{(\mathbf{q})}$ with
probability at least $1-1/n$.

Algorithm 6 sOPTICS

1: Inputs: $\mathbf{X}\subset\mathcal{S}^{d-1}$, $D$ random vectors
$\mathbf{r}_{i}$, $\varepsilon$, $minPts$

2: Call Algorithm 3 for preprocessing with $m=O(minPts)$

3: Call Algorithm 4 to find the set
$C=\\{(\mathbf{q},\widetilde{B}_{\varepsilon}{(\mathbf{q})},\newline
\\{dist(\mathbf{x},\mathbf{q})\text{ for each
}\mathbf{x}\in\widetilde{B}_{\varepsilon}{(\mathbf{q})}\\})\,|\,\mathbf{q}\text{
is identified as core}\\}$

4: Use the $minPts-$NN distance between $\mathbf{q}$ and
$\mathbf{x}\in\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ as
$coreDist(\mathbf{q})$ for each identified core point $\mathbf{q}$

5: Call OPTICS (Alg. 2) given the output $C$ from Algorithm 4

###### Proof.

We consider the $n$ projection values onto $\mathbf{r}_{1}$, i.e.
$\mathbf{X}^{\top}\mathbf{r}_{1}$, in the descending order. For a given point
$\mathbf{y}\in\mathbf{X}\setminus B_{\varepsilon}{(\mathbf{q})}$, let
$Y=\mathbf{y}^{\top}\mathbf{r}_{1}$. For any $\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}$, we define random variables
$X_{i}=\mathbf{x}_{i}^{\top}\mathbf{r}_{1}$. Denote by
$\overline{\alpha}=\left(\sum_{\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}}{\alpha_{\mathbf{x}_{i}}}\right)/|B_{\varepsilon}{(\mathbf{q})}|$
the average value for all $\alpha_{\mathbf{x}_{i}}$ for $\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}$ and $\mathbf{y}$, by applying Eq. (2) we have

$\displaystyle\textrm{\bf Pr}\left[\mathbf{y}\text{ is ranked as
top-1}\right]\leq\prod_{\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}}{\textrm{\bf Pr}\left[Y\geq X_{i}\right]}\,$
$\displaystyle\leq D^{-\sum_{\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}}{\alpha^{2}_{\mathbf{x}_{i}}}}\leq
D^{-|B_{\varepsilon}{(\mathbf{q})}|\overline{\alpha}^{\,2}}\,.$

Let $B_{minPts}(\mathbf{q})$ be the set of top-$minPts$ nearest neighbors of
$\mathbf{q}$ in $\mathbf{X}$. We define
$\overline{\alpha}_{*}=\left(\sum_{\mathbf{x}_{i}\in
B_{\varepsilon}{(\mathbf{q})}\setminus
B_{minPts}(\mathbf{q})}{\alpha_{\mathbf{x}_{i}}}\right)/\left(|B_{\varepsilon}{(\mathbf{q})}|-minPts\right)$.
Using the same argument, we bound the probability that $\mathbf{y}$ is ranked
on the top-$minPts$ points among $n$ projection values onto $\mathbf{r}_{1}$
as

$\textrm{\bf Pr}\left[\mathbf{y}\text{ is ranked on top-}minPts\right]\leq
D^{-\left(|B_{\varepsilon}{(\mathbf{q})}|-minPts\right)\overline{\alpha}_{*}^{\,2}}\,.$

By setting
$D=n^{2/\left(|B_{\varepsilon}{(\mathbf{q})}|-minPts\right)\overline{\alpha}_{*}^{\,2}}$,
this probability is bounded by $1/n^{2}$.

For any $\mathbf{y}_{j}\in\mathbf{X}\setminus B_{\varepsilon}{(\mathbf{q})}$,
let $\alpha_{*}=\operatorname*{arg\,min}_{\mathbf{y}_{j}\in\mathbf{X}\setminus
B_{\varepsilon}{(\mathbf{q})}}\overline{\alpha}_{*}$ and
$D=n^{2/\left(|B_{\varepsilon}{(\mathbf{q})}|-minPts\right)\alpha_{*}^{2}}$,
applying the union bound, we have

$\displaystyle\textrm{\bf Pr}\left[\text{Top-}minPts\text{ points closest to
$\mathbf{r}_{1}$ are in }B_{\varepsilon}{(\mathbf{q})}\right]\,$
$\displaystyle\geq 1-n\cdot\textrm{\bf Pr}\left[\mathbf{y}_{j}\text{ is ranked
among the top-}minPts\text{ positions}\right]\,$ $\displaystyle\geq 1-1/n\,.$

Hence, we prove the claim given a sufficiently large $D$. ∎

Lemma 4.1 indicates that setting $m=minPts$ suffice to identify whether a
point $\mathbf{q}$ is core. As Lemma 2.1 holds with the top-$k$
closest/furthest random vectors to $\mathbf{q}$ given a constant $k$, so does
Lemma 4.1. Therefore, Algorithm 4 (Lines 4–11) runs the same procedure on
these $2k$ specific random vectors, increasing the core point identification’s
accuracy and enriching the core point’s neighborhood. This is essential to
ensure the quality of sDBSCAN for clustering and its corresponding sOPTICS for
visualization.

We note that Lemma 4.1 holds given significantly large $D$ random vectors,
i.e.
$D=n^{2/\left(|B_{\varepsilon}{(\mathbf{q})}|-minPts\right)\alpha_{*}^{2}}$.
Empirically, we observe that, for any core point $\mathbf{q}$ regarding
$(\varepsilon,minPts)$, $|B_{\varepsilon}{(\mathbf{q})}|$ is often
substantially larger than $minPts$. Furthermore, the distance gap between
$\mathbf{q}$ and points inside and outside $B_{\varepsilon}{(\mathbf{q})}$ is
significant, making $\alpha_{*}^{2}$ large. Hence, setting $D=1,024$ suffices
to achieve the clustering quality on many real-world data sets.

###  4.2. Ensure sDBSCAN’s quality

Ensuring the clustering quality without any assumptions about the data
distribution is hard. Following up on previous works (Jang and Jiang, 2019;
Jiang et al., 2020), we describe the common assumption used in analyzing the
performance of sDBSCAN given the approximate neighborhood of identified core
points.

######  Assumption 1.

There exists a constant $t$ such that, for any pair of nearby core points
$\mathbf{q}_{1},\mathbf{q}_{2}$, if
$dist(\mathbf{q}_{1},\mathbf{q}_{2})\leq\varepsilon$, then
$B_{\varepsilon}(\mathbf{q}_{1})$ and $B_{\varepsilon}(\mathbf{q}_{2})$ share
at least $t$ common core points.

Since two connected core points share at least $t$ common core points, this
assumption ensures that the density-based clusters would not become
arbitrarily thin anywhere. Otherwise, it is a good indicator that we need to
select different parameter settings $(\varepsilon,minPts)$ to reflect the
clustering structure. Our assumption is similar to the third assumption in
(Jiang et al., 2020), and our proof technique is inspired by (Jiang et al.,
2020). However, we do not need the other two assumptions in (Jiang et al.,
2020) since we can leverage the distance preservation property of CEOs.

Given that DBSCAN produces $l$ density-based clusters
$C_{1},C_{2},\ldots,C_{l}$, it can be seen easily that $t$ will be the lower
bound of the min-cut of the subgraph $G_{i}$ formed by connecting all core
points in the cluster $C_{i}$ together. We will use the following lemma (Jiang
et al., 2020; Karger, 1999) to guarantee the quality of sDBSCAN.

###### Lemma 4.2.

Let $G$ be a graph of $n$ vertices with min-cut $t$ and $0<\delta<1$. There
exists a universal constant $c$ such that if
$s\geq\frac{c\left(\log{(1/\delta)}+\log{(n)}\right)}{t}$, then with
probability at least $1-\delta$, the graph $G_{s}$ derived by sampling each
edge of $G$ with probability $s$ is connected.

Now, the rest of the analysis shows that for a given core point $\mathbf{q}\in
G_{i}$, we guarantee that sDBSCAN will find any point $\mathbf{x}\in
B_{\varepsilon}{(\mathbf{q})}$ with probability at least
$c\left(\log{(1/\delta)}+\log{(|G_{i}|)}\right)/t$.

Consider if $dist(\mathbf{x},\mathbf{q})\leq\varepsilon$ then
$\mathbf{x}^{\top}\mathbf{q}\geq 1-\varepsilon^{2}/2$, we make a change in our
algorithm. For each random vector $\mathbf{r}_{i}$, we maintain two sets
$S_{i}=\\{\mathbf{x}\in\mathbf{X}\,|\,\mathbf{x}^{\top}\mathbf{r}_{i}\geq(1-\varepsilon^{2}/2)\sqrt{2\ln{(D)}}\\}$
and
$R_{i}=\\{\mathbf{x}\in\mathbf{X}\,|\,\mathbf{x}^{\top}\mathbf{r}_{i}\leq-(1-\varepsilon^{2}/2)\sqrt{2\ln{(D)}}\\}$,
instead of keeping only top-$m$ closest/furthest points. In other words, for
each random vector $\mathbf{r}_{i}$, the value of $m$ is set adaptively to the
data distributed around $\mathbf{r}_{i}$. Now, given a point $\mathbf{q}$ and
its closest random vector $\mathbf{r}_{1}$, we compute
$dist(\mathbf{x},\mathbf{q})$ for all $\mathbf{x}\in S_{1}$ where
$S_{1}=\\{\mathbf{x}\in\mathbf{X}\,|\,\mathbf{x}^{\top}\mathbf{r}_{1}\geq(1-\varepsilon^{2}/2)\sqrt{2\ln{(D)}}\\}$.
By checking all $\mathbf{x}\in S_{1}$, we guarantee to select any
$\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ with a probability at least 1/2
due to the Gaussian distribution in Eq. (1).

For any point $\mathbf{q}$, by computing the distance between $\mathbf{q}$ and
all points in $S_{i}$ or $R_{i}$ corresponding to the top-$k$ closest/furthest
random vectors of $\mathbf{q}$, we can boost the probability to identify any
$\mathbf{x}\in B_{\varepsilon}{(\mathbf{q})}$ to at least
$1-\left(1/2\right)^{2k}$ due to the asymptotic independence among these $2k$
vectors (Pham, 2021; David and Galambos, 1974). Therefore, by Lemma 4.2, if
$t\left(1-\left(1/2\right)^{2k}\right)\geq
c\left(\log{(1/\delta)}+\log{(n_{i})}\right)$ where $n_{i}$ is the number of
core points of $C_{i}$, we can guarantee that the cluster structures provided
by DBSCAN and sDBSCAN are the same with probability at least $1-\delta$. We
are now ready to state our main result.

###### Lemma 4.3.

Let $G_{1},G_{2},\ldots,G_{l}$ be connected subgraphs produced by DBSCAN where
each $G_{i}$ corresponds to a cluster $C_{i}$ with $n_{i}$ core points. Assume
that any pair of nearby core points $\mathbf{q}_{1},\mathbf{q}_{2}$, if
$dist(\mathbf{q}_{1},\mathbf{q}_{2})\leq\varepsilon$, then
$B_{\varepsilon}(\mathbf{q}_{1})$ and $B_{\varepsilon}(\mathbf{q}_{2})$ share
at least $t$ common core points. There exists a constant $c$ such that if
$t\left(1-\left(1/2\right)^{2k}\right)\geq
c\left(\log{(1/\delta)}+\log{(n_{i})}\right)$ for $i\in[l]$, sDBSCAN will
recover $G_{1},G_{2},\ldots,G_{l}$ as clusters with probability at least
$1-\delta$.

Lemma 4.3 indicates that when the cluster $C_{i}$ of size $n_{i}$ is not thin
anywhere, i.e. the neighborhoods of any two connected core points share
$t=O(\log{(n_{i})})$ common core points, sDBSCAN can recover $C_{i}$ with
probability $1-1/n_{i}$. However, it comes with the cost of maintaining larger
neighborhoods around the random vector $\mathbf{r}_{i}$ (i.e. $S_{i}$,
$R_{i}$) and hence causes significant computational resources.

In practice, a core point $\mathbf{q}$ is often surrounded by many other core
points in a dense cluster. Therefore, instead of maintaining the sets
$S_{i},R_{i}$ for each random vector $\mathbf{r}_{i}$, we can keep the top-$m$
points of these sets where $m=O(minPts)$. This setting substantially reduces
the memory usage and running time of sDBSCAN without degrading clustering
results.

###  4.3. Discuss sOPTICS’s quality

Ensuring sOPTICS recovers OPTICS’s result is difficult without any further
assumptions as OPTICS’s result is sensitive to the order of processed core
points and their exact neighborhoods. Hence, we will discuss sOPTICS’s quality
in practical scenarios.

Like sDBSCAN, sOPTICS only considers top-$m$ closest/furthest points to any
random vector where $m=O(minPts)$. Given a core point $\mathbf{q}$, the core
distance of $\mathbf{q}$ derived from the set
$\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ is an upper bound of
$coreDist(\mathbf{q})$. Since a core point $\mathbf{q}$ is often surrounded by
many other core points in a dense cluster,
$\widetilde{B}_{\varepsilon}{(\mathbf{q})}$ tends to contain core points.
Hence, the upper bound of reachability distance provided by sOPTICS is tight.
When the clustering structure is well separated, i.e., valleys in the
reachability-plot are deep, sOPTICS with $m=O(minPts)$ is a reliable tool to
guide the selection of $(\varepsilon,minPts)$ for DBSCAN. Importantly, the
extra space of sOPTICS is linear, i.e. $O(nk\cdot minPts)$, as the approximate
neighborhood size of each point is $O(k\cdot minPts)$.

###  4.4. Extend to other distance measures

While previous subsections present and analyze sDBSCAN and sOPTICS on cosine
distance, this subsection will extend them to other popular distance measures,
including L2, L1, $\chi^{2}$, and Jensen-Shannon (JS). We will utilize the
random features (Rahimi and Recht, 2007; Vedaldi and Zisserman, 2012) to embed
these distances into cosine distance. In particular, we study fast randomized
feature mapping $f:\mathbb{R}^{d}\mapsto\mathbb{R}^{d^{\prime}}$ such that
$\textrm{\bf
E}\left[f(\mathbf{x})^{\top}f(\mathbf{q})\right]=K(\mathbf{x},\mathbf{q})$
where $K$ is the kernel function. We study Gaussian, Laplacian, $\chi^{2}$,
and JS kernels as their randomized mappings are well-studied and efficiently
computed. Also, the embeddings’ extra costs are negligible compared to those
of sDBSCAN and sOPTICS.

Given
$\mathbf{x}=\\{x_{1},\ldots,x_{d}\\},\mathbf{y}=\\{y_{1},\ldots,y_{d}\\}$ and
$\sigma>0$, the following are the definitions of the investigated kernels.

$\displaystyle K_{L}(\mathbf{x},\mathbf{y})$
$\displaystyle=e^{-\|\mathbf{x}-\mathbf{y}\|_{1}/\sigma}\,;\,K_{G}(\mathbf{x},\mathbf{y})=e^{-\|\mathbf{x}-\mathbf{y}\|_{2}^{2}/2\sigma^{2}}\,;$
$\displaystyle K_{\chi^{2}}(\mathbf{x},\mathbf{y})$
$\displaystyle=\sum_{i}\frac{2x_{i}y_{i}}{x_{i}+y_{i}}\,;$ $\displaystyle
K_{JS}(\mathbf{x},\mathbf{y})$
$\displaystyle=\sum_{i}\frac{x_{i}}{2}\log{\left(\frac{x_{i}+y_{i}}{x_{i}}\right)}+\frac{y_{i}}{2}\log{\left(\frac{x_{i}+y_{i}}{y_{i}}\right)}\,.$

Due to the space limit, we present the random Fourier embeddings (Rahimi and
Recht, 2007) for $K_{L}$ and $K_{G}$ with $\sigma=1$. We first generate
$d^{\prime}$ random vectors $\mathbf{w}_{i},i\in[d^{\prime}]$ whose
coordinates are from $N(0,1)$ for $K_{G}$ and $Lap(0,1)$ for $K_{L}$. Our
randomized mappings are:

$f(\mathbf{x})=\frac{1}{\sqrt{d^{\prime}}}\\{\sin{(\mathbf{w}_{i}^{\top}\mathbf{x})},\cos{(\mathbf{w}_{i}^{\top}\mathbf{x})}\,|\,i\in[d^{\prime}]\\}\in\mathcal{S}^{2d^{\prime}-1}\,.$

Since
$|f(\mathbf{x})^{\top}f(\mathbf{y})|\leq\|f(\mathbf{x})\|_{2}\|f(\mathbf{y})\|_{2}=1$,
the Hoeffding’s inequality guarantees: $\textrm{\bf
Pr}\left[|f(\mathbf{x})^{\top}f(\mathbf{y})-K(\mathbf{x},\mathbf{y})|\geq\delta\right]\leq
e^{-d^{\prime}\cdot\,\delta^{2}/2}\,.$ By selecting $d^{\prime}=O(\log{(n)})$,
the randomized mapping $f$ preserves well the kernel function of every pair of
points. Hence, sDBSCAN and sOPTICS on these randomized embeddings output
similar results to DBSCAN and OPTICS on the corresponding distance measures.

Complexity. For $K_{G},K_{L}$, the embedding time is $O(dd^{\prime})$. For
$K_{\chi^{2}},K_{JS}$, the embedding time is $O(d^{\prime})$ for $d^{\prime}$
random features by applying the sampling and scaling approaches (Vedaldi and
Zisserman, 2012). Empirically, the random feature construction time is
negligible compared to the sDBSCAN and sOPTICS time. As we execute random
projections on the constructed random features for each point and compute
$dist(\mathbf{x},\mathbf{y})$ using the original data, we only need a small
extra space to store random vectors $\mathbf{w}_{i}$.

###  4.5. From theory to practice

We observe that the core point $\mathbf{q}$ often falls into the high-density
area where $B_{\varepsilon}{(\mathbf{q})}$ tends to be dominated by core
points in real-world data sets. Hence, $m=O(minPts)$ suffices to identify core
points and connect them to form the density-based clustering.

We note that sDBSCAN requires $D$ random vectors whose coordinates are
randomly selected from $N(0,1)$, which requires $O(dD)$ time to process a
point. This work will use the Structured Spinners (Andoni et al., 2015) that
exploits Fast Hadamard Transform (FHT) to reduce the cost of random
projections. In particular, we generate 3 random diagonal matrices
$\mathbf{D}_{1},\mathbf{D}_{2},\mathbf{D}_{3}$ whose values are randomly
chosen in $\\{+1,-1\\}$. The random projection $\mathbf{R}\mathbf{x}$ is
simulated by the mapping
$\mathbf{x}\mapsto\mathbf{H}\mathbf{D}_{3}\mathbf{H}\mathbf{D}_{2}\mathbf{H}\mathbf{D}_{1}\mathbf{x}$
where $\mathbf{H}$ is the Hadamard matrix. With FHT, the random projection can
be simulated in ${\mathcal{O}}\left(D\log{(D)}\right)$ time and use additional
$O(D)$ extra space to store random matrices.

Figure 1. Reachability-plot dendrograms of OPTICS and sOPTICS over L2 and L1
on Mnist. While sOPTICS needs less than 30 seconds, scikit-learn OPTICS
requires 1.5 hours on L2 and 0.5 hours on L1.

A random projection-based heuristic to cluster non-core points. As sDBSCAN
focuses on identifying core points and approximating their neighborhoods, it
misclassifies border and noisy points. As the neighborhood size of detected
core points is upper bound by $2km$, sDBSCAN might suffer accuracy loss on
data sets with a significantly large number of border and noisy points. Denote
by $C$ and $\overline{C}$ the set of identified core and non-core points by
sDBSCAN, we propose a simple heuristic to classify any
$\mathbf{q}\in\overline{C}$. We will build a nearest neighbor classifier (1NN)
where training points are sampled from $C$, and scale up this classifier with
the CEOs approach (Pham, 2021, Alg. 1). We call sDBSCAN with the approximate
1NN heuristic as sDBSCAN-1NN.

In particular, for each sampled core point $\mathbf{x}\in C$, we recompute
their random projection values with the stored $D$ random vector
$\mathbf{r}_{i}$ as we do not keep these values after preprocessing. For each
non-core point $\mathbf{q}\in\overline{C}$, we retrieve the precomputed
top-$k$ closest/furthest vectors and use the projection values of $\mathbf{x}$
at these top-$k$ vectors to estimate $\mathbf{x}^{\top}\mathbf{q}$. To ensure
this heuristic does not affect sDBSCAN time where
$|C|\approx|\overline{C}|\approx n/2$, we sample $0.01n$ core points from $C$
to build the training set. Empirically, sDBSCAN time dominates this heuristic
time, and the extra space usage to store $0.01nD$ projection values is
negligible.

###  4.6. Time and space complexity

We first analyze the time complexity of the preprocessing and finding
neighborhood steps with $m=O(minPts)$. Then we discuss the time and space
complexity of sDBSCAN and sOPTICS.

Time complexity. Using FHT, the preprocessing (Alg. 3) runs in
$O\left(nD\log{(D)}+nD\log{(k)}+nD\log{(minPts)})\right)$ time since we
retrieve top-$k$ closest/furthest vectors for each $\mathbf{q}\in\mathbf{X}$,
and top-$m$ closest/furthest points for each random vector $\mathbf{r}_{i}$.
Finding the neighborhood for $n$ points (Alg. 4) runs in $O(dnk\cdot minPts)$
time since each point needs $O(k\cdot minPts)$ distance computations. For a
constant $k$, sDBSCAN runs in $O(dn\cdot minPts+nD\log{(D)})$ time.

For each point $\mathbf{q}$, sOPTICS keeps
$|\widetilde{B}_{\varepsilon}{(\mathbf{q})}|=O(k\cdot minPts)$ points and
distance values. The size of the priority queue $Q$ of sOPTICS is $O(nk\cdot
minPts)$. Therefore, for a constant $k$, sOPTICS runs in $O(dn\cdot
minPts+nD\log{(D)}+n\cdot minPts\cdot\log{(n\cdot minPts)})$. When $D=o(n)$,
both sDBSCAN and sOPTICS run in subquadratic time.

Empirically, the cost of the preprocessing step $O(nD\log{(D)})$ is much
smaller than the cost of finding neighborhood $O(dnk\cdot minPts)$ in large
data sets. This is because finding the neighborhood for each point requires
$O(k\cdot minPts)$ distance computations that need expensive random memory
access, while the cache-friendly FHT uses sequential memory access.
Fortunately, preprocessing and finding neighborhood steps are elementary to
run in parallel. Our multi-threading implementation of sDBSCAN and sOPTICS
shows a 10$\times$ speedup with 64 threads.

Space complexity. Our sDBSCAN needs $O(nk+D\cdot minPts)$ extra space to store
$O(k)$ closest/furthest vectors for each point, and $O(minPts)$ points
closest/furthest to each random vector. When $D=o(n)$, sDBSCAN’s additional
memory is negligible compared to the data size $O(nd)$. Due to the priority
queue of size $O(nk\cdot minPts)$, sOPTICS uses $O(nk+D\cdot minPts+nk\cdot
minPts)$ extra space, which is linear when $D=o(n)$, and independent on any
value of $\varepsilon$.

##  5\. Experiment

We implement sDBSCAN and sOPTICS in C++ and compile with g++ -O3 -std=c++17
-fopenmp -march=native. We conducted experiments on Ubuntu 20.04.4 with an AMD
Ryzen Threadripper 3970X 2.2GHz 32-core processor (64 threads) with 128GB of
DRAM. We present empirical evaluations on the clustering quality compared to
the DBSCAN’s clustering result and the ground truth (i.e. data labels) to
verify our claims, including:

  * •

sDBSCAN and sOPTICS can output the same results as DBSCAN and OPTICS using
significantly smaller computational resources on high-dimensional data sets.

  * •

sDBSCAN with the suggested parameter values provided by sOPTICS runs
significantly faster and achieves competitive accuracy compared to other
clustering algorithms.

  * •

Multi-threading sDBSCAN and sOPTICS run in minutes, while the scikit-learn
counterparts cannot run on million-point data sets.

Our competitors include pDBSCAN (Gan and Tao, 2017)
444https://sites.google.com/view/approxdbscan as a representative grid-based
approach, DBSCAN++ (Jang and Jiang, 2019)
555https://github.com/jenniferjang/dbscanpp and sngDBSCAN (Jiang et al., 2020)
666https://github.com/jenniferjang/subsampled_neighborhood_graph_dbscan as
representatives for sampling-based approaches. DBSCAN++ has two variants,
including DBSCAN++ with uniform initialization (called uDBSCAN++) that uses
KD-Trees to speed up the search of core points and $k$-center initialization
(called kDBSCAN++). We also compare with multi-threading scikit-learn
implementations of DBSCAN and OPTICS 777https://scikit-
learn.org/stable/modules/clustering.html. The released JAVA implementation of
random projection-based DBSCAN (Schneider and Vlachos, 2017) cannot run even
on the small Mnist data set. To demonstrate the scalability of sDBSCAN on
other distance measures, we compare it with the popular scikit-learn
$k$-means++ (Arthur and Vassilvitskii, 2007) and the result of kernel
$k$-means in (Wang et al., 2019).

We use the normalized mutual information (NMI) to measure the clustering
quality. We conduct experiments on three popular data sets: Mnist
($n=70,000,d=784$, # clusters = 10), Pamap2 ($n=1,770,131,d=51$, # clusters =
18), and Mnist8m ($n=8,100,000,d=784$, # clusters = 10). We use the class
labels as the ground truth. For Pamaps2, we discarded instances that contain
NaN values and removed the dominated class 0 corresponding to the transient
activities. We note that Mnist and Mnist8m are sparse data sets with at least
75% sparsity, while Pamap2 is dense. All results are the average of 5 runs of
the algorithms.

A note on our implementation. We use the Eigen library
888https://eigen.tuxfamily.org for SIMD vectorization on computing the
distances. Our sDBSCAN and sOPTICS are multi-threading friendly. We only add
#pragma omp parallel directive on the for loop when preprocessing and finding
the neighborhood for each point.

###  5.1. An ablation study of sOPTICS on Mnist

Figure 2. sOPTICS’s graphs on L2, cosine, $\chi^{2}$, and JS on Mnist. Each
runs in less than 3 seconds.

This subsection measures the performance of sOPTICS and scikit-learn OPTICS
with multi-threads. We show that sOPTICS can output the same OPTICS’s results
in less than 30 seconds, which is up to $180\times$ speedups over scikit-learn
OPTICS.

Comparison to scikit-learn OPTICS on L2 and L1. We use scikit-learn OPTICS to
generate the dendrogram given $minPts=50$. To select a reasonable value of
$\varepsilon$ for OPTICS to reduce the running time, we randomly sample 100
points and use the average top-100 nearest neighbor distances of these sampled
points as $\varepsilon$. Accordingly, we use $\varepsilon=1,800$ for L2 and
$\varepsilon=18,000$ for L1.

To recover OPTICS’s results, sOPTICS uses $D=2,048,k=2$ and $m=1,000$. For L2
and L1 distances, sOPTICS requires two additional parameters, including the
scale $\sigma$ and the number of embeddings $d^{\prime}$, for random Fourier
embeddings. We observe that the performance of sOPTICS is insensitive to
$\sigma$ and $d^{\prime}$, hence we simply set $\sigma=2*\varepsilon$ and
$d^{\prime}=1,024$ for our experiments.

We run both scikit-learn OPTICS and sOPTICS with 64 threads. Regarding speed,
sOPTICS needs less than 30 seconds, while OPTICS takes hours to finish. This
shows the advantages of sOPTICS in accurately finding candidates to construct
neighborhoods and efficiently utilizing multi-threading. Regarding accuracy,
sOPTICS outputs nearly the same graphs as OPTICS, as shown in Figure 1. Since
there are more valleys on L2 than L1, the clustering accuracy regarding the
ground truth using L2 will be higher than L1.

On the needs of sOPTICS on other distances. While DBSCAN on L2 is popular, the
capacity to use arbitrary distances is an advantage of DBSCAN compared to
other clustering algorithms. We use sOPTIC to visualize the cluster structure
on other distance measures. We use $D=1,024,m=minPts=50,k=5$, and set
$\varepsilon=1,800$ for L2, and $\varepsilon=0.25$ for the others. We use
$d^{\prime}=1,024$ random features and set $\sigma=2*\varepsilon$ for L2.

Figure 2 shows reachability-plot dendrograms of sOPTICS on 4 studied distance
measures. Since points belonging to a cluster have a small reachability
distance to their nearest neighbors, the number of valleys in the dendrograms
reflects the cluster structure. From Figure 2, we can predict that cosine,
$\chi^{2}$ and JS provide higher clustering quality than L2. sOPTICS on these
measures show a clear 4 valleys compared to 3 hazy valleys of L2. Importantly,
any $\varepsilon$ in the range $[0.1,0.15]$ can differentiate these 4 valleys
while it is impossible to select a specific value to separate the 3 valleys of
L2.

Note that the sOPTICS graphs on L2 of Figures 1(b) and 2(a) are slightly
different due to the smaller values of $D,m$. Hence, sOPTICS in the setting in
Figure 2 runs significantly faster. As sOPTICS graph on L1 shows an inferior
clustering quality, we do not report L1.

###  5.2. An ablation study of sDBSCAN on Mnist

This subsection measures the performance of sDBSCAN compared to scikit-learn
DBSCAN with multi-threads. We also compare sDBSCAN with recent competitors,
including pDBSCAN (Gan and Tao, 2017), DBSCAN++ (Jang and Jiang, 2019)
(uDBSCAN++ and kDBSCAN++), and sngDBSCAN (Jiang et al., 2020) with 1 thread as
their implementations do not support multi-threading.

####  5.2.1. Comparison to DBSCAN’s output on cosine distance.

Given $minPts=50$, we set $\varepsilon=0.11$ as DBSCAN returns the highest NMI
of 43% compared to the ground truth. sDBSCAN has two main parameters on cosine
distance: top-$m$ points closest/furthest to a random vector and top-$k$
closest/furthest random vectors to a point. These parameters govern the
accuracy and efficiency of sDBSCAN. We set $D=1,024$ and vary $m,k$ in the
next experiments.

Table 1. Comparison of sDBSCAN with the DBSCAN’s output on cosine distance with $\varepsilon=0.11,minPts=50$ over different $k$ and $m$ on Mnist. The scikit-learn DBSCAN runs in 71 seconds. $m$ | 50 | 100 | 200 | 400 | 1,000 | 2,000 | 2,000
---|---|---|---|---|---|---|---
$k$ | 40 | 20 | 10 | 5 | 2 | 1 | 2
NMI | 69% | 76% | 81% | 86% | 88% | 91% | 95%
Time (s) | 8.8 | 9.9 | 10.5 | 11.1 | 12.1 | 12.6 | 23

Accuracy and efficiency of sDBSCAN. For sDBSCAN, we vary
$k=\\{40,20,\ldots,1\\}$, $m=\\{50,100,\ldots,2,000\\}$ such that it computes
nearly the same $2km$ distances for each point. Table 1 shows the performance
of multi-threading sDBSCAN on DBSCAN’s outputs with
$\varepsilon=0.11,minPts=50$. We can see that sDBSCAN can recover DBSCAN’s
result with larger $m$. These findings justify our theoretical result as
larger $m$ increases the chance of examining all points in the set $S_{i}$ and
$R_{i}$ corresponding to the random vector $\mathbf{r}_{i}$, increasing the
chance to recover the DBSCAN’s output.

In the last column with $m=2,000$, sDBSCAN with $k=2$ achieves NMI of 95% but
runs 2 times slower than $k=1$ since it nearly doubles the candidate size.
sDBSCAN with all configurations runs at least $3\times$ faster than scikit-
learn DBSCAN. This presents the advantages of sDBSCAN in accurately finding
candidates to find core points and efficiently utilizing the multi-threading
architecture.

sDBSCAN’s parameter setting. Given $m\geq minPts$ and $k$, each point needs at
most $2km$ distance computations due to the duplicates on top-$m$ candidates
corresponding to $2k$ investigated random vectors. As a larger $k$ leads to
more duplicates among $2km$ candidates, given a fixed budget $B=2km$, Table 1
shows that $k=1,m=B/2$ has higher accuracy but significantly higher running
time than $k=k_{0}>1,m=B/2k_{0}$.

Table 2. Running time of sDBSCAN components in seconds with $D=1,024,k=5,m=minPts=50,\varepsilon=0.11$ on Mnist. # Threads | Preprocess | Find core points | Cluster | Total
---|---|---|---|---
1 thread | 1.424 | 7.745 | 0.001 | 9.198
64 threads | 0.160 | 0.700 | 0.001 | 0.862

While larger $m$ and $D$ tend to increase the accuracy of sDBSCAN, they affect
space and time complexity. Since we often set $D=1,024$ to ensure Lemma 4.1
holds, and the memory resource is limited due to large data sets, we set
$m=minPts=50$ and $k=\\{5,10\\}$ for most experiments. Compared to the ground
truth, this setting does not affect the accuracy of sDBSCAN but uses
significantly less computational resources than other configurations.

Figure 3. NMI comparison of DBSCAN variants on cosine, L2, L1, JS distances on Mnist over suggested ranges of $\varepsilon$ by sOPTICS in Figure 2. pDBSCAN and scikit-learn have identical results. As the sampling-based DBSCAN implementations only support L2 and cosine distances, we report our implemented sngDBSCAN on L1 and JS. Table 3. The NMI on the best $\varepsilon\in[0.1,0.2]$ and running time comparison of DBSCAN variants using cosine distance with $minPts=50$ on Mnist. sDBSCAN and scikit-learn DBSCAN run in multi-threading while the others are on a single thread. Alg. | sDBSCAN | scikit DBSCAN | sDBSCAN1 | uDBSCAN++ | kDBSCAN++ | sngDBSCAN | pDBSCAN
---|---|---|---|---|---|---|---
NMI | 43% | 43% | 43% | 43% | 7% | 33% | 43%
Time | 0.9s | 86s | 8.8s | 67s | 87s | 18s |  $1.85$ hours
$\varepsilon$ | 0.14 | 0.11 | 0.14 | 0.18 | 0.2 | 0.15 | 0.11

Running time of sDBSCAN’s components. Given $\varepsilon=0.11$, $m=minPts=50$,
$k=5$, Table 2 shows the running time of sDBSCAN components on 1 and 64
threads. On 1 thread, we can see that finding neighborhoods is the primary
computational bottleneck while forming clusters is negligible. This is due to
the expensive random access operations to compute $2km$ distances for each
point. As the main components of sDBSCAN, including preprocessing (Alg. 3) and
finding neighborhoods (Alg. 4) can be sped up with multi-threading, we achieve
nearly $10\times$ speedup with 64 threads. We also observe that the
construction time of the randomized embeddings to support L2, L1, $\chi^{2}$,
and JS is similar to the preprocessing time and is negligible to that of
finding neighborhoods.

####  5.2.2. Comparison to the ground truth on several distances.

We conduct experiments to measure the clustering accuracy regarding the class
labels as the ground truth. We fix $minPts=50$, and select a suitable range
values of $\varepsilon$ based on the sOPTICS’s graphs. For example, we select
5 different values $\varepsilon$ on $[0.1,0.15]$ for $\chi^{2}$ and JS, and
report the representative result of JS due to the similar outcomes.

sDBSCAN uses $D=1,024$, $m=50$, $k=5$, and hence computes at most $2km=1000$
distances for each point. For DBSCAN++ variants and sngDBSCAN, we set the
sampling probability $p=0.01$ so that they compute $pn=700$ distances for each
point. pDBSCAN uses $\rho=0.001$ as we observe that changing $\rho=0.0001$
does not affect its running time. We also found that the brute force for range
search queries is the fastest method for exact DBSCAN on Mnist.

Figure 3 shows NMI scores over a wide range of $\varepsilon$ on 4 different
distances. The grid-based approach pDBSCAN only supports L2 and its accuracy
is identical to scikit-learn on cosine and L2. sDbscan is superior on all 4
supported distances, except L2 when compared to uDBSCAN++. While sDBSCAN
reaches DBSCAN’s accuracy of NMI 43% on cosine and JS, sngDBSCAN gives lower
accuracy on all 4 distances. While uDBSCAN++ gives at most 32% NMI on L2 and
cosine, kDBSCAN++ does not provide a meaningful result on the studied range
values of $\varepsilon$. L2 and L1 distances show inferior performance on
clustering compared to cosine and JS, as can be predicted from their sOPTICS
graphs in Figure 2.

Comparison to the ground truth on cosine distance over a wider range of
$\varepsilon$. Table 3 summarizes the performance of studied DBSCAN variants
on the best $\varepsilon\in[0.1,0.2]$ with cosine distance. sDBSCAN has two
variants: multi-threading and single thread (sDBSCAN1). On 1 thread, sDBSCAN1
runs nearly $2\times,8\times$ and $10\times$ faster than sngDBSCAN, uDBSCAN++
and kDBSCAN++, respectively. This is due to the significant overhead of the
KD-Tree indexes used by uDBSCAN++ and $k$-center initialization of kDBSCAN++.
Though pDBSCAN shares the same NMI with scikit-learn DBSCAN, it is not
feasible for high-dimensional data sets. It takes nearly 2 hours to finish,
while the others need less than 1.5 minutes.

sDBSCAN achieves the same NMI of 43% with DBSCAN. Its multi-threading sDBSCAN
runs in less than 1 second, which is $96\times$ faster than multi-threading
scikit-learn. While sDBSCAN uses the range of $\varepsilon$ suggested by
sOPTICS, sampling-based approaches have to explore a much wider range for
$\varepsilon$ to recover DBSCAN’s accuracy.

Figure 4. sOPTICS’s graphs on L1, L2 and cosine distances on Pamap2. Each runs
in less than 2 minutes. Figure 5. sOPTICS’s graphs on L2, cosine, $\chi^{2}$,
and JS distances on Mnist8m. Each runs in less than 11 minutes.

###  5.3. Comparison on Pamap2 and Mnist8m

This subsection compares the performance of sDBSCAN and sOPTICS with other
clustering variants on million-point Pamap2 and Mnist8m data sets. scikit-
learn OPTICS and DBSCAN cannot finish due to the memory constraint, and the
grid-based pDBSCAN cannot finish after 2 hours. As our implemented sngDBSCAN
runs significantly faster than (Jiang et al., 2020) and supports multi-
threading, we use our implementation for comparison. We set $p=1$ for
sngDBSCAN to recover the exact DBSCAN. sDBSCAN and sOPTICS use
$k=10,m=minPts=50$. DBSCAN++ variants and sngDBSCAN use $p=0.01$ on Pamap2 and
$p=0.001$ on Mnist8m.

####  5.3.1. sOPTICS graphs on Pamap2 and Mnist8m.

Figure 6. NMI comparison of DBSCAN variants on L1, L2 and cosine on Pamap2 on
suggested ranges of $\varepsilon$ by sOPTICS in Figure 4.

We use the average top-100 nearest neighbor distances of 100 sampled points to
select a suitable $\varepsilon$ for sOPTICS. Figure 4 and 5 show sOPTICS’s
graphs of Pamap2 and Mnist8m with $minPts=50$. As Pamap2 contains negative
features, we only run on cosine, L2, and L1 distances. sOPTICS uses $D=1,024$,
$\sigma=2*\varepsilon$, $d^{\prime}=1,024$ runs in less than 2 minutes and 11
minutes on Pamap2 and Mnist8m, respectively. Both figures show that L2 is less
relevant than the other distances as it does not show clear valley areas. This
reflects the need to use other distance measures rather than L2 for density-
based clustering to achieve reasonable performance.

####  5.3.2. Comparison to the ground truth on Pamap2.

From the sOPTICS graphs, we select relevant range values for $\varepsilon$ to
run DBSCAN variants. Figure 6 shows the NMI scores of studied algorithms on
such ranges. On these ranges of $\varepsilon$, the NMI peak of sDBSCAN is
consistently higher than that of sngDBSCAN but is 5% lower than DBSCAN on L1
and L2. While sDBSCAN achieves the peak of NMI at the investigated ranges of
$\varepsilon$ on 3 distances, the performance of the others is very different
on cosine. We found that DBSCAN with $\varepsilon=0.005$ returns NMI 47% but
offers only 37% NMI on $\varepsilon=0.01$. This explains the reliability of
sOPTICS on guiding the parameter setting for sDBSCAN and the difficulty in
selecting relevant $\varepsilon$ for other DBSCAN variants without any visual
tools.

Table 4. The NMI on the best $\varepsilon$ and running time comparison on cosine and L1 distances on Pamap2. The upper 3 algorithms run in multi-threading with $10\times$ speedup compared to 1 thread while the lower ones use 1 thread. Algorithms | Cosine ($\varepsilon\in[0.005,0.05]$) | L1 ($\varepsilon\in[30,80]$)
---|---|---
NMI | Time | $\varepsilon$ | NMI | Time | $\varepsilon$
DBSCAN | 47% | 28.4 min | 0.005 | 50% | 29.3 min | 40
sDBSCAN | 34% | 0.2 min | 0.04 | 46% | 0.3 min | 60
sngDBSCAN | 42% | 2.8 min | 0.015 | 40% | 2.7 min | 50
uDBSCAN++ | 46% | 3 min | 0.015 | – | – | –
kDBSCAN++ | 39% | 13.4 min | 0.05 | – | – | –
$k$-mean++ ($k=18$) | 36% | 0.4 min | – | – | – | –
Figure 7. NMI comparison of DBSCAN variants on L2, cosine, $\chi^{2}$, and JS distances and kernel $k$-means on Mnist8m over suggested ranges of $\varepsilon$ by sOPTICS in Figure 5. Table 5. The NMI on the best $\varepsilon$ and running time comparison of multi-threading DBSCAN variants on L2, cosine, $\chi^{2}$, and JS distances on Mnist8m. Kernel $k$-means ($k=10$) (Wang et al., 2019) runs in 15 minutes on a supercomputer of 32 nodes and achieves NMI 41%. Algorithms | L2 ($\varepsilon\in[1100,1500]$) | Cosine ($\varepsilon\in[0.1,0.2]$) |  $\chi^{2}$ ($\varepsilon\in[0.1,0.2]$) | JS ($\varepsilon\in[0.1,0.2]$)
---|---|---|---|---
NMI | Time | $\varepsilon$ | NMI | Time | $\varepsilon$ | NMI | Time | $\varepsilon$ | NMI | Time | $\varepsilon$
sDBSCAN-1NN | 36% | 8 min | 1400 | 37% | 14 min | 0.16 | 38% | 15 min | 0.17 | 38% | 15 min | 0.15
sDBSCAN | 25% | 7 min | 1350 | 32% | 8 min | 0.16 | 32% | 10 min | 0.17 | 31% | 10 min | 0.15
sngDBSCAN ($p=0.001$) | 22% | 43 min | 1150 | 26% | 42 min | 0.16 | 28% | 64 min | 0.15 | 27% | 64 min | 0.17

As L2 is inferior to L1 and cosine on sampling-based DBSCAN, Table 4 reports
the NMI scores and running time of studied algorithms on L1 and cosine
distances over a larger range of $\varepsilon$. While sDBSCAN shows a low NMI
on cosine, its accuracy is 45% on L1, which is higher than sngDBSCAN on both
cosine and L1. As sngDBSCAN uses $p=0.01$, each point will compute $np\sim
17,700$ distances compared to $2km=1000$ of sDBSCAN. Hence, sDBSCAN runs up to
14$\times$ faster than sngDBSCAN. On L1, sDBSCAN is nearly $100\times$ faster
than DBSCAN. By changing $k=5,m=200$, sDBSCAN reaches 48% NMI on L1 and still
runs in less than 1 minute. Compared to $k$-mean++, multi-threading sDBSCAN
runs faster and offers significantly higher NMI with L1. We emphasize that the
advantage of multi-threading sDBSCAN comes from its simplicity, as it is
effortless engineering to run sDBSCAN on multi-threads.

Among sampling-based approaches, uDBSCAN++ gives the highest NMI score of 46%,
while kDBSCAN++ is very slow. kDBSCAN++ runs approximately $5\times$ slower
than uDBSCAN due to the overhead of $k$-center initialization and the
efficiency of KD-Trees on Pamap2 with $d=51$. In general, sDBSCAN provides
competitive clustering accuracy and runs significantly faster than other
DBSCAN variants. Like Mnist, our sOPTICS on Pamap2 runs in less than 2
minutes, even faster than any sampling-based implementations.

####  5.3.3. Comparison to the ground truth on Mnist8m.

As Mnist8m is non-negative, we conduct experiments on cosine, L2, and L1,
$\chi^{2}$, and JS distances. Similar to Mnist, sOPTICS graphs show L1 is
inferior, so we do not report L1 here.

uDBSCAN++ and kDBSCAN++ with $p=0.001$ could not finish after 3 hours. It is
not surprising as our multi-threading sngDBSCAN runs in nearly 1 hour, and
single thread sngDBSCAN is at least $4\times$ faster than DBSCAN++ variants on
Mnist as shown in Table 3. As we cannot run scikit-learn $k$-means++, we use
the result of 41% NMI given by a fast kernel $k$-means (Wang et al., 2019)
running on a supercomputer with 32 nodes, each of which has two 2.3GHz 16-core
(32 threads) Haskell processors and 128GB of DRAM. This configuration of a
single node is similar to our conducted machine.

From the sOPTICS graphs, we select 5 specific values on the relevant range of
$\varepsilon$, including $\\{1200,\ldots,1400\\}$ for L2,
$\\{0.14,\ldots,0.18\\}$ for cosine, $\chi^{2}$, and $\\{0.12,\ldots,0.16\\}$
for JS. Figure 7 shows the NMI scores of 3 algorithms, sDBSCAN-1NN with 1-NN
heuristic described in Subsection 4.5, sDBSCAN, sgnDBSCAN, and kernel
$k$-means on Mnist8m. sDBSCAN-1NN shows superiority among DBSCAN variants,
achieving 10% and 5% higher than sngDBSCAN and sDBSCAN, respectively, at the
peak of NMI on 4 studied measures. sDBSCAN consistently gives higher accuracy
than sngDBSCAN with the most significant gap of 5% on $\chi^{2}$ and cosine.

Table 5 summarizes the performance of multi-threading sDBSCAN-1NN, sDBSCAN,
and sngDBSCAN, including the NMI score on the best $\varepsilon$ and the
running time, on L2, cosine, $\chi^{2}$, and JS. sDBSCAN-1NN runs in at most
15 minutes and returns the highest NMI among DBSCAN variants with a peak of
38% NMI on $\chi^{2}$ and JS. We emphasize that kernel $k$-means with Nyström
approximation (Wang et al., 2019, Table 4) also needs 15 minutes on a
supercomputer and gives 41% NMI.

sDBSCAN runs faster than sDBSCAN-1NN as it does not assign labels to non-core
points, and still achieves significantly higher NMI scores than sngDBSCAN on
all 4 studied distances. Among 4 distances, L2 shows lower accuracy but runs
faster than $\chi^{2}$ and JS due to the faster distance computation. sDBSCAN
runs $6.4\times$ faster than sngDBSCAN, which is justified by the number of
distance computations $np=8,100$ of sngDBSCAN compared to $2km=1000$ of
sDBSCAN. As sDBSCAN-1NN samples $0.01n$ core points to build the approximate
1NN classifier, the running time overhead of this extra step is smaller than
sDBSCAN’s time.

##  6\. Conclusion

The paper presents sDBSCAN for density-based clustering, and sOPTICS for
interactive exploration of density-based clustering structure for high-
dimensional data. By leveraging the neighborhood preservation of random
projections, sDBSCAN preserves the DBSCAN’s output with theoretical
guarantees. We also extend our proposed algorithms to other distance measures
to facilitate density-based clustering on many applications. Empirically, both
sDBSCAN and sOPTICS are very scalable, run in minutes on million-point data
sets, and provide very competitive accuracy compared to other clustering
algorithms. We hope that the results of our work will stimulate research works
that leverage lightweight indexing for ANNS to scale up density-based
clustering in high dimensions.

## References

  * (1)
  * Ahle et al. (2017) Thomas D. Ahle, Martin Aumüller, and Rasmus Pagh. 2017\.  Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. In _SODA_. 239–256.
  * Andoni et al. (2015) Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015\.  Practical and Optimal LSH for Angular Distance. In _NIPS_. 1225–1233.
  * Andoni et al. (2018) Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshteyn. 2018\.  Approximate Nearest Neighbor Search in High Dimensions.  _CoRR_ abs/1806.09823 (2018).
  * Ankerst et al. (1999) Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. 1999.  OPTICS: Ordering Points To Identify the Clustering Structure. In _SIGMOD_. 49–60.
  * Arthur and Vassilvitskii (2007) David Arthur and Sergei Vassilvitskii. 2007.  k-means++: the advantages of careful seeding. In _SODA_. 1027–1035.
  * Arya et al. (2010) Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. 2010\.  A Unified Approach to Approximate Proximity Searching. In _ESA_ , Vol. 6346. 374–385.
  * Campello et al. (2020) Ricardo J. G. B. Campello, Peer Kröger, Jörg Sander, and Arthur Zimek. 2020.  Density-based clustering.  _WIREs Data Mining Knowl. Discov._ 10, 2 (2020).
  * Chazelle et al. (2008) Bernard Chazelle, Ding Liu, and Avner Magen. 2008.  Approximate range searching in higher dimension.  _Comput. Geom._ 39, 1 (2008), 24–29.
  * David and Galambos (1974) H. A. David and J. Galambos. 1974.  The Asymptotic Theory of Concomitants of Order Statistics.  _Journal of Applied Probability_ 11, 4 (1974), 762–770.
  * de Berg et al. (2019) Mark de Berg, Ade Gunawan, and Marcel Roeloffzen. 2019\.  Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces.  _Int. J. Comput. Geom. Appl._ 29, 1 (2019), 21–47.
  * Dhillon et al. (2004) Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. 2004\.  Kernel k-means: spectral clustering and normalized cuts. In _SIGKDD_. 551–556.
  * Erickson (1995) Jeff Erickson. 1995\.  On the relative complexities of some geometric problems. In _CCCG_. 85–90.
  * Esfandiari et al. (2021) Hossein Esfandiari, Vahab S. Mirrokni, and Peilin Zhong. 2021\.  Almost Linear Time Density Level Set Estimation via DBSCAN. In _AAAI_. 7349–7357.
  * Ester et al. (1996) Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996.  A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In _KDD_. 226–231.
  * Gan and Tao (2017) Junhao Gan and Yufei Tao. 2017.  On the Hardness and Approximation of Euclidean DBSCAN.  _ACM Trans. Database Syst._ 42, 3 (2017), 14:1–14:45.
  * Huang and Ma (2023) Xiaogang Huang and Tiefeng Ma. 2023.  Fast Density-Based Clustering: Geometric Approach.  _Proc. ACM Manag. Data_ 1, 1 (2023), 58:1–58:24.
  * Impagliazzo et al. (2001) Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001\.  Which Problems Have Strongly Exponential Complexity?  _J. Comput. Syst. Sci._ 63, 4 (2001).
  * Jang and Jiang (2019) Jennifer Jang and Heinrich Jiang. 2019.  DBSCAN++: Towards fast and scalable density clustering. In _ICML_. 3019–3029.
  * Jiang (2017) Heinrich Jiang. 2017\.  Density Level Set Estimation on Manifolds with DBSCAN. In _ICML_ , Vol. 70. 1684–1693.
  * Jiang et al. (2020) Heinrich Jiang, Jennifer Jang, and Jakub Lacki. 2020.  Faster DBSCAN via subsampled similarity queries. In _NeurIPS_.
  * Karger (1999) David R. Karger. 1999\.  Random Sampling in Cut, Flow, and Network Design Problems.  _Math. Oper. Res._ 24, 2 (1999), 383–413.
  * Kumar and Reddy (2016) K. Mahesh Kumar and A. Rama Mohan Reddy. 2016.  A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method.  _Pattern Recognit._ 58 (2016), 39–48.
  * Mai et al. (2016) Son T. Mai, Ira Assent, and Martin Storgaard. 2016.  AnyDBC: An Efficient Anytime Density-based Clustering Algorithm for Very Large Complex Datasets. In _SIGKDD_. ACM, 1025–1034.
  * Matousek (1994) Jirí Matousek. 1994\.  Geometric Range Searching.  _ACM Comput. Surv._ 26, 4 (1994), 421–461.
  * Pham (2021) Ninh Pham. 2021\.  Simple Yet Efficient Algorithms for Maximum Inner Product Search via Extreme Order Statistics. In _KDD_. 1339–1347.
  * Pham and Liu (2022) Ninh Pham and Tao Liu. 2022\.  Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search. In _NeurIPS_.
  * Rahimi and Recht (2007) Ali Rahimi and Benjamin Recht. 2007.  Random Features for Large-Scale Kernel Machines. In _NIPS_. 1177–1184.
  * Schneider and Vlachos (2017) Johannes Schneider and Michail Vlachos. 2017.  Scalable density-based clustering with quality guarantees using random projections.  _Data Min. Knowl. Discov._ 31, 4 (2017), 972–1005.
  * Schubert et al. (2017) Erich Schubert, Jörg Sander, Martin Ester, Hans-Peter Kriegel, and Xiaowei Xu. 2017\.  DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN.  _ACM Trans. Database Syst._ 42, 3 (2017), 19:1–19:21.
  * Shi and Malik (2000) Jianbo Shi and Jitendra Malik. 2000.  Normalized Cuts and Image Segmentation.  _IEEE Trans. Pattern Anal. Mach. Intell._ 22, 8 (2000), 888–905.
  * Vedaldi and Zisserman (2012) Andrea Vedaldi and Andrew Zisserman. 2012.  Efficient Additive Kernels via Explicit Feature Maps.  _IEEE Trans. Pattern Anal. Mach. Intell._ 34, 3 (2012), 480–492.
  * Viswanath and Babu (2009) P. Viswanath and V. Suresh Babu. 2009.  Rough-DBSCAN: A fast hybrid density based clustering method for large data sets.  _Pattern Recognit. Lett._ 30, 16 (2009), 1477–1488.
  * Wainwright (2019) Martin J. Wainwright. 2019\.  _Basic tail and concentration bounds_.  Cambridge University Press, 21–57.
  * Wang et al. (2019) Shusen Wang, Alex Gittens, and Michael W. Mahoney. 2019\.  Scalable Kernel K-Means Clustering with Nyström Approximation: Relative-Error Bounds.  _J. Mach. Learn. Res._ 20 (2019), 12:1–12:49.
  * Williams and Yu (2014) Ryan Williams and Huacheng Yu. 2014.  Finding orthogonal vectors in discrete structures. In _SODA_. 1867–1877.

##  Appendix A Random kernel features

We first show empirical results on random kernel mappings that facilitate
sDBSCAN and sOPTICS on L1, L2, $\chi^{2}$, and JS distance. We use Pamap2 for
L1 and L2 as it contains negative values and Mnist for $\chi^{2}$ and JS as it
does not contain negative values.

###  A.1. L1 and L2 on Pamap2

We carry out experiments to evaluate the sensitivity of the parameter $\sigma$
used on random kernel mappings on L1 and L2. We fix
$k=10,m=minPts=50,D=1024,d^{\prime}=1024$ and vary $\sigma$ for L1 and L2.
Figure 8 shows the accuracy of sDBSCAN on the recommended range of
$\varepsilon$ by sOPTICS graphs with $\sigma=\\{50,100,200,400$ for L1 on
Figure 12 and $\sigma=\\{20,40,80,160\\}$ for L2 on Figure 13.

Figure 8. sDBSCAN’s NMI on L1 and L2 with various $\sigma$ on Pamaps with
$k=10,m=50$. Each runs in less than 20 seconds. Figure 9. sDBSCAN’s NMI on L1
and L2 with various $\sigma$ on Pamaps with $k=10,m=50$. Each runs in less
than 20 seconds. Figure 10. sDBSCAN’s NMI on L1 with various $k,m$ on Pamaps.

While L1 provides 46% NMI, higher than just 40% NMI by L2, the setting
$\sigma=2\varepsilon$ reaches the peak of NMI for both L1 and L2. For example,
sDBSCAN at $\varepsilon=50,\sigma=100$ reaches NMI 46% for L1. sDBSCAN at
$\varepsilon=15,\sigma=20$ and $\varepsilon=21,\sigma=40$ reach NMI of 40% for
L2. Also, the performance of sDBSCAN is not sensitive to the value $\sigma$,
especially with the guide of sOPTICS graphs. For example on L2 as shown in
Figure 13, $\sigma=160$ suggests the suitable range $[40,50]$ while
$\sigma=80$ shows $[30,40]$. The best values of $\varepsilon$ of these two
$\sigma$ values are clearly on these ranges, as shown in Figure 8(b). This
observations appear again on $\sigma=\\{20,40\\}$ for the range of $[10,20]$
and $[20,30]$, respectively.

Figure 11. sOPTICS’s graphs on $\chi^{2}$ and JS with $d^{\prime}=\\{3d,5d\\}$
on Mnist with $k=5,m=50$. Each runs in less than 3 seconds. Figure 12.
sOPTICS’s graphs on L1 with various $\sigma$ on Pamaps with $k=10,m=50$. Each
runs in less than 2 minutes. Figure 13. sOPTICS’s graphs on L2 with various
$\sigma$ on Pamaps with $k=10,m=50$. Each runs in less than 2 minutes.

###  A.2. $\chi^{2}$ and JS on Mnist

We carry out experiments to evaluate the sensitivity of the parameter
$d^{\prime}$ used on random kernel mappings on $\chi^{2}$ and JS. We fix
$k=5,m=minPts=50,D=1024$ and vary $d^{\prime}$. We note that (Vedaldi and
Zisserman, 2012) approximates $\chi^{2}$ and JS distance using the sampling
approach, hence we set the sampling interval as 0.4, as suggested on scikit-
learn 999https://github.com/scikit-learn/scikit-
learn/blob/5c4aa5d0d/sklearn/kernel_approximation.py. We also note that
$d^{\prime}$ should be set as $(2l+1)d$ for $l\in\mathbb{N}$. Hence, we set
$d^{\prime}=\\{3d,5d\\}$ in our experiment.

Figure 11 shows sOPTICS graphs of $\chi^{2}$ and JS on
$d^{\prime}=\\{3d,5d\\}$. They are very similar to the sOPTICS graphs on
$d^{\prime}=d$ where the range of $\varepsilon$ should be in $[0.15,0.2]$ for
$\chi^{2}$ and $[0.13,0.18]$ for JS. Therefore, we can see that sDBSCAN with
such a recommended range of $\varepsilon$ will reach the peak of accuracy.

Figure 9 shows that sDBSCAN reaches the peak at $\varepsilon=0.16$ with
$\chi^{2}$ and $\varepsilon=0.14$ with JS. Using $d^{\prime}=5d$ slightly
increases the accuracy compared to $d^{\prime}=d$ though it is not significant
on JS. Both measures offer the highest accuracy with 45% NMI.

##  Appendix B Sensitivities of k, m

We carry out experiments on Pamap2 using L1 to study the performance of
sDBSCAN on various values of $k,m$. We fix $\sigma=200,D=1024$ and consider
the range of $\varepsilon\in[30,80]$. As increasing $k,m$ will increase the
memory and running time of sDBSCAN, we first fix $k=\\{5,10\\}$ and then
increase $m=\\{50,100,200,400\\}$.

Figure 10 shows that for a fix $k$, increasing $m$ slightly increases the
accuracy of sDBSCAN. In particular, sDBSCAN with $m=400$ at $\varepsilon=50$
reaches the accuracy of the exact DBSCAN of 50% NMI. Regarding the time,
sDBSCAN with $m=400$ needs 1.5 minutes and xxx mins for $k=5$ and $k=10$,
respectively, which is significantly faster than 29.3 minutes required by the
exact DBSCAN.

##  Appendix C Neighborhood size minPts = 100

We present experiments on the setting of $minPts=100$. We follow the same
procedure that plots sOPTICS graphs first and use them to select the relevant
range values of $\varepsilon$. We all use $k=10,m=100,D=1024$ for Pamap2 and
Mnist8m.

###  C.1. Pamap2

Figure 14 shows sOPTICS graphs on Pamap2 with L1, L2, and cosine distances
where we use $\sigma=200$ for L1, and $\sigma=20$ for L2. It shows again that
L2 is inferior than L1 and cosine distances. Figure 15 shows the accuracy of
sDBSCAN compared to other competitors on Pamap2 with studied distances over
the range of $\varepsilon$ suggested by their corresponding sOPTICS graphs.

It is clear that sDBSCAN reaches the highest NMI at the suggested range of
$\varepsilon$ by their sOPTICS graphs. In contrast, sampling-based approaches
have to investigate a much wider range of $\varepsilon$ to achieve good
performance. We observe that the performance of sDBSCAN is stable regarding
$minPts$ though a larger $minPts$ requires larger $m$ which increases the
running time. Each instance of sDBSCAN runs in 0.5 minutes, which is
significantly faster than 3 minutes by uDBSCAN++ and 13.4 minutes by
kDBSCAN++. sDBSCAN shows the advantage of running on many distance measures,
which leads to the highest of 48% of NMI of L1. In contrast, uDBSCAN++
achieves the highest of 46% of NMI among cosine and L2 distances.

Figure 14. sOPTICS’s graphs on L1, L2, cosine on Pamap2 with $k=10,m=100$.
Each runs in less than 5 minutes. Figure 15. sDBSCAN’s NMI on L1, L2, and
cosine on Pamap2 with $k=10,m=100$. Figure 16. sOPTICS’s graphs on L2, cosine,
$\chi^{2}$, and JS distances on Mnist8m with $k=10,m=100$. Each runs in less
than 20 minutes. Figure 17. sDBSCAN’s NMI on L2, cosine, $\chi^{2}$, and JS on
Mnist8m with $k=10,m=100$.

###  C.2. Mnist8m

Figure 16 shows sOPTICS graphs on Mnist8m with L2, cosine, $\chi^{2}$ and JS
distances where we use $\sigma=4000$ for L2, and $d^{\prime}=d$ on $\chi^{2}$
and JS. It shows the advantages of sDBSCAN on supporting many distances and
predicts that cosine, $\chi^{2}$ and JS provide higher accuracy than L2.

Figure 17 shows the accuracy of sDBSCAN variants compared to other competitors
on Mnist8m with studied distances over the range of $\varepsilon$ suggested by
their corresponding sOPTICS graphs. We consider sDBSCAN-1NN with the
approximation 1NN heuristic to cluster border and noisy points detected by
sDBSCAN. It shows again that sDBSCAN variants outperform sngDBSCAN on all
studied distances. sDBSCAN-1NN on a single computer nearly reaches the
accuracy of kernel $k$-means (Wang et al., 2019). Regarding the speed, each
instance of sDNSCAN-1NN runs in less than 15 minutes, which is the time
requirement for kernel $k$-means on a supercomputer.