Scalable DBSCAN with Random Projections
Authors: HaoChuan Xu
Ninh Pham
Venue: NeurIPS 2024 poster (2024)
Keywords: Density-based clustering
random projections
extreme order statistics
Primary area: evaluation
TL;DR: Scale up DBSCAN and OPTICS with random projections

Abstract: We present sDBSCAN, a scalable density-based clustering algorithm in high dimensions with cosine distance. sDBSCAN leverages recent advancements in random projections given a significantly large number of random vectors to quickly identify core points and their neighborhoods, the primary hurdle of density-based clustering. Theoretically, sDBSCAN preserves the DBSCAN’s clustering structure under mild conditions with high probability. To facilitate sDBSCAN, we present sOPTICS, a scalable visual tool to guide the parameter setting of sDBSCAN. We also extend sDBSCAN and sOPTICS to L2, L1, χ2, and Jensen-Shannon distances via random kernel features. Empirically, sDBSCAN is significantly faster and provides higher accuracy than competitive DBSCAN variants on real-world million-point data sets. On these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-learn counterparts and other clustering competitors demand several hours or
cannot run on our hardware due to memory constraints. Our code is available at https://github.com/NinhPham/sDbscan.

Scalable DBSCAN with Random Projections
HaoChuan Xu School of Computer Science University of Auckland
Ninh Pham
School of Computer Science
University of Auckland ninh www.ppphaaaaaaaaaeaa nz
hxu612@aucklandume acc. ac nz
Abstract
We present sDBSCAN, a scalable density-based clustering algorithm in high dimen- sions with cosine distance. sDBSCAN leverages recent advancements in random projections given a significantly large number random vectors to quickly identify core points and their neighborhoods, the primary hurdle of density-based -based clustering. Theoretically. sDBSCAN preserves the DBSCAN's clustering structure under mild conditions with high probability. To facilitate sDBSCAN, we present sOPTICS, a scalable visual tool to guide the parameter setting of sDBSCAN. We also extend sDBSCAN and sOPTICS to I.2, L1, x2, and Jensen-Shannon distances via random kernel features. Empirically, sDBSCAN is significantly faster and provides higher accuracy than competitive DBSCAN variants real-world million-point data sets. On these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-learn counterparts and other clustering competitors demand several hours cannot run our hardware due to memory constraints. Our code is available at https:://itthne com/ cwm/Ninh NinhPham /DDbscan
1 Introduction
DBSCAN [T] is one of the most fundamental clustering algorithms with many applications in data mining and machine learning [2]. has been featured several data analysis tool kits, including scikit-leam in Python, ELKI in Java, and CRAN in R. In principle, DBSCAN connects neighboring points from nearby high-density areas to form cluster where the high density is decided by sufficiently large number of points in the neighborhood. DBSCAN is parameterized by (c, min where is the distance threshold govern the point's neighborhood and to connect nearby areas; and minPls is the density threshold to identify high-density areas.
Apart from other popular clustering algorithms, including k-means variants 4 and spectral clustering (5). DBSCAN is non-parametric. It can find the number of clusters, detect arbitrary clustering shapes and sizes, and work on any arbitrary distance measure.
Given distance measure, DBSCAN has two primary steps, including (1) finding the e-ncighborhood (i.e. points within radius e) for every point discover the density areas surrounding the point and (2) forming the cluster by connecting neighboring points. The first step is the main bottleneck as finding n-neighborhoods for all points requires worst-case O(n2) time for a data of points in high-dimensions 77. This limits the applications of DBSCAN on modern million-pon point data sets.
Another hurdle of PissPPss-D is the choice of which highly depends on the data distribution and distance measure. While minPls easier to set for smoothing the density estimate, DBSCAN's outputs are susceptible to especially in high dimensions where the range of is very sensitive. For instance, when applying DBSCAN with cosine distance on the Pamap2 data set, changing by just 0,005 can diminish the clustering accuracy by 10%. In practice, ones often need to compute an e-neighborhood for each point given a large value of s, and use them to explore the quality of clustering structures smaller values of Using large causes Onn²) memory bottleneck
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

as the e-neighborhood of one point might need O(n) space. We observe that on our hardware, such memory constraint is the primary hurdle limiting the current scikit-learn implementation on million-point data sets. Therefore, it is essential to not only develop scalable versions of DBSCAN, but also to provide feasible tools to guide its parameter setting on large-scale 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 in exact and approximate manners.
9 10] partition the data set into several subsets and iteratively extract and refine clusters from these subsets by performing additional e e-neighborhood queries on a small set of important points. Other grid-based methods L2 6 [ efficiently identify neighborhood areas by confining the neighbor search exclusively to neighboring grids. However, these approaches still have worst-case quadratic time their complexity grows exponentially to the dimension. Random projections [12 [3 have been used to build grid-based or tree-based indexes for faster approximate e-neighborhoods on L2, though they do not offer theoretical guarantees on the clustering accuracy.
Exact DBSCAN approaches 8
Instead of finding the e-neighborhood for every point, DBSCAN++ [44 finds e-neighborhoods for a subset of random points chosen through uniform sampling or k-centering methods. SngDBSCAN [TS] approximates the e-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 [16] that requires many strong assumptions on the data distribution. Moreover, selecting suitable parameter values (especially for E) for sampling-base based approaches is challenging due to the nature of sampling.
DBSCAN's parameter setting guideline with OPTICS. OPTICS [17] attempts to mitigate the problem of selecting relevant E 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 broad range of E, which indicates relevant range of for DBSCAN.
Like DBSCAN, OPTICS requires the E-neighborhood for every point, leading to an ((n)) time complexity. In practice, OPTICS often needs large E to discover clustering structures on wide range of e. Such large & demands Onn²) memory as the e-neighborhood of one point needs (n) space. Such memory constraint is infeasible for million-point data sets.
Contribution. Inspired by sampling approaches, we observe that the exact e-neighborhood for every point is unnecessary to form and visualize the density-based clustering results. Our approach, named sDBSCAN, first builds lightweight random projection-basee index with a sufficiently large number of projection vectors. Utilizing the asymptotic property of the extreme order statisties associated with some specific random vectors [18, sDBSCAN can select high-quality candidates to identify e-neighborhoods with theoretical guarantees. sDBSCAN provably outputs DBSCAN's s clustering structure similar to DBSCAN on cosine distance under mild conditions from data distribution. These conditions are much weaker than the ones used on recent sampling- based DBSCAN [14] 155) Empirically, sDBSCAN runs significantly faster than several competitive DBSCAN variants while achieving similar DBSCAN clustering accuracy on million-poii 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, LI, x² and Jensen-Shannon (JS), that allow random
kernel features 19 20
Scalability. Both sDBSCAN and sOPTICS are scalable and multi-thread friendly. sDBSCAN and SOPTICS take a few minutes to cluster and visualize clustering structures for million- point data sets while the scikit-learn counterparts cannot on hardware. On Mnist8m with 8.1 million points, sDBSCAN gives 38% accuracy (measuring by the normalized mutual information NMI), running in 15 minutes single machine of 2.2GHz 32-core (64 threads) AMD processor with 128GB of DRAM. In contrast, kernel k-means [21] 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

---

2 Preliminary
We briefly describe DBSCAN O. OPTICS 17], and the connection with approximate neighbor search (ANNS). We present a recent advanced random projection method 22 23 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 large-scale data sets.
2.1 DBSCAN
DBSCAN is density-based approach that links nearby dense areas to form the cluster. For distance measure dist(;;) :) DBSCAN has two parameters and Pts. Given the data set X, for each point q X. DBSCAN executes range reporting query (g) that finds all points x E X within the E-neighborhood of q, i.. B (q) = {x E X dist (x, q) S E}. Based on the size of the range query result, DBSCAN determines q core if (a) minPts; otherwise, non-core points. We will call the e-neighborhood B_ (q) as the neighborhood q for short.
DBSCAN forms clusters by connecting core points and their neighborhoods where two core points qi and q2 are connected if q1 E Bg (q2). A non-core point belonging to a core point's neighborhood will be con- sidered a border point and share the core point's label. Non-core points not belonging to any core point's neighborhood will be classified as noise. Indeed, DBSCAN forms graph G that connects n points together 7 [14. G will have several disconnected components corresponding to the cluster structure. Each connected component contains connected core points and their neighborhoods, as shown in Alg. T
Algorithm I DBSCAN
1: Inputs: X, E, minPts, the set
{(q B3 (q)) q is core)
2: G + initialize empty graph
3: for each q E C' do
4: Add an edge (and possibly vertices) in
G from q to all core points in B, (q)
5: Add an edge (and possibly vertices)
in G from q non-core points
(q) if x is not connected 6: return connected components of G
2.2 OPTICS
OPTICS [17] attempts to mitigate the problem of selecting relevant = by linearly ordering the data points such that close points become neighbors in the ordering. For each point q E X. OPTICS computes a reachability distance from its closest core point. The cluster ordering and reachability distance of each point used to construct reachability- plltt dendrogram that visualizes the density- based clustering results corresponding to a broad range of e. Valleys in the reachability-ple are considered clustering indicators. The OPTICS's algorithm is detailed in the appendix.
Given pair (e, min minPls). OPTICS first identifies the core points, the neighborhoods of core points, and then computes the core distance of every point, defined as below.
if q is non-core, coreDist(q) = minn NN distance otherwise.
Then, OPTICS iterates X, and for each X, computes the smallest reachability distance, defined by x.reach, between 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 reachability distance reachDist(x, q) is defined as follows.
reachDist(x, q) = fo0
q is non-core, otherwise.
(mao(coreDist(q) dist(x, q))
For a core point q. reachDist(x, q) is dist(x, q) if is not belonging to minPts-NN of q. Among several core points whose neighborhood contains x, OPTICS tends seek the smallest reachability distance, i.e. x.reach, for x from these core points, which reflects the distance between x and its nearby cluster. Therefore, points tend to be grouped with its neighborhood to form a cluster. sharp decrease of x.reach of the point in the group indicates that we are processing points in denser regions, and slight increase indicates that we are processing points in sparser regions. This creates valleys the dendrograms reflecting the number of clusters where points downwards the valley floor are on denser regions while points upwards the valley head are on sparser regions. By selecting & to separate valleys provided by OPTICS, DBSCAN can achieve the peak of accuracy.
3

---

Time and space complexity. Similar to DBSCAN, the running time of OPTICS is Onn²) makes it impractical on large-scale data sets. Fast implementations of OPTICS with large values of æ might require (nn²) memory to store the matrix distance between the core points and their neighborhood points. Such implementations are infeasible for large n.
2.3 Random projection-based neighborhood preservation
Since the primary bottleneck of DBSCAN is to find core points and their neighborhoods by ex- ecuting n range queries, reducing the computational cost of this step will significantly improve the performance. Scaling up DBSCAN poses the need for lighteeigtt indexing data structures, ideally with linear construction time, to approximately answer range queries. Heavyweight graph- based indexes [24, 25 with O(n²) construction time and locality-sensitie hashing (LSH)-based
indexes 23 26 with subquadratic construction time will dominate the clustering time.
We elaborate on the recent work, called CEOs 22 that studies extreme order statistics properties of random projection methods to approximate inner product. Given D random vectors r; E TR i E (D), whose coordinates are randomly selected from the standard normal distribution ((0 1), and the sign function sgn(.). CEOs randomly projects and q onto these D Gaussian random vectors. It studies the behavior of the projection values on specific random vectors that are closest or furthest to q. e.g., arg max,, lq r.). Given sufficiently large D, the projection values on the closest furthest random vector to q approximately preserve x q. The proof is described in the appendix.
Lemma 1. [22) For two points x, 9 8a-1 and significantly large D random vectors rú, w.l.o.g. we let r. = arg max,, 1q rı]. Then, we have
x xJr. rx 2 N (sga(qTr.) r.) xT xxqxxxqqvv // (D), (x (xTa)²)
As a geometric intuition, for significantly large D random vectors, r. is closest or furthest to q. the projection values of all points in X onto r., tend to preserve their inner product order with q. For constant l >> 0, Lemma T also holds for the top-k closest/furthest vectors to q due to the asymptotic property of extreme normal order statistics [18] (2). Therefore, by maintaining a few points that are closest/furthest to random vectors, we can approximate the neighborhood of each point accurately and efficiently. 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.
3 Scalable density-based clustering with random projections
We first present simple and scalable DBSCAN, called sDBSCAN, with cosine distance. We then leverage well-known random feature embeddings [19 20 to extend our proposed sDBSCAN to other popular distance measures, including L1 and L2 metrics, and widely used similarity measures for image data, including x" and Jensen-Shannon (JS). We also present sOPTICS to select relevant values of for sDBSCAN. The detailed discussion and complexity of sOPTICS are in the appendix.
3.1 sDBSCAN: A simple and scalable density-based clustering
For each point q X C sdl-1, we compute random projection values q Tr, where i E [D] W.l.o.g., we let r. arg max,, q Tr,l arg max,, q r,, Lemma [ indicates that, given sufficiently large D, points closest to r. tend to have smaller distances to and hence are important discover q's neighborhood. Hence, computing the distance between q to the top-m points closest to r, where m = (mminPts) suffices to ensure whether or not q is a core point.
Algorithm 2 shows how we preprocess the data set. For each point q E X, we keep top-k closest and furthest random vectors. For each random vector r, we keep top-m closest and furthest points. Algorithm 3 iidentiiies core point q and its approximate neighborhood by computing the distance between q and 2km points associated to the l closest and & furthest random vectors to q. sDBSCAN and sOPTICS are essential DBSCAN and OPTICS using the outputs of Algorithm as inputs.
Scalability. Given m O(minPis)) sDBSCAN and sOPTICS need O(k: minPis) distance computations, compared to On)) of the exact solution, to identify core point q and its neighborhood

---

Algorithm 2 Preprocessing
1: Inputs: X C S random vectors r,, k, m = O(minPts)
2: for each X, compute and store top-k closest and top-k furthest vectors r; to q-
3: for each random vector ri, compute and store top-m closest and top-m furthest points to r;-
Algorithm 3 Finding points and their approximate neighborhoods
1: Inputs: X C S D random vectors rú, k; O(minPts)
2: Initialize empty set B3 (q) for each q X
3: for each E X do
4: for each F; from top-k closest (or furthest) random vectors of q do
5: for each x from top-mn closest (or furthest) points of r; do
6: if dxst(x, q) I then
7:
Insert x into (q) and insert q into (x)
8:
for each q X do
9:
if [B) 2 minPts then
Output q as a core point and (g) as an approximate B. (q) for DBSCAN (Alg. 11: Output dist(x, q) for each x E (q) for OPTICS (Alg. 6
Algorithm sDBSCAN
1: Inputs: X C C D random vectors r,, c, min Pts
2: Call Algorithm| for preprocessing with m = O(minPts))
3: Call Algorithm 3 to find the set C' = {q. (g)) is identified core)
4: Call DBSCAN given the output C from Algorithm
Algorithm 5 sOPTICS
1: Inputs: X C Sd-1 D random vectors r,, E, minPls
2: Call Algorithm 2 for preprocessing with m O(minPls)
3: Call Algorithm to find the set C' {(q (q),
{dist(x, 9) for each x E (g) l is identified as core]
4: Use the PrinPts-NN distance between q and (q) coreDist(a) for each identified core point q
5: Call OPTICS (Alg. given the output C from Algorithm
subset (q) (g) The memory usage store Bg (q) is also bounded by O(k minn This makes sDBSCAN and sOPTICS scalable regarding both time and space complexity.
Multi-threading. Like DBSCAN, the main computational bottlenecks of sDBSCAN and sOPTICS are identifying core points and approximating their neighhorhood. Fortunately, Algorithm 2 and 3 are fast and frrenlel-friendly. We only need to add #pragma omp parallel directive the for loops to run in multi-threads. This enables sDBSCAN and sOPTICS to deal with million-poin data sets in minutes while the scikit-learn counterparts take hours cannot finish due to the memory constraints.
3.2 Theoretical analysis of sDBSCAN
In practice, setting m Omin suffices to identify core points and approximate their neigh- borhoods to ensure the quality of sDBSCAN. However, to theoretically guarantee the quality of sDBSCAN, we need to adjust based on the data distribution since ensuring the density-based clustering quality without any information about the data distribution is hard [1 [5]
As in the unit sphere, if (2(x, 9) S then x 2 =2/2, make change in algorithm. For each random vector r;, maintain two sets S; (x X x r, (1 - 22/2) (D)) and R; (x x < -(1 8² 2//2) 22) (D)), instead of keeping only top-m closest/furthest points. In other words, for each random vector r,, the value of is set adaptively to the data
5

---

distributed around r,. For a point and its closest random vector r., if we compute L2(x, q) for all x E S. where S. {x E X x rr (1- 2 (D)}. then any x E (q) is found with a probability at least 1/2 due to the Gaussian distribution in Eq. ( By computing the distance between q and all points in S; or R& corresponding to the top-k closest/furthest random vectors r, of q. we can boost this probability
= 1 - (1/2)²² 2* due to the asymptotic independence among these
2k vectors 18 122].
By connecting core points and their associated border points, DBSCAN outputs e-neighborhood graph with disconnected components G1, G....., Gj corresponding to I density-based clusters C1 C2..... Gt. Hence, by maintaining S₃ and R, for each vector r,, sDBSCAN forms a subgraph G¹ S - 15 1.....l, I,, by sampling each edge of G; with probability at least s. We now use the following lemma [27] to guarantee the connectivity of subgraphs G¹, provided by SDBSCAN.
Let G be a graph of n vertices with min-cut t and 0 < 8 < 1. There exists a universal constant e such that if s 2 ellog (1/8)++log(m)) (w)),, then with probability at least 1 - 6, the graph G' derived by sampling each edge of G with probability s connected.
Lemma 2.
Since DBSCAN connects core points, there exists a constant / > such that, for any pair of nearby core points QI, q2, if (2 q2) S E, then (q( ) and (4p) share at least L common core points. We assume that will not small to ensure that the density-based clusters will not become arbitrarily thin anywhere Given that DBSCAN produces / disconnected graphs G1, G2..... .... Gt. it is clear that t will be the lower bound of the min-cut of any G, By applying Lemma on each G., we state our main result.
Theorem 1. Let G1, ..,,........ Gi be connected subgraphs produced by DBSCAN where each G; corresponds to cluster C₁ with ni core points. Assume that any pair of nearby core points qı, qp. if L2(q1, qe) S s, then B₂ (q(qi) and Br (42) share at least common core points. There exists a constant e such that ift (1 (1/2) 2h) 2 c (log (1/8) + log (nr)forr i E [1], sDBSCAN will recover G1, G2...., Gi as clusters with probability at least 1 - 6.
Theorem indicates that when the cluster C, of n, core points is not thin anywhere, i.e. the common neighborhood of any two nearby core points has at least t = O(log (n:) core points, sDBSCAN can recover Cj with probability 1-1 1/n4- While our statistical guarantee is inspired by 15) do not need any strong assumption about the data distribution as used in [15] However, it comes with the cost of maintaining larger neighborhoods around the random vector r; (i.e. S, R₂) that causes significant computational resources.
In practice, a core point q is often surrounded by many other core points in a dense cluster. Therefore, instead of maintaining the sets S₁, R2 for each random vector r,, we can keep the top-m points of these sets where m (/minPts), This practical setting substantially reduces the memory usage and running time of sDBSCAN without degrading clustering results. The next subsection justifies it.
3.3 From theory to practice
We observe that for any core point q regarding mi,mintts)) [B (q) is often substantially larger than misS We will present heuristics to improve the performance of sDBSCAN.
Identify core points with m = O Given a core point q. we denote by x E (q) and y E X (e(g) any close and far away points to q regarding the distance threshold W.l.o.g., we assume that r. = arg max,, q r,, and let X x &r,, Y = y Jr. be the
projection values of y,y on r,, respectively. From Eq. ① X Y follows a Gaussian
distribution whose variance is bounded by (VI-(x)) (xT q)² + V (y (yTa)²) Let axy =
/ (V1- -x)-)
+ (y and a, = arg min x B, (q). (B) Gxy- As
Lemma [ holld for l: closest/furthest random vectors, assume that the event any point x E (.(q) is ranked higher than all y E X (q) is independent, Lemma 3 justifies that m min Pts suffices to identify as core point. The proof based on the tail bound of the Gaussian variable X - Y and the union bound is left in the appendix.

---

Lemma 3. Given D = /ko? for a given core point q E X C S6-1 where [B(()) 2 minPts, maintaining top-minPts points associated to k closest/furthest vectors to q ensures minPls, Be(g) S (q(q) with probability at least (1 - 1//nmmmiee
[g) 2
e-min mis/t
Lemma LemmaBhholds Bholds given the dependence of D on the data distribution around (i.e. a.). We empirically observe that the distance gap between q and points inside and outside (q) significant, making a large. Hence, setting D = 1, 024, k = {5, ] suffices to identify core points and enrich their neighborhoods, achieving high clustering quality on many
data sets.
sDBSCAN-INN to cluster misidentified border points. As sDBSCAN focuses on identifying core points and approximating their neighborhoods, it misclassifies border points as noise. 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 points. Denote by C and C' the set of clustered core points and noisy points found by sDBSCAN, we propose a simple heuristic to classify any x E C. We will build a nearest neighbor classifier (INN) where training points are sampled from C, and scale up this classifier with the CEOs-based estimation approach 22 Alg. 1]. We call sDBSCAN with the approximate INN heuristic as sDBSCAN-INN.
In particular, for each sampled core point q E C. we recompute their random projection values with the stored D) random vector r; as we do not keep these values after preprocessing, For each noisy point x E C, we retrieve the precomputed top-k closest/furthest vectors and use the projection values of q at these top-k vectors to estimate x q. To ensure this heuristic does not affect sDBSCAN time where [C| |C| R= 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.
Remark. sDBSCAN quickly finds core points and assigns cluster labels for non-core points using a lightweight index. In contrast, LSH-based approaches [23] 28 need several LSH tables or multi-
probes [29 that cause significant space or time overheads. Also, seems non-trivial for multi multi-probe LSH to achieve DBSCAN's accuracy with guarantees as the collision probability of multi-probes is hard to control. Assigning label for identified non-core points with LSH seems non-trivial as these points might collide with many core points from different clusters.
Extend to other distance measures. We extend sDBSCAN to other popular distance measures. including L2, LI, x2, and Jensen-Shannon (JS) via popular randomized kernel features [9 20 In particular, we study fast randomized feature mapping f Rd + Rd such that E [f(x) T f(a))
K K(x, q) where K are Gaussian, Laplacian, x², and JS kernels. As we execute random projections on the constructed random features for each point and compute dist( y) using the original data, we
only need small extra space to store the randomness associated with f. These embeddings' extra costs are negligible compared to sDBSCAN. Detailed discussion is left in the appendix.
Reduce the random projection costs. We will use the Structured Spinners [26] that exploits Fast Hadamard Transform (FHT) to reduce the cost of Gaussian random projections. In particular, we generate 3 random diagonal matrices D1, D2, D3 whose values are randomly chosen in {+1. -1}. The random projection of x is simulated by the mapping x + HD, x where H is the Hadamard matrix. With FHT, the random projection can be simulated in O (D log (D)) time and use additional OD) extra space to store random matrices.
3.4 The time and space complexity of sDBSCAN
We analyze the time and space complexity of sDBSCAN with m = O(mintts).
Time complexity. With FHT, retrieving top-k closest/furthest vectors for each q E X, and top-m closest/furthest points for each random vector r, in the preprocessing (Alg. 2 runs in O (nDlog (D) + nD log (k) + n log (minPts))) time. Finding approximate neighborhoods for Pts) time since each point needs Ofk múnPts) distance computations. For a constant k, sDBSCAN runs in O(dn min + nD nDlog (D)) time. When D o(n), sDBSCAN runs in subquadratic time.
points (Alg. 3 runs in O(dnk
Empirically, the cost of identifying core points and their neighborhood dominates the preprocessing cost due to the expensive random memory access of distance computations. Nevertheless, pre-
7

---

1.5
reachDist
reachDiet
reachDeet
other dis- @Oplice (L1)
(b) &Optice (L2)
@Optics (Cosine)
sOptice (JS)
Diocis
Coucas
8000
(L1)
variants (L2)
(g)
(Cosine)
(h) variants (JS)
Figure I: Top: sOPTICS's graphs on L1, L2, cosine, JS on Mnist. sOPTICS runs within 3 seconds while scikit-learn OPTICS requires 1.5 hours on L2. Bottom: AMI of DBSCAN variants on L1, L2, cosine, JS over the range of suggested by sOPTICS Cosine and JS give the highest AMI.
processing and finding neighborhood steps are elementary to run in parallel. Our straightforward multi-threading implementation of sDBSCAN and sOPTICS shows a 10x speedup with 64 threads.
Space complexity. sDBSCAN needs O D minPlss extra space to store O(k) closest/furthest vectors for each point, and (minnPts) points closest/furthest to each random vector. When D = o(n), sDBSCAN's additional memory is negligible compared the data size Onnd). This key feature makes sDBSCAN highly scalable on million-poo Dollion-pponttt data sets compared to standard DBSCAN and several kernel-base clustering 4 [5]
Experiment
We implement sDBSCAN and sOPTICS in C++ and compile with g++ -03 -std=c++17 -fopemmp -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 ground truth (i.c. data labels) to verify our claims, including:
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 due to memory constraints on our hardware.
Our competitors include PDBSCAN 6 representative grid-based approach, DBSCAN+ [14
and SngDBSCAN [5]. DBSCAN+ has two variants, including DBSCAN+ with uniform ini- tialization (uDBSCAN++) that uses KD-Trees to speed up the search of core points and k-center initialization (kDBSCAN++). We also compare with multi-threading scikit-learn implementations of DBSCAN and OPTICS. To demonstrate the scalability and utility of sDBSCAN
tance measures, we compare it with the result kernel k-means in 21 1 We found other clustering competitors could not work on million-point point data sets given 128 GB of RAM, detailed in the appendix.
We use the adjusted mutual information (AMI) (3 to measure the clustering quality. Results on other measures [3I], including normalized mutual information (NMI) and correlated coefficients (CC) are the appendix. 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). All results are the average of 5 runs of the algorithms.
Parameter settings. We consider min Pl.s 50 for all experiments. sDBSCAN and sOPTICS use D 1024, m = minPls. Randomized kernel embeddings use a 2e, d' = 1024. We use for Mnist and A = 10 for Pamap2 and Mnist8m. We first run sOPTICS to select relevant range of

---

values of E for DBSCAN variants. For DBSCAN+ and sngDBSCAN variants, we set the sampling probability p 0.01 for Mnist and Pamap2, and p 0.001 for Mnist8m have similar number of distance computations with sDBSCAN, pDBSCAN uses = 0.001. Experiments on the sensitivity of parameters m, k; 0, d', min.Ps of sDBSCAN and sOPTICS are left in the appendix.
4.1 An ablation study of sOPTICS and sDBSCAN on Mnist
While DBSCAN on 1.2 is popular, the capacity to use arbitrary distances is an advantage of DBSCAN compared to other clustering algorithms. We sOPTICS to visualize the cluster structure several distance measures, including LI, L.2, cosine, and JS on Mnist with D = 1, 024, m min = 50, k 5. By using the average top-100 nearest neighbor distances of 100 random points find the setting of e for sOPTICS, we set e = 1, 800 for L2, & = 18, 000 for LI, and Æ 0.25 for the others.
The top subfigures of Figure show reachability- 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. Therefore, can predict that cosine and JS provide higher clustering quality than I.2 while L1 suffers low-quality clustering. Importantly, any in the range [0.1, 0.15) can differentiate the 4 valleys by cosine and JS while selecting a specific value to separate the 3 valleys by L.2 is impossible. Note that 64-thread sOPTICS runs in less than 3 seconds while 64-thread scikit-learn OPTICS demands 1.5 hours L2. Indeed, SOPTICS can output similar OPTICS graphs within 30 seconds, as shown in the appendix.
dendrograms of sOPTICS
studied distance
The bottom subfigures of Figure T show AMI scores of several DBSCAN variants over the recom- mended ranges of by SOPTICS. Note that sDBSCAN and DBSCAN reach the peak on such ranges while sampling-based variants do not. sDbscan is superior on all 4 supported distances, except L2 by uDBSCAN++. While sDBSCAN reaches DBSCAN's accuracy of AMI 43% on cosine and JS, SngDBSCAN gives significantly lower accuracy on all 4 distances. uDBSCAN++ gives at most 32% AMI on L2 and cosine while KDBSCAN++ does not provide meaningful result on the studied range values of L.2 and L1 distances show inferior performance clustering compared to cosine and JS, as can be predicted from their corresponding SOPTICS graphs.
Table 1 summarizes the performance of studied DBSCAN variants on the best E [0.1, with cosine distance. On thread, sDBSCAN runs nearly 2x,8 8x and 10x faster than SngDBSCAN, uDBSCAN++ and KDBSCAN++, respectively. 64-thread sDBSCAN runs nearly 10x faster than 1-thread sDBSCAN and x00x faster than 64-thread scikit-learn. Though PDBSCAN shares the same AMI with scikit-learn, its rumning time makes it infeasible for high-dimensional data sets.
4.2 Comparison on million-point data sets: Pamap2 and Mnist8m
This subsection compares the performance of sDBSCAN, DBSCAN+ and sngDBSCAN on million- point data sets. scikit-learn DBSCAN and PDBSCAN cannot finish after 4 hours. Our implemented sngDBSCAN runs faster than [ and supports multi-threading. We use SOPTICS graphs in the appendix to select relevant ranges of e. sOPTICS runs in 2 mins and 11 mins on Pamap2 and Mnist8m, respectively, significantly faster than DBSCAN+ and sngDBSCAN, The released DBSCAN+ does not support LI, x2, JS and multi-threading while the rest are in multi muutii-hrreadin.
Pamap2. Figure shows the performance of sDBSCAN compared to DBSCAN+ and sngDBSCAN. Given suggested ranges of & by SOPTICS, sDBSCAN's AMI peaks are consistently higher than that of SngDBSCAN but 5% lower than DBSCAN on LI and L2. While sDBSCAN achieves the AMI peak on the studied ranges of & on 3 distances, the performance of the others is very different on different range of with cosine. We found that DBSCAN with ε 0.005 returns AMI 47% but
Table 1: AMI on the best = E [0.1, and running time of 64-thread scikit-learn vs. 1-thread DBSCAN variants using cosine distance on Mnist. 64-thread sDBSCAN runs in 0.9 seconds.
Alg.
scikit-learn
sDBSCAN uDBSCAN++ KDBSCAN++ SigDBSCAN
PDBSCAN
AMI
43%
43%
43%
7%
33%
43%
Time 86s
8.8s
67s
87s
18s
1.85 hours
0.11
0.14
0.18
0.2
0.15
0.11

---

sbscan
Dbocan
Ubbscan++
KDegaan-
angübscan
AMI
8x
0.
(b) L2
(c) Cosine
Figure 2: AMI comparison of DBSCAN variants on LI, L2 and cosine Pamap2 over a wide range of suggested by sOPTICS, sDBSCAN runs within 0.3 mins, nearly 10x, 10x, 45x, 100x faster than SngDBSCAN, uDBSCAN++, kDBSCAN++, and DBSCAN, gives the highest AMI.
ACtaaa- IM- Scheast
Disenn 1904 Aincen wwwelimmas rngheroo Do
Veffhsian
120
GM
JS
Figure 3: NMI comparison of DBSCAN variants on L2, cosine, x², and JS and kernel k-means on Mnist8m over wide ranges of suggested by sOPTICS. sDBSCAN and sDBSCAN-INN runs within 10 mins and 15 mins while SngDBSCAN demands nearly hour. Kernel k-means (k = 10) 21 runs in 15 mins supercomputer of 32 nodes, each has 64 threads and 128 GB of DRAM.
offers only 37% AMI on 0.01. This explains the reliability of sOPTICS in guiding the parameter setting for sDBSCAN and the difficulty in selecting relevant & for other DBSCAN variants without any scalable visual tools.
Mnist8m. As DBSCAN++ with = 0.001 could not finish after hours, we only report sngDBSCAN
As cannot scikit-lear k-means++ or any kernel-based clustering 4 5 with 128 GB of RAM, we use the result of 41% NMI given by a fast kernel k-means [2 running on supercomputer with 32 nodes, each of which has two 2.3GHz 16-core (32 threads) Haskell processors and 128GB of single node is similar to our conducted machine. Figure shows
DRAM. This configuration the NMI scores of sDBSCAN-IE -NN with I-NN heuristic deseribed in Subsection 3.3, sDBSCAN sgnDBSCAN, and kernel k-means on Mnist8m. sDBSCAN- NN shows superiority among DBSCAN variants. Its peak is least 10% and 5% higher than SngDBSCAN and sDBSCAN, respectively, studied measures. sDBSCAN consistently gives higher accuracy than SngDBSCAN with the most significant gap of 5% x2 and cosine. Note that sDBSCAN- INN samples 0.01n uses CEOs to build the approximate INN classifier, the time overhead of this step is smaller than sDBSCAN's time. Indeed, sDBSCAN- INN with min 100 reaches 40% NMI on x² running within 15 minutes. Details of the running time comparison are in the appendix.
points, and
Conclusion
The paper presents a simple and scalable sDBSCAN for density-based clustering, and sOPTICS for interactive clustering exploration for high-dimensional data. By leveraging the neighborhood preservation of random projections, sDBSCAN preserves the DBSCAN's s output with theoretical guarantees under mild conditions. We extend our proposed algorithms to other distance measures to facilitate density-based clustering on many applications with image data. Empirically, both sDBSCAN and sOPTICS are highly scalable, run in minutes million-point data sets, and provide very competitive accuracy compared other clustering algorithms. We hope sDBSCAN and SOPTICS will be featured on popular clustering libraries shortly.
10

---

Acknowledgments and Disclosure of Funding
Ninh Pham is supported by Marsden Fund (MFP-UOA2226).
References
[1] Martin Ester, Hans- Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, pages 226-231, 1996.
[2] Ricardo J. G. B. Campello, Peer Kröger. Jörg Sander, and Arthur Zimek. Density-based clustering. WIREs Data Mining Knowl. Discov, 10(2). 2020.
[3] David Arthur and Sergei Vassilvitskii. k-means++: the advantages careful seeding. In SODA, pages 1027-1035, 2007.
[4] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In SIGKDD, pages 551-556, 2004.
[5] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-90) 2000.
[6] Junhao Gan and Yufei Tao. On the hardness and approximation euclidean DBSCAN, ACM Trans. Database Syst., 42:3)):1:1-14::: 2017.
[7] Erich Schubert, Jörg Sander, Martin Ester, Hans-Peter Kriegel, and Xiaowei Xu. DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Trans. Databuse Syst., 12:3):19:1119:21, 2017.
[8] Son T. Mai, Ira Assent, and Martin Storgaard. Anydbe: An efficient anytime density-based clustering algorithm for very large complex datasets. In SIGKDD, pages 1025-1034. ACM, 2016.
[9] Xiaogang Huang and Tiefeng Ma. Fast density-based clustering: Geometric approach. Proc. ACM Manag, Data, ((1):58:1-5822) 2023.
[10] K. Mahesh Kumar and A. Rama Mohan Reddy. A fast DBSCAN clustering algorithm by accelerating neighbor searching using groups method. Pattern Recognit, 58:39-48, 48,99488885 2016.
[11] Mark de Berg, Ade Gunawan, and Marcel Roeloffzen. Faster DBSCAN and HDBSCAN in low-dimensional euclidean spaces. Int. J. Comput. Geom. Appl., 29(1):21-4) 2019.
[12] Hossein Esfandiari. Vahab S. Mirrokni, and Peilin Zhong. Almost linear time density level set estimation via DBSCAN. In AAAI, pages 7349-7357, 2021.
[13] Johannes Schneider and Michail Vlachos. Scalable density-based clustering with quality guarantees using random projections. Data Min. Knowl. Discov., 31(4):972-1005, 2017.
[14] Jennifer Jang and Heinrich Jiang. Dbscan++: Towards fast and scalable density clustering, In
ICML, pages 3019-3029, 2019.
[15] Heinrich Jiang, Jennifer Jang, and Jakub Lacki. Faster DBSCAN via subsampled similarity queries. In NeurlPS, 2020.
[16] Heinrich Jiang. Density level set estimation on manifolds with DBSCAN. In ICML, volume 70, pages 1684-1666 1693, 2017.
[17] Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. OPTICS: ordering points to identify the clustering structure. In SIGMOD, pages 49-60, 1999.
[18] H. A. David and J. Galambos. The asymptotic theory of concomitants of order statistics. Journal of Applied Probability, 11(4):762-77) 1974.
[19] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In NIPS, pages 1177-1184, 2007.

---

[20] Andrea Vedaldi and Andrew Zisserman. Efficient additive kernels via explicit feature maps.
IEEE Trans. Pattern Anal. Mach. Intell., 34(3):480-492 492000499222900 2012.
[21] Shusen Wang, Alex Gittens, and Michael W. Mahoney. Scalable kernel k-means clustering with nyström approximation: Relative-error bounds. J. Mach. Learn. Res., 20: 20:12:1-12:49 2019.
[22] Ninh Pham. Simple yet efficient algorithms for maximum inner product search via extreme order statistics. In KDD, pages 1339-1347,200 2021.
[23] Ninh Pham and Tao Liu. Falconn++: A locality-sensitive filtering approach for approximate nearest neighbor search. In NeurIPS, 2022.
[24] Faiss Library. Faiss. https://faiss.ail.
[25] Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell., 4244))824-836, 2020.
[26] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In NIPS, pages 1225-1233, 2015.
[27] David R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2):383-413, 1999.
[28] Thomas D. Ahle, Martin Aumüller, and Rasmus Pagh. Parameter-fire free locality sensitive hashing for spherical range reporting. In SODA, pages 239-256, 2017.
[29] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for high-dimensional similarity search. In VLDB, pages 950-961, 2007.
[30] Xuan Vinh Nguyen, Julien Epps, and James Bailey. Information theoretic measures for cluster- ings comparison: Variants, properties, normalization and correction for chance. J. Mach. Learn. Res., 11:2837-28542 2010.
[31] Martijn Gösgens, Alexey Tikhonov, and Liudmila Prokhorenkova. Systematic analysis of cluster similarity indices: How to validate validation measures. In ICML, volume 139, pages 3799-3808, PMLR, 2021.
[32] H. A. David. Concomitants of Extreme Order Statistics, pages 211 211-224. Springer US, 1994.
[33] Martin J. Wainwright, Basic tail and concentration bounds, pages 21-57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
12

---

A OPTICS and sOPTICS
A.1 OPTICS
OPTICS [17] attempts to mitigate the problem of selecting relevant by linearly ordering the data points such that close points become neighbors in the ordering. For each point x E X, OPTICS computes a reachability distance from its closest core point. Each point's cluster ordering and reachability distance are used to construct reachability--los dendrogram that visualizes the density- based clustering results corresponding to broad range of e. Hence, given the setting of large E, valleys in the reachability plot are considered as the clustering indicators.
In principle, given pair (e, min.Pts) OPTICS first identifies the core points, their neighborhoods, and their core distances. Then, OPTICS iterates X, and for each x E X, computes the smallest reachability distance, called x.reach, between 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, and reachability distance, reachDist, are defined as follows.
if q is non-core, minnts NN distance otherwise.
coreDist(q) =
foo reachDist(x, q) (maa(coreDiss((g) dist( 9))
if q is non-core, otherwise.
For core point q. reach DestxxDis(x, q) is dist(x; q) if is not belonging to minPis-NN of q- Among several core points whose neighhorhood contains x, OPTICS seeks the small- est reachability distance x.reach for from these core points. In other words, x.reach ming. (reachDist(xx, q:) q: is core and x E Bg (q:))-
OPTICS can be implemented as nested loop shown in Algorithm 6 In the outer loop (Line 4), a random q E X is selected and inserted into an empty cluster ordering O. If q is core, each point (q(q) is inserted into priority queue Q with reach Dist(x, q) as the key value. An inner loop (Line 12) that successively pops q' from Q until Q is empty. We can see that the priority of q' E 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 O is slightly different from the original version 17 Since we do not know how to implement decrease-key operation efficiently on the priority queue we propose a "lazy deletion" where we keep adding x into Q with the new key. Though x might be duplicated on Q, by checking whether or not is processed (Lines 16-18), we can process each point exactly once and output it into the cluster ordering O. When a point x is inserted into the ordering O, x.reach at the time it was popped out of Q is recorded. Therefore, by setting large enough, OPTICS outputs a cluster ordering that can be used as a visualization to extract clustering structure for smaller values e.
Time and space complexity. Similar to DBSCAN, the running time of OPTICS is O(n²) makes it impractical on large-scale data sets. Fast implementations of OPTICS with large values of & will require (n²) memory to store the matrix distance between the core points and its neighborhood points. Such implementations are infeasible for large
A.2 SOPTICS
To guide sDBSCAN's parameter setting, Algorithm 5 presents sOPTICS, an OPTICS variant with the identified core points and their neighborhood subsets provided by Algorithm 3 Given the identified
core point q and B. (q), we store the set (dist(x, q) for each x E (a)) (Line 16 of Alg. 3 Using
this set, we can estimate coreDis((q) as the minPls-NN distance between q and B. Though such estimation is an upper bound of coreDisl((q). the tightness of the upper bound and the accurate neighborhood approximation make the reachability-plot provided by SOPTICS very similar to the
IC+ STL priority queue does support decrease-key function.
13

---

Algorithm 6 OPTICS
Inputs: X, E, minPts, the set C' {(q. B3 core
[xi q) for each x E BB(q))) [ q core)
2: Initialize empty cluster ordering O
3: q.reach t oo for each q E X
4: for each unprocessed q E X do
5: Mark q as processed, and insert q into O
6: if q is core then
7: Seeds <- empty priority queue Q
8: for each x E (q) do if x is umprocessed then
9:
10:
x.reach + Insert (x, x.reach into Q
reach q))
11:
12:
while Q is not empty do
13:
q' <- Q.poop()
14:
if q' is processed then
15:
continue
16:
Mark q' as processed, and insert q' into O if q' is core then
17:
18:
for each umprocessed x E B=(q') do x.reach min( reachDist(x, q)))
20:
Insert (x, xeach) into Q return Cluster ordering O
21:
original OPTICS with the same valley areas. Therefore, sOPTICS is fast and reliable tool to guide DBSCAN and sDBSCAN parameter settings and to visualize the clustering structure.
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, will discuss SOPTICS's quality in practical scenarios.
Like sDBSCAN, sOPTICS only considers top-m closest/furthest points to any random vector where (mmnn Given core point q, the distance of derived from the set (g is upper bound of core Dost Since core point is often surrounded by many other core points in dense cluster, B_ (q) tends to contain core points. Hence, the upper bound of reachability distance provided by sOPTICS tight. When the clustering structure well separated, i.c., valleys in the reachability-plot are deep, sOPTICS with (s, minPts) for DBSCAN. Importantly, the extra space of sOPTICS is linear, i.c. O(nk minPts). the approximate neighborhood size of each point is O minPts).
O(minPis is reliable tool to guide the selection of
Time complexity. Similar to sDBSCAN, sOPTICS runs in Odn minPts + nD log (D)) time for preprocessing and identifying core points and its approximate neighborhood. For each point sOPTICS keeps [B (q)l O(k månPts) points and distance values. The size of the priority queue Q of sOPTICS is Onn minPts). Therefore, for a constant k. sOPTICS runs in O(dn minPts nD log (D) n min Pts log (n minPts)). When D o(n), sOPTICS run in subquadratic time.
Space complexity. sOPTICS needs Onk + mánPts) extra space store O(k) closest/furthest vectors for each point, and O(minPis) points closest/furthest to each random vector. Due to the priority queue size Onk minPis), sOPTICS uses O(nk + minPls + nk mlnnlss extra space, which is linear when D = o(n), and independent on any value of s. Note that scikit-learn uses O(n2) memory and hence could not run OPTICS on million-pone data sets.
B Proof of Lemma 1, Lemma 3, and extension other distance measures
B.1 Proof of Lemmal
We briefly describe the proof of Lemma where points are on the unit sphere Sd-1, We note that Lemma I holds on general Euclidean space detailed in [22
14

---

Given two vectors q. E S and any random Gaussian vector r E R we let Q; = q and X; x rr, It is well known that Q, N0, 1), N(0, and Qi and X; are normal bivariates from N (0, 0, 1, p) where p x"q. Let (Q1 X1), (Q2. X2), .2...... (QD,Xp) be D random samples from N (o, O, 1, p) generated by D Gaussian vectors r,, < S D. We form the concomitants of normal order statisties by descendingly sorting these pairs based on Q-value.
Let r, = arg max,, q rr, Let X be the concomitant of the first (maximum) order statistic Qay. Then we have Q11 = q X1 =x'r, The theory of concomitants of extreme order statisties [88 321 studies the asymptotic behavior of the concomitants X given the asymptotic behavior of Q(1) when D goes to infinity.
The seminal work of David and Galambos of normal order statistics.
18 establishes the following properties of concomitants
E [Qo] 2 v 22 (D): Var [Q(n] 2 0.
[[u]] = (x q) E [(n) 2 x 21 (D),
Var [Xu]] = (x kTaa q))² + (x q)² Var [Qw)]] 2 1 - 1 9)
X11 2 N E [m]] Var [11i
Since Gaussian distribution is symmetric, we can use both XμI and -Xpp corresponding to the maximum (1) associated to the closest random vector and minimum Q(D) associated to the furthest random vector to q for estimating q. This proves the claim Lemma
B.2 Proof of Lemma 3
Given D random vectors r; E R E standard normal distribution (0, 1), and the sign function sgn(-), randomly projects and q onto these Gaussian random vectors. For significantly large random vectors rú, w.l.o.g. we assume that 1 arg max,, lq rz]. we have
[D], whose coordinates are randomly selected from the
x xJr1 ~ N (sgn(q r1) (ign(gTr):> xx'xx (n (x) aT)))
For constant k > this property (i.e. Lemma 1 also holds for the top-k closest/furrtest vectors due to the asymptotic property of extreme normal order statistics [18 (2))
Given core point q. we denote by points to q regarding the distance threshold E. W.l.ogg, we assume that rı = arg max,, lq rıl = arg max,, q qrr, Let X = x Fr, Y y rı be random variable corresponding to the projection values of x, y on F1, respectively. Then we have
(q) and
X (q) any close and far away
X ~ N x T q 22/221 (D), (x (xT))2 )) Y ~ N N (D)
Let axy = (x Txxg--'' y the Gaussian variable Y X gives
1 () + V a))
applying Chernoff bound 33 on
Pr 2 X] x a-y
2)2)² D-
Let a, = arg minxe x B. (x).,eX),BBB. Oxy and D = 2/n applying the union bound, we have Pr x is ranked higher than all E X (q) on r,] 2 1 1/n.
Since Lemma I holds for l: closest/furthest random vectors r; to due to their asymptotic indepen- dence, let R. be the set of these vectors associated to By setting D = n !/kof we have
Pr [x is ranked higher than all y X \\ Be(q) on vector in R. 1-1nn.
Assume that the event any point x E (g) is ranked higher than all y X (q) is independent, we have
Pr At least minPis points in (g) appear on top-minPls points associated to Rqj > (1 (1-1/n)min/?
This proves the claim of Lemma 3.
15

---

B.3 Extension to other similarity measures with random kernel features
We show how to extend sDBSCAN and sOPTICS to other popular distance measures, including L2, LI, x². and Femenn-haamin (JS). We will utilize the random features [19 20 to embed these distances into cosine distance. In particular, we study fast randomized feature mapping f: R + Rd such that E [x() f(q)] = K (xx q) where K is the kernel function. We study Gaussian, Laplacian, x2. and IS 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.
0, the following the definitions of the Given (f1,--.,5d) Fd).y - ya) and investigated kernels.
Ky (x,,))
1xx |xxyyll/a k)(x,y) e- 111--y11/22r
(x,(x,y) Σ
20g4ii
+ Yi
Kjs(x,8) = Σ
log
+
V/
+
Yi
log
I; + y/i
2
32
2
V/
We present here the random Fourier embeddings [19 for K2 and Ka with a 1. We first generate d' random vectors W,, i E [d'] whose coordinates are from (N,0,) 1) for Ka and Lap(O, 1) for Kr. Our randomized mappings are:
f(x) V
{sin (w: (w:x). x). cos (w, x) e [d']] S2
1, the Hoeffding's inequality guarantees: 89/ By selecting d' = Ollog (n)). the randomized mapping / preserves well the kernel function of every pair of points. Hence, sDBSCAN and sOP- TICS on these randomized emheddings output similar results to DBSCAN and OPTICS on the corresponding distance measures.
Since f(y) S |
Pr [lf(x) f(y) - K(x. y)]
/)) 2 6] S e
Complexity, For KG. KL, the embedding time is (dd'). For K KJs, the embedding time is Odd') for d' random features by applying the sampling and scaling approaches (20]. Empirically, the random feature construction time negligible compared to the sDBSCAN and sOPTICS time. As execute random projections on the constructed random features for each point and compute dist(x.y y) using the original data, we only need a small extra space to store random vectors w.-
C Additional experiments
We use the Eigen library I for SIMD vectorization on computing the distances. It will only give advantages on dense data sets, e.g., Pamap2. Our sDBSCAN and sOPTICS are mulli-threaddig friendly. We only add #pragma omp parallel directive the for loop when preprocessing and finding the neighborhood for each point.
Clustering competitors. We tried several clustering algorithms on scikit-leam, including DBSCAN, spectral clustering, and kernel k-means. They could not work on million-point data sets given our DRAM of 128 GB. The released JAVA implementation of random projection-based DBSCAN [33 cannot run even on the small Mnist data set.
Our competitors include PDBSCAN 6 as representative grid-based approach. DBSCAN+ 14
and SngDBSCAN [B3 as representatives for sampling-buss 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 +DBSCAN++)) We also compare with multi-threading scikit-learn implementations of DBSCAN and OPTICS
hhtps:/eiign..uxffflllloogg
http:///dcakkklooonnnggrrreee/er html
16

---

Figure 4: Reachability- plot dendrograms of OPTICS and sOPTICS over 1.2 and L.1 on Mnist. While sOPTICS needs less than 30 seconds, scikit-learn OPTICS requires 1.5 hours on 1.2 and 0.5 hours on L.1.
Since the current SngDBSCAN only supports L2 and single thread, we re-implement sngDBSCAN support LI, x², and JS distance with multi-threading.
three popular data sets: Mnist (n 70, 000, d 784, # clus- ters = 10), Pamap2 (n 1, 770, 131, d = 51, # clusters = 18), and Mnist8m (n = 8, 100, 000, d = 784, # clusters = 10), as shown in Table 2 For Pamaps2, we discarded instances that contain NaN values and removed the dominated class corresponding to the transient activities. We note that Mnist and Mnist8m sparse data sets with at least 75% sparsity, while Pamap2 is dense.
Datasets. We conduct experiments
C.1 SOPTICS vs. seikit-learn OPTICS on Mnist over L1 and L2
This subsection measures the performance of sOPTICS and seikit-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 180x speedups over scikit-learn OPTICS.
We use scikit-leam OPTICS to generate the dendrogram given minPts 50. To select a reasonable value of for OPTICS to reduce the running time. randomly sample 100 points and use the average top- 100 nearest neighbor distances of these sampled points as E. Accordingly, we use & = 1, 800 for L2 and g = 18, 000 for L1.
To recover OPTICS's results, sOPTICS uses D 2, 048, k 2 and m 000. For L2 and L1 distances, sOPTICS requires two additional parameters, including the scale a and the number of embeddings d', for random Fourier embeddings. We observe that the performance of sOPTICS insensitive to a and d', hence we simply set 2 e and d' = 1, 024 for our experiments.
We run both seikit-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 4 Since there are more valleys on L2 than LI, the clustering accuracy regarding the ground truth using L2 will be higher than LI.
C.2 SDBSCAN scikit-learn DBSCAN Mnist over cosine
We first normalize all data points. Since cosine distance is identical to L2 on a unit sphere, we use scikit-leam DBSCAN on L2 compare with sDBSCAN on cosine distance. Given minPts 50, we set E = 0.11 as DBSCAN returns the highest NMI of 43% with the ground truth. sDBSCAN has two main parameters on cosine distance: top-m points closest/furthest closest/furthest random vectors to a point. These parameters govern the accuracy and efficiency of sDBSCAN. We set D 1, 022 and vary m, the next experiments.
random vector and top-k
Table 2: The data sets
Datasets
# clusters
Mnist
70,000
784
10
Pamap2
1,770,131
18
Mnist8m
8,100,000
784
10
17

---

Accuracy and efficiency of sDBSCAN. For SDBSCAN, we vary k = {40, 20..... 1), m (50, 100,.... ...,,.... 2, 000} such that it computes nearly the same 2km distances for each point. Ta- ble 3 shows the performance of multi-threading sDBSCAN on DBSCAN's outputs with e 50. We can see that sDBSCAN can recover DBSCAN's result with larger m. These findings justify our theoretical result as larger increases the chance of examining all points in the set S; and RG corresponding to the random vector I;, increasing the chance to recover the DBSCAN's output.
0. min,
In the last column with m 2, 000, sDBSCAN with achieves NMI of 95% but runs times slower than k = 1 since it nearly doubles the candidate size. sDBSCAN with all configurations runs least 3 faster than seikit-lear 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 min Pts and k; each point needs 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 fixed budget B 2km, Table 3 shows that k = 1, m = B/2 2 has higher accuracy but significantly higher running time than k Ko 1,m B/2k
While larger m and tend to increase the accuracy of sDBSCAN, they affect space and time complexity. Since often set D 1. 024 ensure Lemma 3 holds. and the memory resource is limited due to large data sets, we set m = minPts = 50 and & = (5, 10} for most experiments. Compared the ground truth, this setting does not affect the accuracy of sDBSCAN but uses significantly less computational resources than other configurations.
Rumning time of sDBSCAN's components with multi-threading. Given & 0.11, minPts = 50, A = 5. Table 4 shows the running time of sDBSCAN components on and 64 threads. On I 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 preprocess- ing (Alg. 2 and finding neighborhoods (Alg. B can be sped up with multi-threading, we achieve nearly 10x speedup with 64 threads. We also observe that the construction time of the randomized embeddings to support 1.2, L1, x2, and JS similar to the preprocessing time and is negligible to that of finding neighborhoods.
C.3 SOPTICS graphs Pamap2 and Mnist8m
We use the average top- 100 nearest neighbor distances of 100 sampled points to select suitable for SOPTICS. Figure 5 6 sOPTICS's graphs of Pamap2 and Mnist&m with minPls 50. As Pamap2 contains negative features, we only run on cosine, 1.2, and L. distances. SOPTICS uses D 024, a 2 E, d' 1, 024 runs in less than minutes and 11 minutes on Pamap2 and Mnist8m, respectively. Both figures show that L2 is less relevant than the other distances as it does show clear valley areas. This reflects the need use other distance measures rather than L2 for density-based clustering to achieve reasonable performance.
Table 3: Comparison of sDBSCAN with the DBSCAN's output on cosine distance with 0.11, minPts= = 50 over different & 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
Table 4: Running time of sDBSCAN components in seconds with D 1,024, k
5, m
min misnPts- = 50, = 0.11 on Mnist.
Threads
Preprocess
Find core points
Cluster
Total
thread
1.424
7.745 0.700
0.001
9.198
64 threads
0.160
0.001
0.862
18

---

reacho
100
Figure 5: sOPTICS's graphs on LI, L2 and cosine distances on Pamap2. Each runs within 2 minutes. scikit-learn OPTICS could not finish in hours.
Figure 6: sOPTICS's graphs on I.2, cosine, x2, and JS distances on Mnist8m. Each runs within 11 minutes. scikit-learn OPTICS could not finish in 4 hours.
C.4 Detailed comparison on Pamap2
As L.2 inferior to and cosine on sampling- DBSCAN, Table 5 reports the NMI scores and running time of studied algorithms on L1 and cosine distances over larger range of E. While sDBSCAN shows low NMI on cosine, its accuracy is 45% on I.1, which higher than sngDBSCAN on both cosine and L1. As sngDBSCAN uses p 0.01, each point will compute npp 17, 700 distances compared to 2km = 1000 of sDBSCAN. Hence, sDBSCAN runs up to 14x faster than sngDBSCAN on L2. On LI, sDBSCAN is nearly 100x faster than DBSCAN, By changing 5, m 200, sDBSCAN reaches 48% NMI on L1 and still runs less than minute. Compared
Table 5: The NMI on the best and running time comparison cosine and L1 distances on Pamap2. The upper algorithms run in multi-threading with 10x speedup compared thread while the lower ones use 1 thread.
Cosine (s 00.05 0.05))
LI (E E [30, 80))
Algorithms
NMI
Time
NMI
Time
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
Table 6: The NMI on the best and rumning time comparison of muultithreeadin DBSCAN variants on 1.2 and cosine on Mnist8m. Kernel k-means (k- 10) (1 runs in 15 minutes on a supercomputer of 32 nodes and achieves NMT 41 %.
L2 (s E [1100, 1500))
Cosine (e E [0.1, 0.2)
Algorithms
NMI
Time
NMI
Time
sDBSCAN-INN sDBSCAN
36%
8 min
1400
37 %
14 min 0.16
25%
min
1350
32%
min 0.16
SigDBSCAN (p 0.001)
22%
43 min
1150
26%
42 min
0.16
19

---

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 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 5x 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 minutes, even faster than any sampling- -baed implementations.
C.5 Detailed comparison on Mnistöm
As Mnist8m non-negative, we conduct experiments on cosine, 1.2, and I.1, x², and JS distances. Similar to Mnist, sOPTICS graphs show L.1 is inferior, so we do not report 1.1 here.
uDBSCAN++ and kDBSCAN++ with p 0.001 could not finish after hours. It not surprising as our multi-threading sngDBSCAN runs in nearly hour, and single thread sngDBSCAN is at least 4x faster than DBSCAN+ variants on Mnist. As cannot run scikit-learn k-means++, we use the result of 41% NMI given by fast kernel k-means (2l] 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 single node is similar to our conducted machine.
Table 6 and 7 summarize the performance of multi- threading IN,, sDBSCAN, and mgDBSCAN, including the NMI score on the best & and the running time, on 1.2, cosine, x² and IS. sDBSCAN-INN runs in at most 15 minutes and returns the highest NMI among DBSCAN variants with a peak of 38% NMI on x² and JS. We emphasize that kernel k-means with Nyström approximation [21 Table 4] also needs 15 minutes on a supercomputer and gives 41 % NMI.
sDBSCAN runs faster than SDBSCAN-ING INN as 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 x² and JS due to the faster distance computation. sDBSCAN runs 6.4x 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- 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.
C.6 Sensitivity of parameters used in random kernel features
We first show empirical results random kernel mappings that facilitate sDBSCAN and sOPTICS on LI, L2, x², and JS distance. We use Pamap2 for LI and L2 as it contains negative values and Mnist for x and JS as it does not contain negative values.
L1 and L2 on Pamap2. We carry out experiments to evaluate the sensitivity of the parameter a used on random kernel mappings on LI and L2. We fix & 10, 1024 and vary a for LI and L2. Figure 7 shows the accuracy of sDBSCAN on the recommended range of by sOPTICS graphs with (50, 100, 200, 400} for LI on Figure 8 and a {20, 40, 80, 160) for L.2 on Figure
minPts 50, D = 1024, d'
Table 7: The NMI on the best e and running time comparison of multi-threading DBSCAN variants on x² and IS distances on Mnist8m. Kernel k-means (k: 10) 21 runs in 15 minutes on supercomputer of 32 nodes and achieves NMI 41%.
x² (s E (0.1,02))
JS (s E [0.1, 0.2)
Algorithms
NMI
Time
NMI
Time
SDBSCAN-INN
38%
15 min
0.17
38%
15 min 0.15
sDBSCAN
32%
10 min
0.17
31%
10 min
0.15
SigDBSCAN (p 0.001)
28%
64 min
0.15
27%
64 min
0.17
20

---

114
100
60
DM)
(b 12
Figure 7: sDBSCAN's NMI on L1 and L.2 with various a on Pamaps with & = 10,m = mmn 50. Each runs in less than 20 seconds.
Figure 8: SOPTICS's s graphs on LI with various a on Pamaps with & 10, m = minPts 50. Each runs in less than 2 minutes.
PORD
POPP
Figure 9: SOPTICS's graphs on 1.2 with various a on Pamaps with & 10, m mén 50. Each runs in less than 2 minutes.
NM
2
fart
31
0:1
312
0.1
6.4
8.5
31t
017
0.0
JB
Figure 10: sDBSCAN's NMI on x² and JS with various a on Mnist with A = 10, m minPts = 50. Each runs in less than 20 seconds.
While L.1 provides 46% NMI, higher than just 40% NMI by 1.2, the setting a = 2s reaches the peak of NMI for both LI and L2. For example, sDBSCAN at ε = 50, a = 100 reaches NMI 46% for LI. sDBSCAN
15, 20 and 21, 40 reach NMI of 40% for L2. Also. the performance of sDBSCAN is not sensitive to the value a, especially with the guide of sOPTICS graphs. For example on L2 shown in Figure 9
80 shows 330 40]. The best values of these two a values are clearly on these ranges, as shown in Figure b). This observations appear again respectively.
160 suggests the suitable range [40, 50] while
{20, 40) for the range of [10, 20 and [20, 30),
x and JS on Mnist. We carry out experiments evaluate the sensitivity of the parameter d' used on random kernel mappings on x² and JS. We fix k 5, m minPls = 50, 1024 and vary d'. We note that (20) approximates x² and JS distance using the sampling approach, hence we set
21

---

nadt
3800
10.5 di 2332
-900
Figure 11: sOPTICS's graphs x² and JS with d' {3d, 5d) on Mnist with & = 5, minPts 50. Each runs in less than 3 seconds.
0Dbsan, m-00
30
00
/Cboaan m=100
40baaa m--25
400ppa mi-400
(b)) k-5
(b) 10
Figure 12: sDBSCAN's NMI on L1 with various k, m on Pamaps with min Pls = -00.
sampling interval as 0.4, as suggested on scikit-learn We also note that d' should set as (21 + 1)d for 1 N. Hence, set d' {3d, 5d) in our experiment.
Figure 11 shows SOPTICS graphs of x2 and on d' {3d, 5d]. They are very similar to the sOPTICS graphs on d' = d where the range of should be in [0.15, 0.2) for x² and [0.13, 0.18) for IS. Therefore, we can see that sDBSCAN with such recommended range of will reach the peak of accuracy.
Figure 10 shows that sDBSCAN reaches the peak
0.16 with x² and 0.14 with JS. Using d' 5d slightly increases the accuracy compared to d' = d though it is not significant on JS. Both measures offer the highest accuracy with 45% NMI.
C.7 Sensitivities of k, m of sDBSCAN
We carry out experiments on Pamap2 using L1 to study the performance of sDBSCAN on various values of k, m since L1 shows superiority compared to cosine and L2. We fix 200, D = 1024 and consider the range of time of sDBSCAN, we first fix k = (5, 10} and then increase
(30, 80). As increasing m will increase the memory and running
(50, 100, 200, 400).
Figure 12 shows that for fix k, increasing m slightly increases the accuracy of sDBSCAN. In
particular, sDBSCAN with m = 400 at E 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.
C.8 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 We all use A 10, 100, D 1024 for Pamap2 and Mnist8m.
Pamap2. Figure 13 shows sOPTICS graphs Pamap2 with L1, L,2, and cosine distances where we use a 200 for L1, and a 20 for L.2. shows again that 1.2 inferior than L. and cosine
approximation.p
22

---

100
02)
16) Cosin
Figure 13: sOPTICS's graphs on L1, L2, cosine Pamap2 with & runs in less than 5 minutes.
10, min Pts 100. Each
aDbscan
-
Obscan
il DDoicanee
KDbecanee
- e-sngDhacar
NMA
NMI
NM.1
(a)
(b) L2
Cosine
Figure 14: sDBSCAN's NMI on LI, L2, and cosine on Pamap2 with k = 10, m = minPts 100. Each runs within minute.
distances. Figure 14 shows the accuracy of sDBSCAN compared to other competitors Pamap2 with studied distances over the range of suggested by their corresponding sOPTICS graphs.
SDBSCAN reaches the highest NMI at the suggested range of by their sOPTICS graphs. In contrast, sampling-based approaches have to investigate a much wider range of & to achieve good performance. We observe that the performance of sDBSCAN is stable regarding min Pts though larger min Pl.s requires larger m7 which increases the running time. Each instance of sDBSCAN runs in 0.5 minutes, which is significantly faster than 3 minutes 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 L.2 distances.
Mnist8m. Figure 15 shows sOPTICS graphs on Mnist8m with L2, cosine, x² and JS distances where we use 4000 for 1.2, and d'' on x² and JS. shows the advantages of sDBSCAN on supporting many distances and predicts that cosine, x² and JS provide higher accuracy than 1.2.
Figure 16 shows the accuracy of sDBSCAN variants compared to other competitors on Mnist8m with studied distances over the range of & suggested by their corresponding sOPTICS graphs. We consider sDBSCAN- INN with the approximation INN heuristic to cluster border and noisy points detected by sDBSCAN. It shows again that sDBSCAN variants outperform sngDBSCAN on all studied distances. sDBSCAN-INN on a single computer nearly reaches the accuracy of kemel k-means (21] Regarding the speed, each instance of sDNSCAN- -NN runs in less than 15 minutes, which is the time requirement for kernel k k-means on supercomputer.
23

---

Figure 15: sOPTICS's graphs on L2, cosine, x2, and JS distances on Mnist8m with A: 10, m min 100. Each runs in less than 20 minutes.
NMI
00
(8) Cosine
x
JB
Figure 16: sDBSCAN's NMI on L2, cosine, x², and JS Mnist8m with i: = 10, minPts 100. Each runs within 20 minutes.
C.9 Clustering accuracy with NMI and CC on Mnist and Pamap2
Figures 17 and 18 show the clustering accuracy with NMI and CC on Mnist and Pamap2 of sDbscan, DBSCAN, uDBSCAN++, KDBSCAN++, SngDBSCAN on minPtss 50. These figures show that sDBSCAN is competitive to other DBSCAN variants on different clustering accuracy measures.
Bassan
(c) Dbscan variants (L.1)
(9 Dasccn variants (L2)
(g) Dbscan variants (Cosine)
(h) Dbscan variants (JS)
Cascan
Discaa
0200
3000
1900
1100
1200
100
1300
3.11
8.02
214
C5s
33
Dbscan variants (L.1)
Doscan variants (L2)
Dbscan variants (Cosine)
(h) Dbscan variants
Figure 17: NMI and CC of DBSCAN variants on Mnist with L1, L2, cosine, JS over the range of suggested by sOPTICS. Cosine and JS give the highest clustering accuracy.
24

---

sDbscan
Dbscan
DDbscan++
kDbscan+
sng Dbscan
NMI
80
NMI
30
NMI
20
20
10
40
0.00
0.035
0.04
0.565
(a) L1
(b) L2
Cosine
20
10
8
8
00
40
50
60
70
12
15
21
0.02
0.985
0.00
0.035
0.04
0.045
(a) L1
(b) L2
(c) Cosine
Figure 18: NMI and CC DBSCAN variants on Pamap2 with L1, L2, cosine over the range of suggested by sOPTICS. L1 gives the highest clustering accuracy.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We show how to scale up DBSCAN and OPTICS with million-point data within a few minutes. After preprocessing, our proposed sDBSCAN and sOPTICS only need O pls nn) distance computations and additional (mmiPlss n) extra space compared to O(??) DBSCAN and OPTICS.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The theoretical result of sDBSCAN uses the asymptotic property of extreme order statisties that require D - 30, and an assumption on the strong connection of density- based components of a cluster. Nevertheless, we observe that D = 1024 works very well in practice and the cost of executing random projections is significantly smaller than the cost of distance computations.
Guidelines:
25

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.mitations" section in their paper:
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For Theorem 1, we use the result of Lemma 1, which requires the asymptotic property of extreme order statistics, and the need to maintain the set S; and Rł whose sizes depend on the neighborhood around the random vector r, For Lemma 3, we assume that the event any point x E (g) is ranked higher than all y E X Bg (q) is independent.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
All assumptions should be clearly stated or referenced
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
We release the source code, parameter setting guidelines, and data set for reproducibility.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
26

---

If the paper includes experiments, a No answer to this question will not be perceived
well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The appendix describes detailed clustering competitors and their settings. Our released sDBSCAN and sOPTICS on Github has Python wrappers to test with scikit-learn competitors.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ctatlss.ccppbblcc/// hwwpbbliccguiieeee cilee//Coeeubbiis.e cotuuummsssiiiii ssionolicc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
27

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We state how to set parameter settings for other competitors, and how to set parameter settings for DBSCAN variants via sOPTICS.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them. The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report the error bar on the clustering accuracy (AMI, NMI, and CC),
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com-- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide detailed computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
28

---

The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://p///.ea......cco////aaaaa
Answer: [Yes]
Justification:
We anonymized our work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper proposes new density-based clustering algorithm that can be run on any nigh-dimensional data set.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No risks.
Guidelines:
The answer NA means that the paper poses such risks.
29

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use released data sets, including Mnist, Mnist8m, Pamap2 which are very popular in research community.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We propose new algorithm.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing.
Guidelines:
30

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "fP6jf93hwt", "reviewer": "Reviewer_QDtd", "summary": "Paper studies scalable algorithms for DBSCAN, a popular clustering method. \nIn DBSCAN, each point considers a radius of epsilon, and is called \"core\" if it has at least m points in the epsilon ball.\nThen, each core point is connected to all other points (core or non-core) in its epsilon ball.\n\nFinally, connected components are output as the clusters. Popular method used for clustering different types of datasets when k is not known, or the metric is not euclidean. However, slow to compute since identifying core points itself is cumbersome operation.\n\nThis paper tries to address the slowness (for euclidean vectors) by using random projections, a la LSH or locality sensitive hashing. Indeed, suppose all vectors are unit norm. Then suppose x is a database point and y is close to it, i.e., large inner product. We need to quickly identify if y is in the epsilon ball of x or not, and repeat this for all y, to determine if x is a core point or not. To this end, then suppose we draw many random directions in space, and we find that there is a direction r which has large inner product with both x and y. Then we can use r as a witness to conclude that y is likely to be in the ball of x. \nTo capture this, each point x will remember which are the top m random lines w.r.t inner product. And each line r will remember the top m' points w.r.t inner product. So when x will try to check if it is core or not, we dont scan with all points to see how many are in the epsilon ball. We simply scan the points which are in the top m' for the m random directions close to x, reducing the work needed to m*m' checks.\nIf we set m and m' suitably, we can prove that most of the real points are captured and this estimate works well.\n\nThe paper also shows theoretical guarantees under some assumptions on the connectivity of the clusters, that if the true connected components are sufficiently connected, then this algorithm will recover the connected components correctly. \n\nThe paper also gives emperical evals against SoTA implementations / approximations of DBSCAN and shows faster compute, and better Quality across different datasets.", "questions": "How do you extend this method to other metrics, non euclidean? I presume that one of the appeals of DBSCAN is the non-reliance of euclidean metric.\nHow does your method compare with LSH? So I will build some LSH and each point x will only look inside the bucket it lands into to check if it is core or not.\nMore generally I can use any SOTA approx. nearest neighbor method? Example HNSW or FAISS or SCANN? Will that not work?\nWhy dont you consider other real-world datasets generated by the Neural Networks, like OpenAI embeddings, etc? They represent a growing and fundamental workload right?", "limitations": "Would be good to include limitations section in paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "DBSCAN seems like a popular tool, and making it more scalable is important problem. \nAlgo comes with theoretical backing, and is good empriically.\nPaper is reasonably well written.", "weaknesses": "While authors try to compare with other works, not sure if the comparisons are clear enough as to why prior techniques dont do as well. In particular see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We will address the raised questions below.\n\n**Q1) How do you extend this method to other metrics, non euclidean? I presume that one of the appeals of DBSCAN is the non-reliance of euclidean metric.**\n\nsDBSCAN starts from cosine distance. To extend sDBSCAN on L1, L2, χ2, JS, we resort to kernel features f.\nWe map x $\\mapsto$ f(x) such that E[<f(x), f(y)>] = k(x, y) where k(., .) is a monotone function of other metrics.\nExtending sDBSCAN to non-metric distance is not trivial as the kernel matrix M is not positive-definite anymore.\nA possible solution is to use the feature embeddings into reproducing kernel **Krein** space [a, b].\nSince [b] can learn binary embeddings to preserve pair-wise non-metric distance, we can build sDBSCAN on such embeddings designed for non-metric distances.\n\n[a] Kernel Discriminant Analysis for Positive Definite and Indefinite Kernels - TPAMI 09\n\n[b] Non-Metric Locality-Sensitive Hashing - AAAI 10\n\n\n**Q2) How does your method compare with LSH? So I will build some LSH and each point x will only look inside the bucket it lands into to check if it is core or not.**\n\nWhile sDBSCAN and LSH [26] use random projections, they are indeed different.\nFor sDBSCAN, for each random vector $r_i$, we find top-m' points closest to $r_i$. These points are used as the candidate set for any point x closest to $r_i$.\nThe random vectors in sDBSCAN can be seen as random landmark/pivot points, and their neighborhoods (e.g. top-m' points) are useful to find the neighborhood of any point x closest to the pivot points. \nsDBSCAN indeed simulates the small world phenomenon \"Neighbors of neighbors tend to be neighbors\".\nFor each point x, sDBSCAN finds top-m closet random vector to get m * m' candidates, hence the time complexity is O(dmm') and the extra space to store neighborhood is O(mm').\n\nFor LSH, for each point x, we find the closest random vector. \n**All** points closest to the same random vector (i.e. bucket) will be the candidates.\nHence, the size of the bucket corresponding to $r_i$ varies, e.g. large if $r_i$ points to high-density regions or small if $r_i$ points to low-density regions.\nWe would need L = n^ρ hash tables to ensure good accuracy in finding core points where ρ is an LSH parameter.\nBuilding L = n^ρ hash tables requires O(n ^{1 + ρ}) space and O(dn ^{1 + ρ}) time.\nThis cost is significant, especially compared to sDBSCAN's space and time complexity.\n\nTo reduce the number of hash tables, practical multi-probing LSH schemes probe nearby buckets to get more candidates.\nSince we cannot control the collision probability of nearby buckets, there are likely many far-away points in the probing buckets.\nCompared to sDBSCAN, each point has to compute a fixed O(m*m') distances, and the preprocessing takes only around 10% of the total execution time (See Tab 4 in Appendix).\n\nGiven a core point x, sDBSCAN tends to find the points closest to x, then approximates well the core distance (i.e. minPts-NN distance) of x.\nIt is very useful since sOPTICS uses the core distance to compute the reachablity-distance, and to visualize the clustering structure (e.g. # valleys).\nOur sOPTICS shares similar execution time with sDBSCAN, and suggests the range of value of ε.\nWe can see that sDBSCAN reaches the peak of accuracy given one value of ε in such range.\n\nSince LSH is designed for approximate ε-near neighbor search, it seems difficult to select potential closest points to x if the bucket of x is dense, hence it is challenging to have scalable OPTICS and DBSCAN variants with LSH.\n\n**Q3)  More generally I can use any SOTA approx. nearest neighbor method? Example HNSW or FAISS or SCANN? Will that not work?** \n\nSimilar to LSH, the cost of constructing the index dominates the clustering time though there are still n queries to answer.\nHNSW builds an index in O(dn^2) time. \nWe found that constructing HSNW data structure on 1.7M points (Pamap2) for small indexing time parameters (efConstruct = 128, m = 32) needs 7 seconds, which is similar to the running time of sDBSCAN.\nBuilding HNSW index on Mnist8m take more time than running sDBSCAN.\n\nFaiss and Scann need a Lloyd’s algorithm to learn the product quantization for the index.\nThis learning phase requires O(dn * nlist) where nlist is the number of clusters.\nCompared to sDBSCAN with m = 10, m' = 50, then if nlist = 500, the learning phase has a similar cost of finding core points of sDBSCAN. \n\nWe detailed the indexing time of Faiss, Scann, Hnsw on the response.pdf.\n\nsDBSCAN easily supports streaming data where you can insert or delete any point in the data set.\nFor HNSW, Faiss and Scann, we would need to rebuild the data structure after deleting or inserting a sufficient number of points.\n\n**Q4) Why dont you consider other real-world datasets generated by the Neural Networks, like OpenAI embeddings, etc? They represent a growing and fundamental workload right?**\n\nThank you for the suggestion.\nWe indeed plan to run sDBSCAN on pre-trained image sets to evaluate its utility in practical applications.\nHowever, our concern is whether we take into account the time of computing embeddings into the preprocessing time.\nFor example, we currently test Mnist/Mnist8m data set whose dimensions represent pixel values.\nIf no, then we consider the pre-trained data set as a new data set.\nIf yes, then extracting the OpenAI embeddings will dominate the running time of clustering, especially with large models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xj7AasOtYd", "reviewer": "Reviewer_C5J7", "summary": "DBSCAN is a popular density-based clustering algorithm. For a parameter $\\epsilon$, a point $p \\in X$ is core if its $\\epsilon$-ball is large (over $minPts$ in size). Core points within each others' $\\epsilon$-balls are then connected via an edge, non-core points within $\\epsilon$-balls are considered cluster borders, and all other non-core points are considered noise. OPTICS is an algorithm which visualizes, across all $\\epsilon$ selections, the density of a clustering to assist in the selection of $\\epsilon$.\n\nThis paper focuses on improving the space efficiency of the first step of DBSCAN, which finds the $\\epsilon$-neighborhoods of all points. Normally this requires $O(n^2)$ space. Following sampling-based approaches, they first construct a random projection-based index which allows them to identify $\\epsilon$-neighborhoods without fully constructing them. This pre-existing method projects points onto vectors whose indices are $~N(0,1)$, and leverages the fact that if $r$ is the random vector maximizing $|q^Tr|$, then $|x^Tr| \\approx |x^Tq|$. Thus, $\\epsilon$-balls can be approximated using the top-$k$ random vectors and then the top-$m=O(minPoints)$ nearest points to those random vectors. The resulting algorithm runs in $O(dk\\cdot minPts)$ time and space to process each point, where dimension $d$ denotes the time for distance computations. If $k$ is constant, then with preprocessing, the total runtime is $O(d\\cdot minPts + nD\\log(D))$, which is subquadratic if $D = o(n)$. The space is $O(nk + D\\cdot minPts)$, which is a good improvement.\n\nTo show their theoretical guarantees, they instead keep the top closest and furthest points ($R$ and $S$) to any random vector $r$. To see if a point is sufficiently close to $r$ to be in an $\\epsilon$-ball, its distance is computed from all of $R$ and $S$. This boosts the probability that, given q is in the $\\epsilon$-ball, from $1/2$ to $1-(1/2)^k$. In other words, they sample each edge in DBSCAN's resulting graph with probability $1-(1/2)^k$, which (by a known result) yields a graph with the same connected components for sufficiently large $k$. This argument holds in practice when they just use the top-$m$ points instead of these sets $R$ and $S$, though I was unsure of their reasoning.\n\nFinally, due to sampling, this process may over-label points as noise. Afterwards, to combat this, they run a 1NN algorithm on perceived \"noise\" points to validate they are actually noise, using samples from all other points as training data. With sparse enough sampling, this added runtime is negligible.\n\nThey also test their theoretical findings with experiments. The main takeaway is that the new algorithm provides comparable runtime and accuracy on a single machine as k-means does on a supercomputer.", "questions": "1. \"We observe that such memory constraint is the primary hurdle limiting the current scikit-learn implementation on million-point data\nsets\" -- This is presumably very dependent on hardware, input, etc, right? I feel like the way you've stated this is a bit too strongly. Could you say something more like \"We observe that on our hardware, such memory...\"?\n\n2. In algorithm 2, why do you also need the furthest vectors?\n\n3. In Theorem 1, you claim that you can assume t would be large because, otherwise, you should select different parameters anyways. What happens if t isn't large? You still need to be able to identify the parameters as bad selections. Does your algorithm allow identifying this if t isn't large, or do your assumptions fall apart?\n\n4. I did not understand your selection of D - and I did not see the definition of D. Can you clarify: what is D, what it affects in Lemma 3, and why D=1,024 is adequate? Is D the dimension of the input data?\n\n5. Can you clarify exactly what was a novel contribution and what was repurposed from prior works?", "limitations": "I do not see anything of concern.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "DBSCAN is a very popular and important clustering method with a wide impact. Any improvements to it, therefore, are important. The authors show nice, simple, and theoretically-backed methods to improve the efficiency of DBSCAN. While scalability has been studied before, they are the first to study it with theoretical guarantees on the quality of the scaled methods. The methods are non-trivial and interesting to see how they piece together to get these results. For the most part, the paper is nicely written.", "weaknesses": "There are a few parts in the paper that are dense and hard to understand. In addition, I'm unsure about the novelty of the work - which parts were actual new methodologies that they used? Many of their methods and lemmas seemed to cite past techniques. I put this in the Questions section so they may respond.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We will address the raised questions below.\n\n**Q1) \"We observe that such memory constraint is the primary hurdle limiting the current scikit-learn implementation on million-point data sets\" -- This is presumably very dependent on hardware, input, etc, right? I feel like the way you've stated this is a bit too strongly. Could you say something more like \"We observe that on our hardware, such memory...\"?**\n\nWe agree and will fix it.\n\nFor more specification, our machine has 128GB of RAM and tests on Pamap2 (n = 1.7M points) with size of 0.64 GB.\nWe could not run spectral clustering, kernel k-means, DBSCAN, OPTICS provided by scikit-learn on Pamap2.\nFor spectral clustering and kernel k-means, scikit-learn needs O(n^2) space to store pairwise distance matrix.\nWe found from scikit-learn description: \"This implementation has a worst case memory complexity of `O({n}^2)`, which can occur when the `eps` param is large and `minPts` is low, while the original DBSCAN only uses linear memory.\"\n\nOur implemented DBSCAN using linear memory works on Pamap2 but requires ~ 0.5 hours with multi-threading.\n\n**Q2) In algorithm 2, why do you also need the furthest vectors?**\n\nGiven D random vectors $r_1, \\ldots r_D$, if x is furthest to $r_1$, then $x$ must be closest to $-r_1$.\nWe use the furthest vectors to partition the unit sphere with 2D vectors $r_1, \\ldots, r_D$ and $-r_1, \\ldots, -r_D$, and Lemma 1 still holds for top-k closest and furthest random vectors due to the symmetric Gaussian distribution.\n\n**Q3) In Theorem 1, you claim that you can assume t would be large because, otherwise, you should select different parameters anyways. What happens if t isn't large? You still need to be able to identify the parameters as bad selections. Does your algorithm allow identifying this if t isn't large, or do your assumptions fall apart?**\n\nWe note that density-based clustering will link nearby core points together to form the cluster skeleton.\nHence this assumption is needed to guarantee any density-based clustering. \nConsider the case where core points x, y where dist(x, y) = ε where B(x, ε) $\\cap$ B(y, ε) = {x, y}. \nThere is only **one** edge $xy$ connecting B(x, ε) and B(y, ε).\nIn the worst case, if any approximate DBSCAN misses identifying $xy$ while approximating B(x, ε) and B(y, ε), it cannot recover DBSCAN's output.\nThe assumption t = O(log(n)) makes the density-based cluster C not thin at anywhere, i.e. there are t paths $x p_i y$ that connect x, y together where $p_i$ are the core points in B(x, ε) $\\cap$ B(y, ε).\n\nWhen minPts = 50 (note that t = log(8M) = 16), we expect many core points will have more than 16 core points within their ε-neighborhoods. This happens in practice since if x is in high-density regions, |B(x, ε)| >> minPts.\n\nIf t is not large enough, there might be a thin region separating the density-based cluster.\nThen we should choose ε larger to increase the number of core points in ε-neighborhood, and hence increasing t.\nIn practice, we use sOPTICS graphs to visualize the cluster structure and to select ε large enough to separate valleys.\nThis will give good accuracy.\nFig 1c, 1d shows that ε should be closer to 0.15 to separate 4 clusters, and Fig 1g, 1h shows that ε = 0.14 reaches the peak.\n\nA variant of assumption of t was used in [15] to guarantee the recovery of DBSCAN results of the sngDBSCAN.\nBesides, [15] also needs other 2 strong assumptions regarding the data distribution (See Assumption 1 in [15]) while we do not need them.\n\n**Q4) I did not understand your selection of D - and I did not see the definition of D. Can you clarify: what is D, what it affects in Lemma 3, and why D=1,024 is adequate? Is D the dimension of the input data?**\n\nD is the number of random vectors $r_i \\sim N(0, 1)^d$ where d is input dimension.\nIndeed, Lemma 1 holds when D $\\rightarrow$ ∞ , and in practice, we observe D = 1024 suffices for all 3 data sets.\nThis setting was used in previous works [22, 23].\nOn Lemma 3, we show that if $D = n^{1 / (k \\alpha^2)}$ where $\\alpha$ depends on the data distribution, and assume that such $D$ is large enough to ensure Lemma 1 holds, then we can find core points by maintaining just minPts points closest to each random vector.\nThis saves the space and time complexity of sDBSCAN in practice.\n\n**Q5) Can you clarify exactly what was a novel contribution and what was repurposed from prior works?**\n\nWe believe that the novel contribution is to enable density-based clustering (sDBSCAN) work on million-point data sets, and support many popular distance measures with a visual tool (sOPTICS) to guide the important parameter ε without ground truth.\nBoth sDBSCAN and sOPTICS run fast and use small memory overheads compared to recent DBSCAN variants.\n\nWe expect sDBSCAN will be as popular as k-means in clustering analysis due to its time and space complexity.\nsDBSCAN supports many distance measures, including L1, L2, $\\chi^2$, JS, while k-means works on L2 distance, and kernel k-means and spectral clustering needs O(n^2) space to store the kernel matrix and the prior knowledge of k.\n\nPrior work scaling up DBSCAN limits on L2 [6, 12, 13, 14] or cannot achieve good accuracy [15].\nEspecially, none of these works offer an efficient visual tool to select relevant parameter ε.\nWe can see the execution time of sOPTICS + sDBSCAN is still much faster than sngDBSCAN [15] whereas an efficient heuristic to select relevant values of ε for sngDBSCAN seems difficult due to the natural of sampling.\n\nTo prove theoretical guarantees for sDBSCAN, we use the recent result of Lemma 1 [22] in 2021 and the seminar result of Lemma 2 [27] in 1999.\nThese theoretical foundations enable us to explain random landmark/pivots vectors and their neighborhoods are sufficient for density-based clustering.\nIt works well in practice due to the small world phenomenon \"Neighbors of neighbors tend to be neighbors\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UvoPR1971Q", "reviewer": "Reviewer_UCFw", "summary": "The authors present an accelerated variant of DBSCAN based on random projections. Theoretical results are provided that indicate that this method will yield a similar clustering as the original DBSCAN. Experiments on real-world data show that this method indeed achieves similar performance at a fraction of the computational cost.", "questions": "How fast should $D$ grow be in terms of $d,n$ in order for Lemma 1 to hold?\n\nThe assumption regarding $t$ described between Lemma 2 and Theorem 1 (once again: please enable line numbers) seems somewhat strong. Could you comment on this?\n\nIn Lemma 3, $D=n^{1/k\\alpha^2_*}$ is written. Does this mean $D=n^{\\alpha^2_*/k}$ or $D=n^{k^{-1}\\alpha_*^{-2}}$? Please change this expression for clarification.", "limitations": "Usage of NMI and missing proof of Lemma 1 (see above)", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The proposed method seems to significantly improve upon the running time of DBSCAN while yielding similar performance.\n\nThe authors support their claims with theoretical proofs.", "weaknesses": "The paper is hard to read due to many language errors, odd sentences and sloppy formulations.\n\nLemma 1 seems to be a crucial result for this work, but the proof is not given. Even if it was proven in prior work, it might be worth-while to include the proof. At the very least, the formulation of Lemma 1 should be greatly improved, because the current formulation is rather sloppy: \n* $\\mathcal{S}^{d-1}$ in Lemma 1 is not introduced.\n* The $\\sim$ in Lemma 1 is usually used to indicate that the LHS follows the distribution given on the RHS. But here, the result seems to concern some convergence in distribution, which is usually denoted by $\\stackrel{\\mathcal{D}}{\\rightarrow}$. Please improve the formulation of this important Lemma. \n* When you say that the coordinates of $r_i$ are drawn from a standard Gaussian, then you cannot simply say \"assume w.l.o.g.\" that $r_1=\\arg\\max_i|q^\\top r_i|$. What you could do instead, is formulate your result in terms of $r^*=\\arg\\max_i|q^\\top r_i|$.\n\nThe method is validated using the NMI. NMI is known the be biased towards fine-grained partitions [1,2]. Please use a different validation measure, like the Adjusted Mutual Information [1] or the correlation coefficient [2]\n\nMinor comments:\n* Line numbers would be helpful in the reviewing process. Please use the NeurIPS latex template without changing any of the settings.\n* The plots shown in Figure 1 are too small and the labels are not readable. \n\n[1] Vinh, N. X., Epps, J., and Bailey, J. Information theoretic measures for clusterings comparison: Variants, properties,\nnormalization and correction for chance. The Journal of Machine Learning Research, 11:2837–2854, 2010.\n[2] Gösgens, M. M., Tikhonov, A., & Prokhorenkova, L. (2021, July). Systematic analysis of cluster similarity indices: How to validate validation measures. In International Conference on Machine Learning (pp. 3799-3808). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We will address the raised weaknesses and questions below.\n\n**W1: Regarding notation and proof of Lemma 1**\n\nWe agree with your comments regarding sloppy formulation and will fix them all.\nSince we start sDBSCAN with cosine distance, we state Lemma 1 as a simplified version of [22] on unit sphere $S^{d-1}$ \nIndeed, Lemma 1 is similar to Lemma 2 in [23] as [23] uses this result to scale up approximate kNN on cosine.\n\nWe will add a proof of Lemma 1 in the appendix to make the paper stand-alone.\nLemma 1 follows the results of [22] in case data points are on a unit sphere, and it holds when $D \\rightarrow \\infty$.\n\n**W2: The validation measure NMI, Adjusted Mutual Information (AMI) or the correlation coefficient**\n\nWe have both AMI and NMI. Both scores are very similar (within 1 ‰) in our empirical results.\nThe reason might be that the 3 used data sets do not have any small clusters.\nWe report NMI since we want to compare it with the reported NMI of the kernel k-means [21] as [21] does not have AMI scores on Mnist8m.\nWe found that sngDBSCAN's AMI is even lower than its NMI (See the figure in response.pdf).\n\nIf we understand correctly, to compute the correlation coefficient, we have to form the pair-counting indices vector of size $n^2$ where each component (i, j) = 1 if $x_i$ and $x_j$ are in the same cluster.\nSuch measurement seems nontrivial to compute given $n$ > 1M points (Pamap2 and Mnist8m) due to its space complexity.\n\n**Q1) How fast D grows with d, n to ensure Lemma 1 holds?**\n\nFor our theoretical analysis, we use Lemma 1 with $D \\rightarrow \\infty$, and we stated on Limitations.\n\nThe non-asymptotic results of Lemma 1 are complicated.\nWe will sketch it here, and will add a full proof into the appendix.\n\nLet $x, q \\in S^{d - 1}$ and $D$ random vectors $r_i$ whose coordinates are randomly selected from $N(0, 1)$.\nGiven $\\rho = x^{\\top}q$, and let $X_i = x^{\\top}r_i, Q_i = q^{\\top}r_i$, we  have $(X_i, Q_i) \\sim N(0, 0, 1, 1, \\rho)$.\nIn particular, $X_i = Q_i * \\rho + Z_i$ where $Z_i \\sim N(0, 1 - \\rho^2)$\n\nWe assume that $r_* = \\arg\\max_{r_i} | q^{\\top}r_i | = \\arg\\max_{r_i}  q^{\\top}r_i $.\n$Q_*$ is the maximum value of $D$ random normal variables.\n\nWe first show that $D = e^{1/\\delta^2}$ for $0 < \\delta = 1 / \\sqrt{\\log{D}}< 1$, then with probability at least $1 - 2\\delta$,\n$\\sqrt{2 \\log{D}} (1 - o(\\log{\\log{D}} / \\log{D})) \\leq Q_* \\leq \\sqrt{2 \\log{D}}$.\n\nAfter that, we use Chernoff tail bounds of normal variables $Z_* = X_* - \\rho * Q_*$ to bound the probability that $X_*$ deviates from its expectation, i.e. $\\rho \\sqrt{2 \\log{D}}$.\n\nWhile the Gaussian distribution of $X_*$ in Lemma 1 requires $D \\rightarrow \\infty$, the non-asymptotic tail bounds of $X_*$ show the concentration of $X_*$ around its expectation with high probability $1 - 2 / \\sqrt{\\log{D}}$.\n\nOn Lemma 3, we show that if $D = n^{1 / (k \\alpha^2)}$ where $\\alpha$ depends on the data distribution, and assume that such $D$ is large enough to ensure Lemma 1 holds, then we can find core points by maintaining just $minPts$ points closest to each random vector.\nThis saves the space and time complexity of sDBSCAN in practice.\nWe found that $D = 1024$ works well in 3 used data sets, including Mnist8m with n = 8.1M, d = 784.\nWe think it is due to the small world phenomenon \"Neighbors of neighbors tend to be neighbors\".\nIf $x$ is closest to the random vector $r_*$, then $x$ tends to be close to $r_*$'s neighbors.\n\n**Q2) The assumption regarding the strong connection of a density-based cluster $C_i$ of size $n_i$: For any two close core points $x, y \\in C_i, dist(x, y) < \\epsilon$, their neighborhoods have to share at least $t = O(\\log{n_i})$ common core points. \nWith this assumption, sDBSCAN can recover DBSCAN cluster $C_i$ with probability at least $1 - 1/n_i$.**\n\nWe note that density-based clustering will link only core points together to form the cluster skeleton.\nHence this assumption is needed to guarantee any density-based clustering. \nConsider the case where core points $x, y, dist(x, y) = \\epsilon$ where $B(x, \\epsilon) \\cap B(y, \\epsilon) =$ {$x, y$}. \nThere is only one edge $xy$ connecting $B(x, \\epsilon)$  and $B(y, \\epsilon) $.\nIn the worst case, if any approximate DBSCAN misses identifying $xy$ while approximating $B(x, \\epsilon)$ and $B(y, \\epsilon)$, it cannot recover DBSCAN's output.\nThe assumption $t = O(\\log{n})$ makes the density-based cluster $C$ not thin at anywhere, i.e. there are $t$ paths $x p_i y$ connecting $x, y$ together where the core point $p_i \\in B(x, \\epsilon) \\cap B(y, \\epsilon)$.\n\nWhen $minPts = 50$ (note that $t$ = log(8M) = 16), we expect many core points will have more than 16 core points within their $\\epsilon$-neighborhoods.\nThis happens in practice since if the core point $x$ tends to be in high-density regions and $|B(x, \\epsilon)| >> minPts$.\nSince we use the minPts points closest to random vectors to find $\\epsilon$-neighborhoods of core points, if both core points share the same closest random vectors, their neighborhoods tend to contain the same core points, and hence be connected together.\n\nIf $t$ is not large enough, there might be a thin region separating the density-based cluster. \nThen we should choose $\\epsilon$ larger to increase the number of points in $\\epsilon$-neighborhood, and hence increasing $t$.\nIn practice, we use sOPTICS graphs to visualize the cluster structure and to select $\\epsilon$ large enough to separate valleys.\nThis will give good accuracy.\nFig 1c, 1d shows that $\\epsilon$ should be closer to 0.15 to separate 4 clusters, and Fig 1g, 1h shows that $\\epsilon$ = 0.14 reaches the peak.\n\nA variant of the assumption of $t$ was used in [15] to guarantee the recovery of sngDBSCAN on the DBSCAN's output.\nBesides, [15] also needs other 2 strong assumptions regarding the data distribution (See Assumption 1 in [15]).\n\n**Q3) Regarding D in Lemma 3.**\n\nWe will fix it: $D = n^{k^{-1} \\alpha_*^{-2}}$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Po930dfjpU", "reviewer": "Reviewer_gFWb", "summary": "This paper proposes a scalable DBSCAN algorithm which facilitates random projection to quickly approximate the $\\varepsilon$-neighborhood. The proposed algorithm speeds up conventional DBSCAN algorithms by orders of magnitude.", "questions": "See W1~W6.", "limitations": "The authors discussed the limitations about a sufficiently large number of random vectors, which sound reasonable.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The proposed algorithm speeds up conventional DBSCAN algorithms by orders of magnitude.\n\nS2. The formal proof as well as time complexity analysis are presented in the paper. \n\nS3. The authors also provide a multi-thread implementation of the proposed algorithm for much faster execution.", "weaknesses": "W1. The main contribution may not be very high, because the core idea of approximating $\\varepsilon$-neighborhood is borrowed from the previous work [22].\n\nW2. It is very important to provide a heuristic or guideline for setting the value of $\\varepsilon$, because the peak reached at different values among the proposed algorithm and previous algorithms. For this purpose, the authors present a variation of OPTICS, i.e., sOPTICS, which suggests a **range** of $\\varepsilon$. As this range is quite wide, I am skeptical about the practical usability of the proposed algorithm. How do you pick the best value while you do not know the ground-truth clustering result in practice?\n\nW3. More datasets need to be included for the evaluation. Only three datasets may not be sufficient to show the superiority of the proposed algorithm.\n\nW4. The organization of this paper has a critical problem. Even though it is claimed that there are two important algorithms, sDBSCAN and sOPTICS, the entire description of sOPTICS is only presented in the supplementary material.\n\nW5. It is not clear whether the preprocessing time is included in the reported execution time. If not, I believe that the proposed algorithm is too much favored in the evaluation.\n\nW6. The clustering accuracy is often lower than those of the conventional algorithms at the cost of fast execution. To achieve a good accuracy, more hyperparameters need to be tuned carefully.\n\nW7. (Minor) NeurIPS may not be the best venue for this paper. KDD best suits this paper.\n\n---\n\nAfter rebuttal, I have increased my rating to 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We will address the raised weakness below.\n\n**W1. The main contribution may not be very high, because the core idea of approximating ε-neighborhood is borrowed from the previous work [22].**\n\nsDBSCAN uses the recent result in [22], i.e. the property of random projections given the number of vectors D is significantly large.\nHowever, this new property has **not** been explored in any clustering algorithm.\nRandom projection is used as dimensionality reduction with D = O(log(n)) to speed up the k-means [a] and DBSCAN [13].\nWe found that [13] does not offer theoretical guarantees on the DBSCAN result, and we could not even run [13] on Mnist with n=70,000.\n\nBuilding on the theory of [22], we prove that sDBSCAN can recover the DBSCAN's output with good probability.\nThis theoretical result aligns with previous works, e.g. [a] that guarantees the quality of k-means using random projections.\nFor practicality, we show that by considering only top-minPts points closet to the random vectors, sDBSCAN can detect core points with high probability (Lemma 3).\nThis scales up sDBSCAN in both time and **space** complexity.\n\nWe found that space complexity is the main issue of several kernel-based clustering and DBSCAN since we have to maintain O(n^2) pairwise distances.\nOur machine with 128GB of RAM cannot run spectral clustering or DBSCAN/OPTICS provided by scikit-learn with million-point data sets.\nsDBSCAN/sOPTICS can run on Mnist8m of size 42GB due to their low memory overheads.\n\nTherefore, we believe that our contribution (especially in practice) is significant.\nWe hope sDBSCAN and its parameter guideline sOPTICS that support various distances (Cosine, L1, L2, χ², JS) will be as popular as k-means in clustering analysis.\n\n[a] NIPS 10 - Random Projections for k-means Clustering\n\n**W2. The authors present a variation of OPTICS, i.e., sOPTICS, which suggests a range of ε. As this range is quite wide, I am skeptical about the practical usability of the proposed algorithm. How do you pick the best value while you do not know the ground-truth clustering result in practice?**\n\nSelecting ε without ground truth is exactly the contribution of sOPTICS graphs where each valley corresponds to a cluster.\nWe can also select better metrics to run sDBSCAN based on sOPTICS graphs with clear valleys (discussed in Sec 4.1).\n\nOn Cosine (Fig 1c), we select ε in [0.1 0.15] as any ε in this range can separate the valleys of the sOPTICS graph.\nAmong 6 values of ε {0.1, 0.11, 0.12, 0.13, 0.14, 0.15}, sDBSCAN (Fig 1g) can reach DBSCAN's accuracy.\nOn the selected range based on sOPTICS, one value of ε gives the accuracy peak on all 3 data sets even with various parameter settings (minPts, σ, d' on Section B6, B7, B8).\n\nThe sampling competitors: sngDBSCAN [15], DBSCAN++ [14] do not offer any tool to suggest ε, and different sampling strategies even require different optimal values of ε!\n\nAs sDBSCAN can nearly recover DBSCAN's output with NMI of 95% (Tab 3 in Appendix) with the same value of (ε, minPts), if DBSCAN works well on a data set without ground truth, sDBSCAN can achieve similar performance but run much faster.\n\n**W3. More datasets need to be included for the evaluation. Only three datasets may not be sufficient to show the\nsuperiority of the proposed algorithm.**\n\nWe agree and will add new datasets (e.g. KDDCup or deep learning-based pretrained data sets).\n\n**W4. The organization of this paper has a critical problem. Even though it is claimed that there are two important\nalgorithms, sDBSCAN and sOPTICS, the entire description of sOPTICS is only presented in the supplementary material.**\n\nWe could not detail sOPTICS in the main paper given 9 page limits.\nSimilar to OPTICS, sOPTICS is a visual tool to guide the setting of ε.\nOPTICS requires many new concepts, including core distance, reachability distance, and its algorithm requires significant room to present (see Section A1).\nWe decided to move sOPTICS to Appendix as its algorithm description is rather simple given OPTICS's description.\nWhile sOPTICS is also one of our contributions, we have to focus on sDBSCAN on the main paper due to the limited space.\n\n**W5. It is not clear whether the preprocessing time is included in the reported execution time. If not, I believe that the\nproposed algorithm is too much favored in the evaluation.**\n\nThe reported execution time **includes** the preprocessing time.\nTab 4 in Appendix shows the running time of preprocessing, finding core points, and clustering. \nThe execution of preprocessing (with sequential memory assess) is rather small, just around 10%, and is dominated by the distance computations (with random memory assess) for finding core points (See **Time complexity** in Section 3.4)\n\n**W6. The clustering accuracy is often lower than those of the conventional algorithms at the cost of fast execution. To\nachieve a good accuracy, more hyperparameters need to be tuned carefully.**\n\nIt is not totally correct.\n\nTab 5: Compared to k-means++, sDBSCAN is faster and gives 10% NMI higher on L1.\nFig 3, 16: Compared to kernel k-means, sDBSCAN gives similar NMI (only 1-2% off) but runs on a single machine.\nNote that we use k as the ground-truth number of clusters.\n\nsDBSCAN requires extra parameters, including number of random vectors D, top-k closest/furthest random vectors, top-m points closest/furthest to random vectors. For L1, L2, χ², JS distances, sDBSCAN need the number of embeddings d', and the scale σ.\nSection B6-B8 shows the sensitivity of these parameters.\nWe also explained the details in the rebuttal message to Reviewer #KGU7\n\nWe do not tune these parameters carefully, except ε visually guided by sOPTICS.\nThe same setting D = 1024, m = minPts, σ = 2ε, d' = D, k = {5, 10} works well on all experiments (see **Parameter settings** in Section 4 and Tab 2 for data set property).\nWithout ground truth, we have to run k-means with several k and DBSCAN variants with several ε on a large range (e.g. on L1, L2).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oE8x6HfLcH", "reviewer": "Reviewer_KGU7", "summary": "The authors presented a significant advancement in density-based clustering algorithms with the introduction of sDBSCAN. The scalability and speed improvements are particularly noteworthy, making it suitable for large datasets where traditional DBSCAN variants struggle. The theoretical underpinning provided confidence in the algorithm’s ability to maintain the clustering structure, while the empirical results demonstrate practical benefits. However, the paper would benefit from a deeper exploration of the algorithm's parameter sensitivity and a more detailed analysis of memory usage. The implementation complexity due to random projections and kernel features might pose challenges for practitioners. Additionally, a broader comparative analysis and more detailed examination of the algorithm’s performance across different distance metrics would strengthen the paper’s contributions.", "questions": "1. How sensitive is sDBSCAN to the choice of parameters such as the number of random vectors and the radius for core points? Are there guidelines for setting these parameters?\n2. How does sDBSCAN perform when extended to L2, L1, χ², and Jensen-Shannon distances in terms of both accuracy and speed?\n3. How robust is sDBSCAN to variations in data distribution and the presence of noise and outliers?\n4. Are there specific real-world applications or case studies where sDBSCAN has shown significant advantages over other clustering methods?", "limitations": "N/A", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. sDBSCAN significantly improves the scalability of density-based clustering algorithms, enabling the handling of million-point datasets efficiently.\n2. By utilizing cosine distance and random projections, sDBSCAN effectively handles high-dimensional data.\n3. The extension of sDBSCAN to other distance metrics (L2, L1, χ², and Jensen-Shannon) via random kernel features enhances its applicability across different types of data.", "weaknesses": "1. The algorithm’s performance may depend on the selection of parameters, and the sensitivity to these parameters is not deeply explored.\n2. The use of random projections and kernel features might complicate the implementation and understanding of the algorithm for practitioners.\n3. While the algorithm is extended to other distance metrics, the performance and effectiveness of these extensions are not thoroughly evaluated.\n4. The paper could benefit from a more comprehensive comparative analysis with a broader range of clustering algorithms beyond DBSCAN variants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. However, we found that the raised weaknesses and questions have been addressed in the paper and Appendix (Section B).\nWe explain in detail below.\n\n**W1) The algorithm’s performance may depend on the selection of parameters, and the sensitivity to these parameters is not deeply explored.\nQ1) How sensitive is sDBSCAN to the choice of parameters such as the number of random vectors and the radius for core points? Are there guidelines for setting these parameters?**\n\nOne of our contributions is sOPTICS, a visual tool to guide the setting of ε, radius for core points, given minPts.\n\nFor ε, we use sOPTICS graphs to select the relevant range, then find 6 values on such range to run sDBSCAN.\nFig 1 shows the sOPTICS graphs for L1, L2, Cosine, JS, and sDBSCAN's accuracy on 6 values of ε from a certain range that separates the valleys on sOPTICS graphs.\nE.g. on Cosine (Fig 1c and 1g), we select ε = {0.1, 0.11, 0.12, 0.13, 0.14, 0.15}.\nWe detail it in Section 4.1, especially in the 2nd and 3rd paragraphs.\nIn Section 4.2 (Pamap2 and Mnist8m), we state \"We use sOPTICS graph (see the supplement) to select relevant ranges of ε\". \nThese graphs are Fig 5 and 6 in Appendix.\nThis is how we select ε for Fig 2-3.\n\nFor minPts, Fig 1-3 use minPts = 50.\nIn Section B.8, Fig 13, 15 show sOPTICS graphs with minPts = 100. \nAgain, we set ε based on the suggested range from sOPTICS graphs to get sDBSCAN's accuracy in Fig 14, 16.\n\n\nsDBSCAN requires extra parameters, including number of random vectors D, top-k closest/furthest random vectors, top-m points closest/furthest to random vectors.\nFor L1, L2, χ², JS distances, sDBSCAN need the number of embeddings d', and the scale σ.\nWe have stated on Page 8 (Parameter settings) that \"Experiments on the sensitivity of parameters m, k, σ, d', minPts of sDBSCAN and sOPTICS are left in the supplement.\"\n\n- For D, we need D = power of 2 to use FHT (see Section 3.3 - Reduce random projection cost).\nOn Mnist, Mnist8m d = 784, we set D = 1024.\nD = 512 works well on Pamap2 with d = 51.\nFor consistency, we use D = 1024 throughout the paper.\n\n- For sensititvity of m, k, Section B.2 shows how to select sDBSCAN's parameter setting and its running time.\nSection B.7 shows the sensitivity of m, k on L1 on Pamap2 (in Fig 12).\n\n- For sensitivity of σ for L1, L2, see Section B.6. \nFig 7 for sDBSCAN and Fig 8-9 for sOPTICS with L1, L2 on Pamap2.\n\n- For sensititvity of d', see Fig 10-11 for sDBSCAN and sOPTICS on χ², JS on Mnist.\n\nWe do not tune these parameters carefully, except ε guided by sOPTICS. The same setting D = 1024, m = minPts, σ = 2ε, d' = D, k = {5, 10} works well on all experiments (see Parameter settings in Section 4 and Tab 2 for data set property).\n\n**W2) The use of random projections and kernel features might complicate the implementation and understanding of the algorithm for practitioners.**\n\nThe random projections and kernel features are building blocks of many practical machine learning algorithms.\nScikit-learn has featured many randomized kernel features, and we use two of them [19, 20].\n[19] won The Test-of-Time Award while [20] is popular in computer vision.\nSection A.3 shows how to guarantee distance preservation given d' = O(log(n) kernel features.\n\nThe random projection is the algorithmic primitive for many machine learning problems, including clustering [a, b]\n\n[a] NIPS 10 - Random Projections for k-means Clustering\n\n[b] ICML 03 - Random Projection for High Dimensional Data Clustering: A Cluster Ensemble Approach\n\n**W3) While the algorithm is extended to other distance metrics, the performance and effectiveness of these extensions are not thoroughly evaluated.\nQ2) How does sDBSCAN perform when extended to L2, L1, χ², and JS distances in terms of both accuracy and speed?**\n\nThe accuracy of sDBSCAN on L2, L1, χ², JS were shown in **all** figures in the paper and Appendix. \nThe speed is shown in the caption.\nTab 5-7 for Cosine, L1 on Pamap2, and for Cosine, L2, χ², JS on Mnist8m.\nFig 7-16 for parameters sensitivity on L1, L2, χ², JS.\n\n**Q3) How robust is sDBSCAN to variations in data distribution and the presence of noise and outliers?**\n\nSimilar to DBSCAN, sDBSCAN labels all outliers as the noise class.\nThe comparison between sDBSCAN and exact DBSCAN on Mnist and Pamap2 (Fig 1-2, Tab 5), showing the robustness of sDBSCAN with presence of noise.\nTab 3 in Section B.2 shows sDBSCAN can recover nearly the DBSCAN's output with 95% NMI.\n\nFor various data distributions, our experiment data has various # clusters (Tab 2), and hence the data set's distribution varies significantly.\nAlso, the valleys of sOPTICS graphs have very different shapes.\n\nThe sDBSCAN-1NN (Section 3.3) partially addresses the variations in data distribution.\nIf minPts is set correctly, we can identify many core points in the high-density regions and a few core points in low-density regions.\nSince sDBSCAN-1NN uses the nearest found core points to assign cluster labels, it can link points in the low-density regions together, and points in high-density regions together.\nFig 3, 16: sDBSCAN-1NN shows higher accuracy compared to sDBSCAN.\n\n**W4) The paper could benefit from a more comprehensive comparative analysis with a broader range of clustering algorithms beyond DBSCAN variants.\nQ4) Are there specific real-world applications or case studies where sDBSCAN has shown significant advantages over other clustering methods?**\n\nTab 5: Compared to k-means++, sDBSCAN is faster and 10% NMI higher on L1.\nFig 3, 16: compared to kernel k-means, sDBSCAN gives similar NMI and runs on a single machine. \nIn Section B - Clustering competitors: We state \"We tried several clustering algorithms on scikit-learn, including spectral clustering, kernel k-means. They could not work on million-point data sets given our DRAM of 128GB.\"\n\nsDBSCAN is non-parametric but still competitive with k-means variants that need the value of k (unknown in practice) regarding both accuracy and running time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**1) Selecting $\epsilon$ for sDBSCAN by sOPTICS without ground truth**

