Scalable DBSCAN with Random Projections

Authors: haochuan  xu
ninh  pham
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 12:40:00

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.

Main paper: 
 introduction: 
 DBSCAN [1] is one of the most fundamental clustering algorithms with many applications in data mining and machine learning [2] . It has been featured in several data analysis tool kits, including scikit-learn in Python, ELKI in Java, and CRAN in R. In principle, DBSCAN connects neighboring points from nearby high-density areas to form a cluster where the high density is decided by a sufficiently large number of points in the neighborhood. DBSCAN is parameterized by (ε, minP ts) where ε is the distance threshold to govern the point's neighborhood and to connect nearby areas; and minP ts is the density threshold to identify high-density areas.Apart from other popular clustering algorithms, including k-means variants [3, 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 a distance measure, DBSCAN has two primary steps, including (1) finding the ε-neighborhood (i.e. points within a radius ε) for every point to discover the density areas surrounding the point and (2) forming the cluster by connecting neighboring points. The first step is the main bottleneck as finding ε-neighborhoods for all points requires a worst-case O(n 2 ) time for a data set of n points in high-dimensions [6, 7] . This limits the applications of DBSCAN on modern million-point data sets.Another hurdle of (ε, minP ts)-DBSCAN is the choice of ε, which highly depends on the data distribution and distance measure. While minP ts is 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 ε-neighborhood for each point given a large value of ε, and use them to explore the quality of clustering structures over smaller values of ε. Using large ε causes O(n 2 ) memory bottleneck as the ε-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 highdimensional space, researchers study efficient solutions to scale up the process of identifying the neighborhood for each point in exact and approximate manners.Exact DBSCAN approaches [8, 9, 10] partition the data set into several subsets and iteratively extract and refine clusters from these subsets by performing additional ε-neighborhood queries on a small set of important points. Other grid-based methods on L2 [6, 11] efficiently identify neighborhood areas by confining the neighbor search exclusively to neighboring grids. However, these approaches still have worst-case quadratic time or their complexity grows exponentially to the dimension. Random projections [12, 13] have been used to build grid-based or tree-based indexes for faster approximate ε-neighborhoods on L2, though they do not offer theoretical guarantees on the clustering accuracy.Instead of finding the ε-neighborhood for every point, DBSCAN++ [14] finds ε-neighborhoods for a subset of random points chosen through uniform sampling or k-centering methods. sngDBSCAN [15] approximates the ε-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 ε) for sampling-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 ε by linearly ordering the data points such that close points become neighbors in the ordering. Besides the cluster ordering, OPTICS also computes a reachability distance for each point. The dendrogram provided by OPTICS visualizes the density-based clustering results corresponding to a broad range of ε, which indicates a relevant range of ε for DBSCAN.Like DBSCAN, OPTICS requires the ε-neighborhood for every point, leading to an O(n 2 ) time complexity. In practice, OPTICS often needs a large ε to discover clustering structures on a wide range of ε. Such large ε demands O(n 2 ) memory as the ε-neighborhood of one point needs O(n) space. Such memory constraint is infeasible for million-point data sets.Contribution. Inspired by sampling approaches, we observe that the exact ε-neighborhood for every point is unnecessary to form and visualize the density-based clustering results. Our approach, named sDBSCAN, first builds a lightweight random projection-based index with a sufficiently large number of projection vectors. Utilizing the asymptotic property of the extreme order statistics associated with some specific random vectors [18] , sDBSCAN can select high-quality candidates to identify ε-neighborhoods with theoretical guarantees. sDBSCAN provably outputs DBSCAN'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, 15] . Empirically, sDBSCAN runs significantly faster than several competitive DBSCAN variants while achieving similar DBSCAN clustering accuracy on million-point data sets.To further facilitate sDBSCAN, we propose sOPTICS, a scalable OPTICS derived from the random projection-based indexing, to guide the parameter setting. We also extend sDBSCAN and sOPTICS to other popular distance measures, including L2, L1, χ 2 , and Jensen-Shannon (JS), that allow random kernel features [19, 20] .Scalability. Both sDBSCAN and sOPTICS are scalable and multi-thread friendly. Multi-threading sDBSCAN and sOPTICS take a few minutes to cluster and visualize clustering structures for millionpoint data sets while the scikit-learn counterparts cannot run on our hardware. On Mnist8m with 8.1 million points, sDBSCAN gives 38% accuracy (measuring by the normalized mutual information NMI), running in 15 minutes on a single machine of 2.2GHz 32-core (64 threads) AMD processor with 128GB of DRAM. In contrast, kernel k-means [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. 
preliminary: 
 We briefly describe DBSCAN [1] , OPTICS [17] , and the connection with approximate near 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.DBSCAN is a density-based approach that links nearby dense areas to form the cluster. For a distance measure dist(•, •), DBSCAN has two parameters ε and minP ts. Given the data set X, for each point q ∈ X, DBSCAN executes a range reporting query B ε (q) that finds all points x ∈ X within the ε-neighborhood of q, i.e. B ε (q) = {x ∈ X | dist(x, q) ≤ ε}. Based on the size of the range query result, DBSCAN determines q as core if |B ε (q)| ≥ minP ts; otherwise, non-core points. We will call the ε-neighborhood B ε (q) as the neighborhood of q for short.DBSCAN forms clusters by connecting core points and their neighborhoods where two core points q 1 and q 2 are connected if q 1 ∈ B ε (q 2 ). A non-core point belonging to a core point's neighborhood will be considered 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 a 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. 1.1: Inputs: X, ε, minP ts, the setC = {(q, B ε (q)) | q is core} 2: G ← initialize empty graph 3: for each q ∈ 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 to non-core points x ∈ B ε (q) if x is not connected 6: return connected components of GOPTICS [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 ∈ X, OPTICS computes a reachability distance from its closest core point. The cluster ordering and reachability distance of each point are used to construct a reachability-plot dendrogram that visualizes the densitybased clustering results corresponding to a broad range of ε. Valleys in the reachability-plot are considered as clustering indicators. The OPTICS's algorithm is detailed in the appendix.Given a pair (ε, minP ts), OPTICS first identifies the core points, the neighborhoods of core points, and then computes the core distance of every point, defined as below.coreDist(q) = ∞ if q is non-core, minP ts -NN distance otherwise.Then, OPTICS iterates X, and for each x ∈ 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) = ∞ if q is non-core, max(coreDist(q), dist(x, q)) otherwise.For a core point q, reachDist(x, q) is dist(x, q) if x is not belonging to minP ts-NN of q. Among several core points whose neighborhood contains x, OPTICS tends to 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. A sharp decrease of x.reach of the point x in the group indicates that we are processing points in denser regions, and a slight increase indicates that we are processing points in sparser regions. This creates valleys on 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.Time and space complexity. Similar to DBSCAN, the running time of OPTICS is O(n 2 ) makes it impractical on large-scale data sets. Fast implementations of OPTICS with large values of ε might require O(n 2 ) memory to store the matrix distance between the core points and their neighborhood points. Such implementations are infeasible for large n.Since the primary bottleneck of DBSCAN is to find core points and their neighborhoods by executing n range queries, reducing the computational cost of this step will significantly improve the performance. Scaling up DBSCAN poses the need for lightweight indexing data structures, ideally with linear construction time, to approximately answer n range queries. Heavyweight graphbased indexes [24, 25] with O(n 2 ) construction time and locality-sensitive 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 vectorsr i ∈ R d , i ∈ [D],whose coordinates are randomly selected from the standard normal distribution N (0, 1), and the sign function sgn(•). CEOs randomly projects x 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 ri |q ⊤ r i |. Given a sufficiently large D, the projection values on the closest or furthest random vector to q approximately preserve x ⊤ q. The proof is described in the appendix. Lemma 1. [22] For two points x, q ∈ S d-1 and significantly large D random vectors r i , w.l.o.g. we let r * = arg max ri |q ⊤ r i |. Then, we havex ⊤ r * D -→ N sgn(q ⊤ r * ) • x ⊤ q 2 ln (D) , 1 -(x ⊤ q) 2 .(As a geometric intuition, for significantly large D random vectors, if 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 a constant k > 0, Lemma 1 also holds for the top-k closest/furthest vectors to q due to the asymptotic property of extreme normal order statistics [18, 22] . 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.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The theoretical result of sDBSCAN uses the asymptotic property of extreme order statistics that require D → ∞, and an assumption on the strong connection of densitybased 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:• 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 a separate "Limitations" 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 on 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 χ 2 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.For each point q ∈ X ⊂ S d-1 , we compute D random projection values q ⊤ r i where i ∈ [D]. W.l.o.g., we let r * = arg max ri |q ⊤ r i | = arg max ri q ⊤ r i . Lemma 1 indicates that, given a sufficiently large D, points closest to r * tend to have smaller distances to q, and hence are important to discover q's neighborhood. Hence, computing the distance between q to the top-m points closest to r * where m = O(minP ts) suffices to ensure whether or not q is a core point.Algorithm 2 shows how we preprocess the data set. For each point q ∈ X, we keep top-k closest and furthest random vectors. For each random vector r i , we keep top-m closest and furthest points. Algorithm 3 identifies a core point q and its approximate neighborhood by computing the distance between q and 2km points associated to the k closest and k furthest random vectors to q. sDBSCAN and sOPTICS are essential DBSCAN and OPTICS using the outputs of Algorithm 3 as inputs.Scalability. Given m = O(minP ts), sDBSCAN and sOPTICS need O(k • minP ts) distance computations, compared to O(n) of the exact solution, to identify a core point q and its neighborhood Algorithm 2 Preprocessing 1: Inputs: X ⊂ S d-1 , D random vectors r i , k, m = O(minP ts) 2: for each q ∈ X, compute and store top-k closest and top-k furthest vectors r i to q.3: for each random vector r i , compute and store top-m closest and top-m furthest points to r i .Algorithm 3 Finding core points and their approximate neighborhoods 1: Inputs: X ⊂ S d-1 , D random vectors r i , k, ε, m = O(minP ts) 2: Initialize an empty set B ε (q) for each q ∈ X 3: for each q ∈ X do 4:for each r i from top-k closest (or furthest) random vectors of q do 5:for each x from top-m closest (or furthest) points of r i do 6:if dist(x, q) ≤ ε then 7:Insert x into B ε (q) and insert q into B ε (x) 8: for each q ∈ X do9: if | B ε (q)| ≥ minP ts then 10:Output q as a core point and B ε (q) as an approximate B ε (q) for DBSCAN (Alg. 1) 11:Output dist(x, q) for each x ∈ B ε (q) for OPTICS (Alg. 6) Algorithm 4 sDBSCAN 1: Inputs: X ⊂ S d-1 , D random vectors r i , ε, minP ts 2: Call Algorithm 2 for preprocessing with m = O(minP ts) 3: Call Algorithm 3 to find the set C = {(q, B ε (q)) | q is identified as core} 4: Call DBSCAN given the output C from Algorithm 3 Algorithm 5 sOPTICS 1: Inputs: X ⊂ S d-1 , D random vectors r i , ε, minP ts 2: Call Algorithm 2 for preprocessing with m = O(minP ts) 3: Call Algorithm 3 to find the set C = {(q, B ε (q), {dist(x, q) for each x ∈ B ε (q)}) | q is identified as core} 4: Use the minP ts-NN distance between q and x ∈ B ε (q) as coreDist(q) for each identified core point q 5: Call OPTICS (Alg. 6) given the output C from Algorithm 3 subset B ε (q) ⊆ B ε (q). The memory usage to store B ε (q) is also bounded by O(k • minP ts). 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 neighborhood. Fortunately, Algorithm 2 and 3 are fast and parallel-friendly. We only need to add #pragma omp parallel directive on the for loops to run in multi-threads. This enables sDBSCAN and sOPTICS to deal with million-point data sets in minutes while the scikit-learn counterparts take hours or cannot finish due to the memory constraints.In practice, setting m = O(minP ts) suffices to identify core points and approximate their neighborhoods to ensure the quality of sDBSCAN. However, to theoretically guarantee the quality of sDBSCAN, we need to adjust m based on the data distribution since ensuring the density-based clustering quality without any information about the data distribution is hard [14, 15] .As in the unit sphere, if L 2 (x, q) ≤ ε then x ⊤ q ≥ 1 -ε 2 /2, we make a change in our algorithm. For each random vector r i , we maintain two setsS i = {x ∈ X | x ⊤ r i ≥ (1 -ε 2 /2) 2 ln (D)} and R i = {x ∈ X | x ⊤ r i ≤ -(1 -ε 2 /2) 2 ln (D)},instead of keeping only top-m closest/furthest points. In other words, for each random vector r i , the value of m is set adaptively to the data distributed around r i . For a point q and its closest random vector r * , if we compute L 2 (x, q) for all x ∈ S * where S * = {x ∈ X | x ⊤ r * ≥ (1 -ε 2 /2) 2 ln (D)}, then any x ∈ B ε (q) is found with a probability at least 1/2 due to the Gaussian distribution in Eq. (1) . By computing the distance between q and all points in S i or R i corresponding to the top-k closest/furthest random vectors r i of q, we can boost this probability to s = 1 -(1/2) 2k due to the asymptotic independence among these 2k vectors [18, 22] .By connecting core points and their associated border points, DBSCAN outputs an ε-neighborhood graph with l disconnected components G 1 , G 2 , . . . , G l corresponding to l density-based clusters C 1 , C 2 , . . . , C l . Hence, by maintaining S i and R i for each vector r i , sDBSCAN forms a subgraph G ′ i ⊆ G i , i = 1, . . . , l, by sampling each edge of G i with probability at least s. We now use the following lemma [27] to guarantee the connectivity of subgraphs G ′ i provided by sDBSCAN. Lemma 2. Let G be a graph of n vertices with min-cut t and 0 < δ < 1. There exists a universal constant c such that if s ≥ c(log (1/δ)+log (n)) t , then with probability at least 1 -δ, the graph G ′ derived by sampling each edge of G with probability s is connected.Since DBSCAN connects core points, there exists a constant t > 0 such that, for any pair of nearby core points q 1 , q 2 , if L 2 (q 1 , q 2 ) ≤ ε, then B ε (q 1 ) and B ε (q 2 ) share at least t common core points. We assume that t will not be small to ensure that the density-based clusters will not become arbitrarily thin anywhere. Given that DBSCAN produces l disconnected graphs G 1 , G 2 , . . . , G l , it is clear that t will be the lower bound of the min-cut of any G i . By applying Lemma 2 on each G i , we state our main result.Theorem 1. Let G 1 , G 2 , . . . , G l be connected subgraphs produced by DBSCAN where each G i corresponds to a cluster C i with n i core points. Assume that any pair of nearby core points q 1 , q 2 , if L 2 (q 1 , q 2 ) ≤ ε, then B ε (q 1 ) and B ε (q 2 ) share at least t common core points. There exists aconstant c such that if t 1 -(1/2) 2k ≥ c (log (1/δ) + log (n i )) for i ∈ [l], sDBSCAN will recover G 1 , G 2 , .. . , G l as clusters with probability at least 1 -δ.Theorem 1 indicates that when the cluster C i of n i core points is not thin anywhere, i.e. the common neighborhood of any two nearby core points has at least t = O(log (n i )) core points, sDBSCAN can recover C i with probability 1 -1/n i . While our statistical guarantee is inspired by [15] , we 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 (i.e. S i , R i ) 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 i , R i for each random vector r i , we can keep the top-m points of these sets where m = O(minP ts). This practical setting substantially reduces the memory usage and running time of sDBSCAN without degrading clustering results. The next subsection justifies it.We observe that for any core point q regarding (ε, minP ts), |B ε (q)| is often substantially larger than minP ts. We will present heuristics to improve the performance of sDBSCAN.Identify core points with m = O(minP ts). Given a core point q, we denote by x ∈ B ε (q) and y ∈ X \ B ε (q) any close and far away points to q regarding the distance threshold ε. W.l.o.g., we assume that r * = arg max ri q ⊤ r i , and let X = x ⊤ r * , Y = y ⊤ r * be the projection values of x, y on r * , respectively. From Eq. ( 1), X -Y follows a Gaussian distribution whose variance is bounded by1 -(x ⊤ q) 2 + 1 -(y ⊤ q) 2 2 . Let α xy = x ⊤ q -y ⊤ q / 1 -(x ⊤ q) 2 + 1 -(y ⊤ q)2 and α * = arg min x∈Bε(q),y∈X\Bε(q) α xy . As Lemma 1 holds for k closest/furthest random vectors, assume that the event any point x ∈ B ε (q) is ranked higher than all y ∈ X \ B ε (q) is independent, Lemma 3 justifies that m = minP ts suffices to identify q as a 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 = n 1/kα 2 * for a given core point q ∈ X ⊂ S d-1 where |B ε (q)| ≥ minP ts, maintaining top-minP ts points associated to k closest/furthest vectors to q ensures | B ε (q)| ≥ minP ts, B ε (q) ⊆ B ε (q) with probability at least (1 -1/n) minP ts ∼ e -minP ts/n . Lemma 3 holds given the dependence of D on the data distribution around q (i.e. α * ). We empirically observe that the distance gap between q and points inside and outside B ε (q) is significant, making α 2 * large. Hence, setting D = 1, 024, k = {5, 10} suffices to identify core points and enrich their neighborhoods, achieving high clustering quality on many real-world data sets.sDBSCAN-1NN 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 ∈ C. We will build a nearest neighbor classifier (1NN) 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 1NN heuristic as sDBSCAN-1NN.In particular, for each sampled core point q ∈ C, we recompute their random projection values with the stored D random vector r i as we do not keep these values after preprocessing. For each noisy point x ∈ 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| ≈ 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 multiprobes [29] that cause significant space or time overheads. Also, it seems non-trivial for 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, L1, χ 2 , and Jensen-Shannon (JS) via popular randomized kernel features [19, 20] . In particular, we study fast randomized feature mapping f :R d → R d ′ such that E f (x) ⊤ f (q) = K(x, q)where K are Gaussian, Laplacian, χ 2 , and JS kernels. As we execute random projections on the constructed random features for each point and compute dist(x, y) using the original data, we only need a 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 D 1 , D 2 , D 3 whose values are randomly chosen in {+1, -1}. The random projection of x is simulated by the mapping x → HD 3 HD 2 HD 1 x where H is the Hadamard matrix. With FHT, the random projection can be simulated in O (D log (D)) time and use additional O(D) extra space to store random matrices.We analyze the time and space complexity of sDBSCAN with m = O(minP ts).With FHT, retrieving top-k closest/furthest vectors for each q ∈ X, and top-m closest/furthest points for each random vector r i in the preprocessing (Alg. 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- Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 i and R i whose sizes depend on the neighborhood around the random vector r i . For Lemma 3, we assume that the event any point x ∈ B ε (q) is ranked higher than all y ∈ X \ B ε (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 crossreferenced. • All assumptions should be clearly stated or referenced in the 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 to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiment: 
 We implement sDBSCAN and sOPTICS in C++ and compile with g++ -O3 -std=c++17 -fopenmp -march=native. We conducted experiments on Ubuntu 20.04.4 with an AMD Ryzen Threadripper 3970X 2.2GHz 32-core processor (64 threads) with 128GB of DRAM. We present empirical evaluations on the clustering quality compared to the ground truth (i.e. 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] as a representative grid-based approach, DBSCAN++ [14] and sngDBSCAN [15] . DBSCAN++ has two variants, including DBSCAN++ with uniform initialization (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 on other distance measures, we compare it with the result of kernel k-means in [21] . We found other clustering competitors could not work on million-point data sets given 128 GB of RAM, detailed in the appendix.We use the adjusted mutual information (AMI) [30] to measure the clustering quality. Results on other measures [31] , including normalized mutual information (NMI) and correlated coefficients (CC) are in the appendix. We conduct experiments on three popular data sets: Mnist While DBSCAN on L2 is popular, the capacity to use arbitrary distances is an advantage of DBSCAN compared to other clustering algorithms. We use sOPTICS to visualize the cluster structure on several distance measures, including L1, L2, cosine, and JS on Mnist with D = 1, 024, m = minP ts = 50, k = 5. By using the average top-100 nearest neighbor distances of 100 random points to find the setting of ε for sOPTICS, we set ε = 1, 800 for L2, ε = 18, 000 for L1, and ε = 0.25 for the others.The top subfigures of Figure 1 show reachability-plot dendrograms of sOPTICS on 4 studied distance measures. Since points belonging to a cluster have a small reachability distance to their nearest neighbors, the number of valleys in the dendrograms reflects the cluster structure. Therefore, we can predict that cosine and JS provide higher clustering quality than L2 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 L2 is impossible. Note that 64-thread sOPTICS runs in less than 3 seconds while 64-thread scikit-learn OPTICS demands 1.5 hours on L2. Indeed, sOPTICS can output similar OPTICS graphs within 30 seconds, as shown in the appendix.The bottom subfigures of Figure 1 show AMI scores of several DBSCAN variants over the recommended 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 a meaningful result on the studied range values of ε. L2 and L1 distances show inferior performance on 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 ε ∈ [0.1, 0.2] with cosine distance. On 1 thread, sDBSCAN runs nearly 2×, 8× and 10× faster than sngDBSCAN, uDBSCAN++ and kDBSCAN++, respectively. 64-thread sDBSCAN runs nearly 10× faster than 1-thread sDBSCAN and 100× faster than 64-thread scikit-learn. Though pDBSCAN shares the same AMI with scikit-learn, its running time makes it infeasible for high-dimensional data sets.This subsection compares the performance of sDBSCAN, DBSCAN++, and sngDBSCAN on millionpoint data sets. scikit-learn DBSCAN and pDBSCAN cannot finish after 4 hours. Our implemented sngDBSCAN runs faster than [15] and supports multi-threading. We use sOPTICS graphs in the appendix to select relevant ranges of ε. 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 L1, χ 2 , JS and multi-threading while the rest are in multi-threading.Pamap2. Figure 2 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 L1 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 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 p = 0.001 could not finish after 4 hours, we only report sngDBSCAN.As we cannot run scikit-learn 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 [21] running on a supercomputer with 32 nodes, each of which has two 2.3GHz 16-core (32 threads) Haskell processors and 128GB of DRAM. This configuration of a single node is similar to our conducted machine. Figure 3 shows the NMI scores of sDBSCAN-1NN with 1-NN heuristic described in Subsection 3.3, sDBSCAN, sgnDBSCAN, and kernel k-means on Mnist8m. sDBSCAN-1NN shows superiority among DBSCAN variants. Its peak is at least 10% and 5% higher than sngDBSCAN and sDBSCAN, respectively, on studied measures. sDBSCAN consistently gives higher accuracy than sngDBSCAN with the most significant gap of 5% on χ 2 and cosine. Note that sDBSCAN-1NN samples 0.01n core points, and uses CEOs to build the approximate 1NN classifier, the time overhead of this step is smaller than sDBSCAN's time. Indeed, sDBSCAN-1NN with minP ts = 100 reaches 40% NMI on χ 2 , running within 15 minutes. Details of the running time comparison are in the appendix.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We release the source code, parameter setting guidelines, and data set for reproducibility. 
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 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 on million-point data sets, and provide very competitive accuracy compared to other clustering algorithms. We hope sDBSCAN and sOPTICS will be featured on popular clustering libraries shortly.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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, confidence intervals, or statistical significance tests, at 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 run 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 96% CI, if the hypothesis of Normality of 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as well as estimate the total compute.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: 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 ∈ X, OPTICS computes a reachability distance from its closest core point. Each point's cluster ordering and reachability distance are used to construct a reachability-plot dendrogram that visualizes the densitybased clustering results corresponding to a broad range of ε. Hence, given the setting of large ε, valleys in the reachability plot are considered as the clustering indicators.In principle, given a pair (ε, minP ts), OPTICS first identifies the core points, their neighborhoods, and their core distances. Then, OPTICS iterates X, and for each x ∈ 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.coreDist(q) = ∞ if q is non-core, minP ts -NN distance otherwise. reachDist(x, q) = ∞ if q is non-core, max(coreDist(q), dist(x, q)) otherwise.For a core point q, reachDist(x, q) is dist(x, q) if x is not belonging to minP ts-NN of q. Among several core points whose neighborhood contains x, OPTICS seeks the smallest reachability distance x.reach for x from these core points. In other words, x.reach = min qi {reachDist(x, q i ) | q i is core and x ∈ B ε (q i )}.OPTICS can be implemented as a nested loop as shown in Algorithm 6. In the outer loop (Line 4), a random q ∈ X is selected and inserted into an empty cluster ordering O. If q is core, each point x ∈ B ε (q) is inserted into a priority queue Q with reachDist(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 ′ ∈ 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 6 is slightly different from the original version [17] . Since we do not know how to implement decrease-key operation efficiently on the priority queue 1 , 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 x 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 of ε.Time and space complexity. Similar to DBSCAN, the running time of OPTICS is O(n 2 ) makes it impractical on large-scale data sets. Fast implementations of OPTICS with large values of ε will require O(n 2 ) memory to store the matrix distance between the core points and its neighborhood points. Such implementations are infeasible for large n.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 ∈ B ε (q)} (Line 16 of Alg. 3). Using this set, we can estimate coreDist(q) as the minP ts-NN distance between q and B ε (q). Though such estimation is an upper bound of coreDist(q), the tightness of the upper bound and the accurate neighborhood approximation make the reachability-plot provided by sOPTICS very similar to the Given two vectors q, x ∈ S d-1 and any random Gaussian vector r i ∈ R d , we let Q i = q ⊤ r i and X i = x ⊤ r i . It is well known that Q i ∼ N (0, 1), X i ∼ N (0, 1), and Q i and X i are normal bivariates from N (0, 0, 1, 1, ρ) where ρ = x ⊤ q. Let (Q 1 , X 1 ), (Q 2 , X 2 ), . . . , (Q D , X D ) be D random samples from N (0, 0, 1, 1, ρ) generated by D Gaussian vectors r i , 1 ≤ i ≤ D. We form the concomitants of normal order statistics by descendingly sorting these pairs based on Q-value.Let r * = arg max ri q ⊤ r i . Let X [1] be the concomitant of the first (maximum) order statistic Q (1) . Then we have Q (1) = q ⊤ r * , X [1] = x ⊤ r * . The theory of concomitants of extreme order statistics [18, 32] studies the asymptotic behavior of the concomitants X [1] given the asymptotic behavior of Q (1) when D goes to infinity.The seminal work of David and Galambos [18] establishes the following properties of concomitants of normal order statistics.E Q (1) D -→ 2 ln (D) , Var Q (1) D -→ 0 , E X [1] = (x ⊤ q) E Q (1) D -→ x ⊤ q 2 ln (D) , Var X [1] = 1 -(x ⊤ q) 2 + (x ⊤ q) 2 Var Q (1) D -→ 1 -(x ⊤ q) 2 , X [1] D -→ N E X [1] , Var X [1] .Since Gaussian distribution is symmetric, we can use both X [1] and -X [D] corresponding to the maximum Q (1) associated to the closest random vector and minimum Q (D) associated to the furthest random vector to q for estimating x ⊤ q. This proves the claim of Lemma 1.Given D random vectors r i ∈ R d , i ∈ [D],whose coordinates are randomly selected from the standard normal distribution N (0, 1), and the sign function sgn(•), we randomly projects x and q onto these D Gaussian random vectors. For significantly large D random vectors r i , w.l.o.g. we assume that r 1 = arg max ri |q ⊤ r i |, we havex ⊤ r 1 ∼ N sgn(q ⊤ r 1 ) • x ⊤ q 2 ln (D) , 1 -(x ⊤ q) 2 .For a constant k > 0, this property (i.e. Lemma 1) also holds for the top-k closest/furthest vectors to q due to the asymptotic property of extreme normal order statistics [18, 22] .Given a core point q, we denote by x ∈ B ε (q) and y ∈ X \ B ε (q) any close and far away points to q regarding the distance threshold ε. W.l.o.g., we assume that r 1 = arg max ri |q ⊤ r i | = arg max ri q ⊤ r i . Let X = x ⊤ r 1 , Y = y ⊤ r 1 be random variable corresponding to the projection values of x, y on r 1 , respectively. Then we haveX ∼ N x ⊤ q 2 ln (D) , 1 -(x ⊤ q) 2 , Y ∼ N y ⊤ q 2 ln (D) , 1 -(y ⊤ q) 2 . Let α xy = x ⊤ q -y ⊤ q / 1 -(x ⊤ q) 2 + 1 -(y ⊤ q) 2 , applying Chernoff bound [33] on the Gaussian variable Y -X gives Pr [Y ≥ X] ≤ D -(x ⊤ q-y ⊤ q) 2 / √ 1-(x ⊤ q) 2 + √ 1-(y ⊤ q) 2 2 = D -α 2 xy .Let α * = arg min x∈Bε(q),y∈X\Bε(q) α xy and D = n 2/α 2 * , applying the union bound, we have Pr [x is ranked higher than all y ∈ X \ B ε (q) on r 1 ] ≥ 1 -1/n . Since Lemma 1 holds for k closest/furthest random vectors r i to q due to their asymptotic independence, let R q be the set of these vectors associated to q. By setting D = n 1/kα 2 * we have Pr [x is ranked higher than all y ∈ X \ B ε (q) on one vector in R q ] ≥ 1 -1/n . Assume that the event any point x ∈ B ε (q) is ranked higher than all y ∈ X \ B ε (q) is independent, we have Pr [At least minP ts points in B ε (q) appear on top-minP ts points associated to R q ] ≥ (1-1/n) minP ts . This proves the claim of Lemma 3.We show how to extend sDBSCAN and sOPTICS to other popular distance measures, including L2, L1, χ2 , and Jensen-Shannon (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 d → R d ′ such that E f (x) ⊤ f (q) = K(x, q) where K is the kernel function. We study Gaussian, Laplacian, χ 2 , and JS kernels as their randomized mappings are well-studied and efficiently computed. Also, the embeddings' extra costs are negligible compared to those of sDBSCAN and sOPTICS.Given x = {x 1 , . . . , x d }, y = {y 1 , . . . , y d } and σ > 0, the following are the definitions of the investigated kernels.K L (x, y) = e -∥x-y∥1/σ ; K G (x, y) = e -∥x-y∥ 2 2 /2σ 2 ; K χ 2 (x, y) = i 2x i y i x i + y i ; K JS (x, y) = i x i 2 log x i + y i x i + y i 2 log x i + y i y i .We present here the random Fourier embeddings [19] for K L and K G with σ = 1. We first generate d ′ random vectors w i , i ∈ [d ′ ] whose coordinates are from N (0, 1) for K G and Lap(0, 1) for K L .Our randomized mappings are:f (x) = 1 √ d ′ {sin (w ⊤ i x), cos (w ⊤ i x) | i ∈ [d ′ ]} ∈ S 2d ′ -1 . Since |f (x) ⊤ f (y)| ≤ ∥f (x)∥ 2 ∥f (y)∥ 2 = 1, the Hoeffding's inequality guarantees:Pr |f (x) ⊤ f (y) -K(x, y)| ≥ δ ≤ e -d ′ • δ 2 /2 . By selecting d ′ = O(log (n)), the randomized mapping f preserves well the kernel function of every pair of points. Hence, sDBSCAN and sOP-TICS on these randomized embeddings output similar results to DBSCAN and OPTICS on the corresponding distance measures.Complexity. For K G , K L , the embedding time is O(dd ′ ). For K χ 2 , K JS , the embedding time is O(d ′ ) for d ′ random features by applying the sampling and scaling approaches [20] . Empirically, the random feature construction time is negligible compared to the sDBSCAN and sOPTICS time.As we execute random projections on the constructed random features for each point and compute dist(x, y) using the original data, we only need a small extra space to store random vectors w i .We use the Eigen library 2 for SIMD vectorization on computing the distances. It will only give advantages on dense data sets, e.g., Pamap2. Our sDBSCAN and sOPTICS are multi-threading friendly. We only add #pragma omp parallel directive on the for loop when preprocessing and finding the neighborhood for each point.Clustering competitors. We tried several clustering algorithms on scikit-learn, 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 [13] cannot run even on the small Mnist data set.Our competitors include pDBSCAN [6] 3 as a representative grid-based approach, DBSCAN++ [14]4 and sngDBSCAN [15] 5 as representatives for sampling-based approaches. DBSCAN++ has two variants, including DBSCAN++ with uniform initialization (called uDBSCAN++) that uses KD-Trees to speed up the search of core points and k-center initialization (called kDBSCAN++). We also compare with multi-threading scikit-learn implementations of DBSCAN and OPTICS 6 . 2 . For Pamaps2, we discarded instances that contain NaN values and removed the dominated class 0 corresponding to the transient activities. We note that Mnist and Mnist8m are sparse data sets with at least 75% sparsity, while Pamap2 is dense.This subsection measures the performance of sOPTICS and scikit-learn OPTICS with multi-threads. We show that sOPTICS can output the same OPTICS's results in less than 30 seconds, which is up to 180× speedups over scikit-learn OPTICS.We use scikit-learn OPTICS to generate the dendrogram given minP ts = 50. To select a reasonable value of ε for OPTICS to reduce the running time, we randomly sample 100 points and use the average top-100 nearest neighbor distances of these sampled points as ε. Accordingly, we use ε = 1, 800 for L2 and ε = 18, 000 for L1.To recover OPTICS's results, sOPTICS uses D = 2, 048, k = 2 and m = 1, 000. For L2 and L1 distances, sOPTICS requires two additional parameters, including the scale σ and the number of embeddings d ′ , for random Fourier embeddings. We observe that the performance of sOPTICS is insensitive to σ and d ′ , hence we simply set σ = 2 * ε and d ′ = 1, 024 for our experiments.We run both scikit-learn OPTICS and sOPTICS with 64 threads. Regarding speed, sOPTICS needs less than 30 seconds, while OPTICS takes hours to finish. This shows the advantages of sOPTICS in accurately finding candidates to construct neighborhoods and efficiently utilizing multi-threading. Regarding accuracy, sOPTICS outputs nearly the same graphs as OPTICS, as shown in Figure 4 .Since there are more valleys on L2 than L1, the clustering accuracy regarding the ground truth using L2 will be higher than L1.We first normalize all data points. Since cosine distance is identical to L2 on a unit sphere, we use scikit-learn DBSCAN on L2 to compare with sDBSCAN on cosine distance. Given minP ts = 50, we set ε = 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 to a random vector and top-k closest/furthest random vectors to a point. These parameters govern the accuracy and efficiency of sDBSCAN. We set D = 1, 024 and vary m, k in the next experiments. 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. Table 3 shows the performance of multi-threading sDBSCAN on DBSCAN's outputs with ε = 0.11, minP ts = 50. We can see that sDBSCAN can recover DBSCAN's result with larger m. These findings justify our theoretical result as larger m increases the chance of examining all points in the set S i and R i corresponding to the random vector r i , increasing the chance to recover the DBSCAN's output.In the last column with m = 2, 000, sDBSCAN with k = 2 achieves NMI of 95% but runs 2 times slower than k = 1 since it nearly doubles the candidate size. sDBSCAN with all configurations runs at least 3× faster than scikit-learn DBSCAN. This presents the advantages of sDBSCAN in accurately finding candidates to find core points and efficiently utilizing the multi-threading architecture.sDBSCAN's parameter setting. Given m ≥ minP ts and k, each point needs at most 2km distance computations due to the duplicates on top-m candidates corresponding to 2k investigated random vectors. As a larger k leads to more duplicates among 2km candidates, given a fixed budget B = 2km, Table 3 shows that k = 1, m = B/2 has higher accuracy but significantly higher running time thank = k 0 > 1, m = B/2k 0 .While larger m and D tend to increase the accuracy of sDBSCAN, they affect space and time complexity. Since we often set D = 1, 024 to ensure Lemma 3 holds, and the memory resource is limited due to large data sets, we set m = minP ts = 50 and k = {5, 10} for most experiments.Compared to the ground truth, this setting does not affect the accuracy of sDBSCAN but uses significantly less computational resources than other configurations.Running time of sDBSCAN's components with multi-threading. Given ε = 0.11, m = minP ts = 50, k = 5, Table 4 shows the running time of sDBSCAN components on 1 and 64 threads. On 1 thread, we can see that finding neighborhoods is the primary computational bottleneck while forming clusters is negligible. This is due to the expensive random access operations to compute 2km distances for each point. As the main components of sDBSCAN, including preprocessing (Alg. 2) and finding neighborhoods (Alg. 3) can be sped up with multi-threading, we achieve nearly 10× speedup with 64 threads. We also observe that the construction time of the randomized embeddings to support L2, L1, χ 2 , and JS is similar to the preprocessing time and is negligible to that of finding neighborhoods.We use the average top-100 nearest neighbor distances of 100 sampled points to select a suitable ε for sOPTICS. (a) L1 As L2 is inferior to L1 and cosine on sampling-based DBSCAN, Table 5 reports the NMI scores and running time of studied algorithms on L1 and cosine distances over a larger range of ε. While sDBSCAN shows a low NMI on cosine, its accuracy is 45% on L1, which is higher than sngDBSCAN on both cosine and L1. As sngDBSCAN uses p = 0.01, each point will compute np ∼ 17, 700 distances compared to 2km = 1000 of sDBSCAN. Hence, sDBSCAN runs up to 14× faster than sngDBSCAN on L2. On L1, sDBSCAN is nearly 100× faster than DBSCAN. By changing k = 5, m = 200, sDBSCAN reaches 48% NMI on L1 and still runs in less than 1 minute. Compared to k-mean++, multi-threading sDBSCAN runs faster and offers significantly higher NMI with L1. We emphasize that the advantage of multi-threading sDBSCAN comes from its simplicity, as it is effortless engineering to run sDBSCAN on multi-threads.Among sampling-based approaches, uDBSCAN++ gives the highest NMI score of 46%, while kDBSCAN++ is very slow. kDBSCAN++ runs approximately 5× slower than uDBSCAN due to the overhead of k-center initialization and the efficiency of KD-Trees on Pamap2 with d = 51. In general, sDBSCAN provides competitive clustering accuracy and runs significantly faster than other DBSCAN variants. Like Mnist, our sOPTICS on Pamap2 runs in less than 2 minutes, even faster than any sampling-based implementations.As Mnist8m is non-negative, we conduct experiments on cosine, L2, and L1, χ 2 , and JS distances. Similar to Mnist, sOPTICS graphs show L1 is inferior, so we do not report L1 here. uDBSCAN++ and kDBSCAN++ with p = 0.001 could not finish after 3 hours. It is not surprising as our multi-threading sngDBSCAN runs in nearly 1 hour, and single thread sngDBSCAN is at least 4× faster than DBSCAN++ variants on Mnist. As we cannot run scikit-learn k-means++, we use the result of 41% NMI given by a fast kernel k-means [21] running on a supercomputer with 32 nodes, each of which has two 2.3GHz 16-core (32 threads) Haskell processors and 128GB of DRAM. This configuration of a single node is similar to our conducted machine. Table 6 and 7 summarize the performance of multi-threading sDBSCAN-1NN, sDBSCAN, and sngDBSCAN, including the NMI score on the best ε and the running time, on L2, cosine, χ 2 , and JS. sDBSCAN-1NN runs in at most 15 minutes and returns the highest NMI among DBSCAN variants with a peak of 38% NMI on χ 2 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-1NN as it does not assign labels to non-core points, and still achieves significantly higher NMI scores than sngDBSCAN on all 4 studied distances. Among 4 distances, L2 shows lower accuracy but runs faster than χ 2 and JS due to the faster distance computation. sDBSCAN runs 6.4× faster than sngDBSCAN, which is justified by the number of distance computations np = 8, 100 of sngDBSCAN compared to 2km = 1000 of sDBSCAN. As sDBSCAN-1NN samples 0.01n core points to build the approximate 1NN classifier, the running time overhead of this extra step is smaller than sDBSCAN's time.We first show empirical results on random kernel mappings that facilitate sDBSCAN and sOPTICS on L1, L2, χ 2 , and JS distance. We use Pamap2 for L1 and L2 as it contains negative values and Mnist for χ 2 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 σ used on random kernel mappings on L1 and L2. We fix k = 10, m = minP ts = 50, D = 1024, d ′ = 1024 and vary σ for L1 and L2. Figure 7 shows the accuracy of sDBSCAN on the recommended range of ε by sOPTICS graphs with σ = {50, 100, 200, 400} for L1 on Figure 8 and σ = {20, 40, 80, 160} for L2 on Figure 9 .Table 7 : The NMI on the best ε and running time comparison of multi-threading DBSCAN variants on χ 2 and JS distances on Mnist8m. Kernel k-means (k = 10) [21] runs in 15 minutes on a supercomputer of 32 nodes and achieves NMI 41%.EQUATIONmin 0.17 38% 15 min 0.15 sDBSCAN 32% 10 min 0.17 31% 10 min 0.15 sngDBSCAN (p = 0.001) 28% 64 min 0.15 27% 64 min 0.17 While L1 provides 46% NMI, higher than just 40% NMI by L2, the setting σ = 2ε reaches the peak of NMI for both L1 and L2. For example, sDBSCAN at ε = 50, σ = 100 reaches NMI 46% for L1. sDBSCAN at ε = 15, σ = 20 and ε = 21, σ = 40 reach NMI of 40% for L2. Also, the performance of sDBSCAN is not sensitive to the value σ, especially with the guide of sOPTICS graphs. For example on L2 as shown in Figure 9 , σ = 160 suggests the suitable range [40, 50] while σ = 80 shows [30, 40] . The best values of ε of these two σ values are clearly on these ranges, as shown in Figure 7 (b). This observations appear again on σ = {20, 40} for the range of [10, 20] and [20, 30] , respectively.χ 2 and JS on Mnist. We carry out experiments to evaluate the sensitivity of the parameter d ′ used on random kernel mappings on χ 2 and JS. We fix k = 5, m = minP ts = 50, D = 1024 and vary d ′ . We note that [20] approximates χ 2 and JS distance using the sampling approach, hence we set the sampling interval as 0.4, as suggested on scikit-learn 7 . We also note that d ′ should be set as (2l + 1)d for l ∈ N. Hence, we set d ′ = {3d, 5d} in our experiment. distances. Figure 14 shows the accuracy of sDBSCAN compared to other competitors on 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 minP ts though a larger minP ts requires larger m which increases the running time. Each instance of sDBSCAN runs in 0.5 minutes, which is significantly faster than 3 minutes by uDBSCAN++ and 13.4 minutes by kDBSCAN++. sDBSCAN shows the advantage of running on many distance measures, which leads to the highest of 48% of NMI of L1. In contrast, uDBSCAN++ achieves the highest of 46% of NMI among cosine and L2 distances.Mnist8m. Figure 15 shows sOPTICS graphs on Mnist8m with L2, cosine, χ 2 and JS distances where we use σ = 4000 for L2, and d ′ = d on χ 2 and JS. It shows the advantages of sDBSCAN on supporting many distances and predicts that cosine, χ 2 and JS provide higher accuracy than L2.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-1NN with the approximation 1NN heuristic to cluster border and noisy points detected by sDBSCAN. It shows again that sDBSCAN variants outperform sngDBSCAN on all studied distances. sDBSCAN-1NN on a single computer nearly reaches the accuracy of kernel k-means [21] . Regarding the speed, each instance of sDNSCAN-1NN runs in less than 15 minutes, which is the time requirement for kernel k-means on a supercomputer. 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 be 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 it is clear that these goals are not attained by the paper.• The answer NA means that the paper does not include experiments.• 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 a 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 is 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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.C++ STL priority queue does not support decrease-key function.https://eigen.tuxfamily.orghttps://sites.google.com/view/approxdbscanhttps://github.com/jenniferjang/dbscanpphttps://github.com/jenniferjang/subsampled_neighborhood_graph_dbscanhttps://scikit-learn.org/stable/modules/clustering.htmlhttps://github.com/scikit-learn/scikit-learn/blob/5c4aa5d0d/sklearn/kernel_ approximation.py 


Decision: 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

Reviews: review: paper_summary: paper_summary: Paper studies scalable algorithms for DBSCAN, a popular clustering method. 
In DBSCAN, each point considers a radius of epsilon, and is called "core" if it has at least m points in the epsilon ball.
Then, each core point is connected to all other points (core or non-core) in its epsilon ball.

Finally, 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.

This 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. 
To 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.
If we set m and m' suitably, we can prove that most of the real points are captured and this estimate works well.

The 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. 

The paper also gives emperical evals against SoTA implementations / approximations of DBSCAN and shows faster compute, and better Quality across different datasets.
strength_weakness: strength_weakness: 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.
questions: 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.
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.
More generally I can use any SOTA approx. nearest neighbor method? Example HNSW or FAISS or SCANN? Will that not work?
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?
limitations: limitations: Would be good to include limitations section in paper.
paper_summary: paper_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$.

This 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.

To 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.

Finally, 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.

They 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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. "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..."?

2. In algorithm 2, why do you also need the furthest vectors?

3. 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?

4. 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?

5. Can you clarify exactly what was a novel contribution and what was repurposed from prior works?
limitations: limitations: I do not see anything of concern.
paper_summary: paper_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.
strength_weakness: strength_weakness: The paper is hard to read due to many language errors, odd sentences and sloppy formulations.

Lemma 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: 
* $\mathcal{S}^{d-1}$ in Lemma 1 is not introduced.
* 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. 
* 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|$.

The 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]

Minor comments:
* Line numbers would be helpful in the reviewing process. Please use the NeurIPS latex template without changing any of the settings.
* The plots shown in Figure 1 are too small and the labels are not readable. 

[1] Vinh, N. X., Epps, J., and Bailey, J. Information theoretic measures for clusterings comparison: Variants, properties,
normalization and correction for chance. The Journal of Machine Learning Research, 11:2837–2854, 2010.
[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.
questions: questions: How fast should $D$ grow be in terms of $d,n$ in order for Lemma 1 to hold?

The assumption regarding $t$ described between Lemma 2 and Theorem 1 (once again: please enable line numbers) seems somewhat strong. Could you comment on this?

In 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: limitations: Usage of NMI and missing proof of Lemma 1 (see above)
paper_summary: paper_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.
strength_weakness: strength_weakness: W1. The main contribution may not be very high, because the core idea of approximating $\varepsilon$-neighborhood is borrowed from the previous work [22].

W2. 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?

W3. More datasets need to be included for the evaluation. Only three datasets may not be sufficient to show the superiority of the proposed algorithm.

W4. 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.

W5. 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.

W6. 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.

W7. (Minor) NeurIPS may not be the best venue for this paper. KDD best suits this paper.

---

After rebuttal, I have increased my rating to 5.
questions: questions: See W1~W6.
limitations: limitations: The authors discussed the limitations about a sufficiently large number of random vectors, which sound reasonable.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The algorithm’s performance may depend on the selection of parameters, and the sensitivity to these parameters is not deeply explored.
2. The use of random projections and kernel features might complicate the implementation and understanding of the algorithm for practitioners.
3. While the algorithm is extended to other distance metrics, the performance and effectiveness of these extensions are not thoroughly evaluated.
4. The paper could benefit from a more comprehensive comparative analysis with a broader range of clustering algorithms beyond DBSCAN variants.
questions: 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?
2. How does sDBSCAN perform when extended to L2, L1, χ², and Jensen-Shannon distances in terms of both accuracy and speed?
3. How robust is sDBSCAN to variations in data distribution and the presence of noise and outliers?
4. Are there specific real-world applications or case studies where sDBSCAN has shown significant advantages over other clustering methods?
limitations: limitations: N/A

Comments: title: Thank you for your clarification
Thank you for your responses
comment: Thanks for your comment. Since your confidence is 5 and you have not indicated which of your concerns have not been addressed and its rationale, we feel that we have not had any chance to clarify further.
Dear authors, I have read your rebuttal and my evaluation remains unchanged
Thanks for your comment and update the score.

We will fix all sloppy notations of Lemma 1 as your suggestions. 
We will report both AMI and CC for Mnist, Pamap, and Mnist8m data sets.
We also keep NMI on Mnist8m for kernel k-means on the appendix, and cite the two papers you suggested regarding the cluster validation.
> New measurements (CC) instead of NMI / AMI

Thank you for your updated results. It is indeed clear that sDBSCAN outperforms the other sampling methods.

> Lemma 1 holds given the limit in distribution (weak limit).

Thank you for clarifying. It is important to update this in the paper, because the '$\sim$' notation in a limit $D\rightarrow\infty$ is simply not sound. 

> That is, given $r_*$ is closest to $q$ among $D$ random vectors

I really think you should formulate the lemma by *defining* $r_*$ to be the closest to $q$ among $D$ random vectors, because this is cleaner in a probabilistic setting than using language like "assuming" or "given".

> Regarding your question about non-asymptotic results

I did not ask about any non-asymptotic results. Previously, I was under the impression that we also needed $n\rightarrow\infty$ for Lemma 1 to hold, but I now see that this is not the case. In such double limits, it is always worth asking how fast/slow one quantity can grow with respect to the other, which is why I asked about $D=\log\log n$. But I now see that this question does not make any sense.

I am willing to increase my rating. But I do this hoping that the authors will improve the formulation of Lemma 1 (describing the weak limit, defining $r_*$ adequately and adding a proof in the appendix) and improve the experimental validation (report AMI / correlation instead of NMI, except possibly when comparing to other papers). This paper is a solid contribution and sDBSCAN is clearly a great improvement upon other sampling methods. You have the theoretical and experimental results to show this, but their presentation just needs some improvement.
Thank for your comments and we are sorry that our rebuttal does not satisfy your request. We address your main concerns below.

**New measurements (CC) instead of NMI / AMI**

We went through the paper (indeed its arxiv version) [2] you suggested and found the way to compute the correlated coefficient (CC) between two clustering labels in $O(n)$ times. Using sklearn.metrics.cluster.pair_confusion_matrix() to compute N11, N10, N01, N00 values, we can compute any kinds of pair-counting based scores on Table 5 (Appendix B), including CC. We have generated a new figures on NMI, AMI, CC on Mnist and Pamap, but cannot update the response.pdf. So we add a table regarding CC on Mnist with cosine here as a reference.

| $\epsilon$ | sDBSCAN | sngDBSCAN | uDBSCAN | kDBSCAN | DBSCAN |
|----------------|----------------|-------------------|----------------|----------------|--------------|
| 0.1 | 0.13 | 0.072 | 0.039 | 0 | 0.142 |
| 0.11 | 0.13 | 0.083 | 0.07 | 0 | 0.169 |
| 0.12 | 0.134 | 0.09 | 0.093 | 0 | 0.164 |
| 0.13 | 0.145 | 0.097 | 0.094 | 0 | 0.144 |
| 0.14 | 0.166 | 0.104 | 0.096 | 0 | 0.132 |

Regarding the CC measure, sDBSCAN is still better than the other sampling DBSCAN variants on the suggested range of $\epsilon$.
________________________________________________________
For the reponse.pdf, the x-axis is the value of $\epsilon$ suggested by the sOPTICS graphs. 
The y-axis is the NMI and AMI scores in percentages, measured at 6 different values of $\epsilon$.
We observe that the NMI and AMI scores are very similar, e.g. Fig 1(a) at $\epsilon = 0.14$, sDBSCAN has NMI = 0.4139, AMI = 0.4132; uDBSCAN has NMI = 0.3112, AMI = 0.3095, but sngDBSCAN has NMI = 0.3170, AMI = 0.2678.
Similar to Pamap data set, the difference between AMI and NMI scores of all methods is negligible (within 0.002).

**The asymptotic theoretical analysis of Lemma 1**

Lemma 1 holds given the limit in distribution (weak limit).
That is, given $r_*$ is closest to $q$ among $D$ random vectors, then $x^T r_* \xrightarrow{D} N(x^T q \sqrt{2 \log{D}}, 1 - (x^T q)^2)$.

This is the main finding of [22], which shows the connection between random projections when $D \rightarrow \infty$ and the asymptotic behavior of the concomitants of extreme order statistics [18].
It has been used to speed up nearest neighorbor search [23].

[22] Simple Yet Efficient Algorithms for Maximum Inner Product Search via Extreme Order Statistics - KDD 21

[23] Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search - NeurIPS 22

[18] The Asymptotic Theory of Concomitants of Order Statistics - Journal of Applied Probability 74
________________________________________________________

Regarding your question about non-asymptotic results, as far as we know, it seems impossible to achieve the normal distribution given any relationship between $D$ and $n$.
We have not found any result that studies the non-asymptotic behavior of extreme order statistics and its concomitants.
We conjecture that such (useful) non-asymptotic results might not exist due to the field of extreme value theory.

Our previous rebuttal shows our effort to achieve non-asymptotic results.
We first bound the value of $Q_*$, the maximum value of $D$ independent normal variables. 
Another approach using Fisher–Tippett–Gnedenko theorem to estimate $E[Q_*]$ can be seen here (https://en.wikipedia.org/wiki/Generalized_extreme_value_distribution).

Set $\delta = 1 / \sqrt{\log{D}}$, we have $\sqrt{2 \log{D}} (1 - o(\log{\log{D}} / \log{D}) < Q_* < \sqrt{2 \log{D}}$ with prob. $1 - 2\delta$.
To ensure $Q_*$ is highly concentrated on its expectation, i.e. $E[Q_*] \sim \sqrt{2 \log{D}}$, we need $D = e^{n^4}$.
The questioned setting $D = \log{\log{n}}$ does not work as $\log{\log{D}} / \log{D}$ is not small enough.

When $D = e^{n^4}$, we have $\delta = 1/n^2$. 
By the union bound, we can show that **all** $n$ random variables $Q^i_*$ corresponding to the point $x_i$ will be around its expectation with probability $1 - 1/n$.
After that, using the bivariate normal distribution between $X_i = x^T r_i$ and $Q_i = q^T r_i$, we can bound the tail of $x^T r_*$ where $r_*$ is the closest random vector to $q$.

The setting of $D = e^{n^4}$ to ensure the concentration of maximum of $D$ normal variables around $\sqrt{2 \log{D}}$ is pessimistic since it applies to the worst-case distribution of data.
We found that there are several papers (in theory) that use $Q_* = \sqrt{2 \log{D}}$ to derive their results, for example

- Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding. IEEE Trans. Inf. Theory 60(6): 3265-3278 (2014)
- Distributed Estimation of Gaussian Correlations. IEEE Trans. Inf. Theory 65(9): 5323-5338 (2019)

If we use $Q_* = \sqrt{2 \log{D}}$ as theoretical results above, Lemma 1 holds as $x^T r_* = \rho \sqrt{2 \log{D}} + Z_i \sim N( \rho \sqrt{2 \log{D}}, 1 - \rho^2)$ where $\rho = x^T q$ and $Z_i \sim N(0, 1 - \rho^2)$.
Thanks for your comment. I hope you will engage in a discussion with ACs and other reviewers in the next stage to finalize the decision.
Thank you for your responses. Based off this and the other reviewers' comments, I will maintain my review score. I would more strongly defend this paper if I were more of an expert in this area, however I am still not confident about my review.
I thank the authors for their rebuttal.

>  Lemma 1 follows the results of [22] in case data points are on a unit sphere, and it holds when $D \rightarrow \infty$.

This does not answer my question concerning what limit is proven. Does Lemma 1 concern a limit in distribution (weak limit) or an exact result (the r.v. exactly follows the normal distribution) for $D$ above some threshold? 

> 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.

This is incorrect. One does not have to compute these pair-counting vectors in order to compute the value of this measure. This measure (and any other pair-counting measure) can be computed in $O(n)$, as explained in [2]. Actually, computing the correlation is faster than computing AMI, which may have quadratic complexity if one of the partitions consist of many clusters.

> We found that sngDBSCAN's AMI is even lower than its NMI (See the figure in response.pdf).

One cannot compare AMI values to NMI values. They are different measures.  One can, however, compare how the two measures rank a given set of clustering methods. In general, reporting AMI values is preferred over reporting NMI values, because NMI is a biased measure. I can understand that you might want to use NMI to compare your results to previous work, but please report AMI (or correlation) in all other cases.

Moreover, I don't understand the plots in rebuttal.pdf: your x-axes have NMI and AMI written on them, but with values exceeding 1000. Both NMI and AMI are upper-bounded by 1 (or by 100, if expressed as 'percentages').

> For our theoretical analysis, we use Lemma 1 with $D \rightarrow \infty$, and we stated on Limitations.

$D\rightarrow\infty$ as $n\rightarrow\infty$? This would allow for $D=\log\log n$. Are you sure this is sufficient?

The proposed method definitely is certainly a great contribution, but the theoretical validation is unacceptable. In particular, the asymptotics seems quite sloppy. I will decrease the rating.
Thanks for your comment.
Thank you for your further clarification. **In practice**, it is hard to pick the best distance measure, since we do not know the NMIs in real-world applications. Also, the original DBSCAN algorithm is not restricted to a specific distance measure (I am not familiar with DBSCAN++). Overall, I would like to stick to the current rating.
Thanks for your comments and your score increase. 

If possible, could you let us know the concerns that you are not satisfied and the rationale, so that we have chance to clarify and change your opinion on our work?
The authors addressed some of my concerns in this rebuttal. I would like to increase my score to 4 instead of 3.
Thanks for clarification and your score increase. We would like to explain further for W4 and W6

**W4. 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.**

The camera-ready has one extra page. If the submission get accepted, we will use this extra page to explain OPTICS and sOPTICS. This would make the paper stand-alone and clearify the contributions of our work.
We feel it is hard to squeeze both sOPTICS and sDBSCAN into the current limits of 9 pages.
We hope you understand.

**W6. 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.**

We agree that sDBSCAN's peaks are lower than the other algorithms in Fig 2 and 3, and would like to add further explanation.

Compared to sngDBSCAN, sDBSCAN's peak is often higher on all studied metrics on both Fig 2 and 3.

In Fig 2, sDBSCAN's peaks are lower than uDBSCAN++ on L2, and lower than both uDBSCAN++ and kDBSCAN++ on Cosine. 
However, sDBSCAN's on L1 is higher than those peak values on L2 and Cosine.
On Tab 5 (Appendix), sDBSCAN on L1 reach 46% NMI, while uDBSCAN++ reaches 46% and kDBSCAN++ reaches 39% on cosine.
This indeed shows the advantages of sDBSCAN that can work on several metric distances, while DBSCAN++ works only on L2 (given the current theory and released implementation).


We also note that the range of $\epsilon$ is found by sOPTICS.
Without such recommendation, the cost of finding relevant $\epsilon$ for sampling DBSCAN variants can be as inefficient as running an exact OPTICS (i.e. $O(n^2)$ in both space and time).
To add an evidence, sngDBSCAN [15] studied several low-dimensional million-point data sets. Their Fig 4 shows that good $\epsilon$ for each data set is on very different ranges $[0.5, 2.0], [0, 12], [0, 0.04], [1, 5], [0, 0.08]$ !!!

In Fig 3, sDBSCAN could not reach the accuracy of kernel k-mean. This experiment setting is less favoured to sDBSCAN. 
While kernel k-means use the prior knowledge k = 10 and run on a supercomputer, sDBSCAN selects $\epsilon$ based on sOPTICS without any ground-truth, and run on a single machine.

_________

Thank again for your comment, and please let us know any other concerns that we should address to change your opinion on our work.
Thank you for your responses. I have carefully read the authors' rebuttal.

The responses for W1, W2, and W5 are understandable, so I would like to increase my rating to 5. For W6, I meant Figure 2 and Figure 3, where the peaks of sDBSCAN are often lower than those of the other algorithms.