We would like to use global rebuttal to explain further sOPTICS  (details in Section A1), one of our contributions, to select the parameter $\epsilon$ of sDBSCAN.
Without sOPTICS, selecting a good value for $\epsilon$ will be as inefficient as running DBSCAN exactly.

On OPTICS graphs, the x-axis is the point ID and the y-axis presents its corresponding reachability distance ($reachDist$). The points are ordered based on the cluster structure, e.g. if $x$ and $y$ are close, and tend to be in the same cluster, then $x$ and $y$ will be ordered nearby on x-axis.

OPTICS assigns a distance called $reachDist$ for each point.
The $reachDist$ of core points are their $minPts$-NN distances. 
Core points in high-density regions will have smaller $reachDist$ while core points in low-density regions will have larger $reachDist$.
The $reachDist$ of a non-core point $q$ tends to be $dist(q, x)$ where $x$ is the closest core point to $q$.

In brief, OPTICS starts the process from a random point, and looks up the core points nearby the processed points so far.
Core points with the smallest $reachDist$ (stored in a priority queue) tends to be processed first, and output to a clustering order.
Hence, the points tend to be grouped with its neighborhood.
A sharp decrease of $reachDist$ indicates that we are processing points in the denser regions, and a slightly increase of $reachDist$ indicates that we are processing points in sparser regions.
This creates the valley, which is used as the cluster identification.

Similar to OPTICS, the number of valleys in the sOPTICS dendrograms reflect the number of clusters, and points downwards the valley floor are on denser regions while points upwards the valley head are on sparser regions.
By selecting $\epsilon$ to separate these valleys, sDBSCAN will achieve the peak of accuracy.

sOPTICS also needs ($\epsilon'$, minPts) to run and such $\epsilon'$ is usually larger than $\epsilon$ of sDBSCAN.
This ensures $reachDist$ of a point is its minPts-NN distance, which reflects its local density.
This links to the assumption of $t$ used in Theorem 1.
A wrong choice of $\epsilon$ for sDBSCAN will break the cluster into many smaller clusters (due to small $t$ at some place of the cluster).
We should increase $\epsilon$ to ensure $t$ large enough. 
The $\epsilon$ nearby the valley head tends to give the peak of clustering accuracy (see Fig 1c-d for sOPTICS and Fig 1g-h for sDBSCAN's accuracy) since it strengthens the clustering structure on dense regions (i.e. most of points in $B(x, \epsilon)$ are core points). 

sngDBSCAN [15] uses a somewhat stronger variant of the assumption of $t$ to ensure the recovery of DBSCAN's output.
However, none of DBSCAN variants offers an efficient tool to select a relevant value of $\epsilon$.

**2) Limitations in theory**

Our theoretical guarantees on recovering DBSCAN's output need $D \rightarrow \infty$ where $D$ is the number of random vectors, which is our limitation.
However, sDBSCAN works well in practice with $D = 1024$ even for Mnist8m ($n$ = 8.1M, $d$ = 784).
This might be due to the small world phenomenon "Neighbors of neighbors tend to be neighbors".

We use random vectors $r_i$ as pivot points and consider the top-$m$ points closest to $r_i$ as $r_i$'s neighbors.
If $x$ and $y$ are closest to the same random vectors $r_i$, they tend to be close to points in $r_i$'s neighbors.
That will increase the clustering connection when core points $x$ and $y$ share the same neighbors.

**3) Practicality**

For practical setting $D = 1024$, $m = minPts$ and constant $k$, sDBSCAN and sOPTICS (support various metric distances) use small memory overheads (i.e. $O(n * minPts)$) to store $n$'s neighborhods and their main computation cost is distance computations (i.e. $O(dn * minPts)$).

sDBSCAN with recommended parameter provided by sOPTICS is favoured compared to other clustering algorithms, including k-means variant, kernel k-means, sampling-based DBSCAN on million-point high-dimensional data sets, demonstrated by our empirical results in the paper and appendix.

**Response.pdf**

We add a figure to measure the index construction time of approximate nearest neighbor search on SOTA industry libraries, including Faiss, Scann, Hnsw. 

We add AMI and NMI measures for the clustering accuracy.

Meta-review: The paper introduces sDBSCAN, a scalable density-based clustering algorithm in high dimensions with cosine distance. During the review period the following strength and weaknesses have been highlighted.

Strengths:
- the papers improves the scalability of an important algorithm
- the algorithm comes with theoretical backing, and is good empirically
- The methods are non-trivial and interesting

Weaknesses:

- There are a few parts in the paper that are dense and hard to understand
- Limited novelty, the core idea of approximating-neighborhood is borrowed from the previous work [22]

Overall, the paper is interesting and it may be good to accept as a poster.

The committee strongly suggest the authors to implement the discussed improvements regarding the formulation of the theoretical results
Decision: Accept (poster)