Approximate DBSCAN under Differential Privacy
Yuan Qiu, Ke Yi · 2025
Read Approximate DBSCAN under Differential Privacy by Yuan Qiu, Ke Yi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08749.txt.
Introduction
Yuan Qiu and Ke Yi published a research paper in 2025 on clustering data points while keeping each person's data private. The popular DBSCAN method groups points by crowding, but private versions that print each point's group label, the pair argue, leak or garble too much to be useful. They propose printing the spans of the clusters instead.
On that new target they build a private clustering method that runs in straight-line time and meets a sandwich quality promise in any fixed dimension count. They also prove no method can do much better. A fast private histogram sits inside the method as a reusable part. Tests on fake and real data backed the design.
Catalog record
| CREATOR | Yuan Qiu, Ke Yi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-08749
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximate DBSCAN under Differential Privacy Yuan Qiu, Ke Yi Abstract This paper revisits the DBSCAN problem under differential privacy (DP). Existing DP-DBSCAN algorithms aim at publishing the cluster labels of the input points. However, we show that both empirically and theoretically, this approach cannot offer any utility in the published results. We therefore propose an alternative definition of DP-DBSCAN based on the notion of spans. We argue that publishing the spans actually better serves the purposes of visualization and classification of DBSCAN. Then we present a linear-time DP-DBSCAN algorithm achieving the sandwich quality guarantee in any constant dimensions, as well as matching lower bounds on the approximation ratio. A key building block in our algorithm is a linear-time algorithm for constructing a histogram under pure-DP, which is of independent interest. Finally, we conducted experiments on both synthetic and real-world datasets to verify the practical performance of our DP-DBSCAN algorithm. 1 Introduction 1.1 DBSCAN As one of the most popular clustering algorithms, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [ 17 ] has been receiving continuous attention [ 6 , 7 , 20 , 47 , 39 ] over the past 30 years. Unlike centroid-based clustering algorithms such as k-means [ 37 ] , which tend to identify clusters in spherical shapes, DBSCAN can detect clusters of arbitrary shapes. Additionally, DBSCAN offers several advantages, such as not requiring the number of clusters to be specified in advance and its robustness to outliers. Without loss of generality, we consider the d -dimensional unit cube \mathcal{L}:=[0,1]^{d} as the feature space, equipped with Euclidean distance \mathrm{dist}(\cdot,\cdot) . Two parameters decide the DBSCAN clustering result: a real number 1 1 1 We use \alpha instead of the usual symbol \varepsilon , which will be used to denote the privacy parameter. \alpha\in(0,1) and an integer \text{MinPts}\geq 1 . For any location l\in\mathcal{L} , its \alpha -neighborhood is defined as \mathbf{B}(l,\alpha):=\{l^{\prime}\in\mathcal{L}:\mathrm{dist}(l,l^{\prime})<\alpha\} , the d -dimensional ball centered at l with radius \alpha . Let P=(p_{1},\dots,p_{n})\in\mathcal{L}^{n} be the input point set. A point p\in P is called a core point , if its \alpha -neighborhood contains at least MinPts points of P , otherwise a noise point . Two core points p and q are \alpha -reachable if \mathrm{dist}(p,q)<\alpha ; they are \alpha -connected if they are directly or transitively \alpha -reachable. Then an (\alpha,\text{MinPts}) -cluster C is a nonempty maximal subset of the core points that are mutually \alpha -connected, and the DBSCAN output, denoted \mathcal{C}(\alpha,\text{MinPts}) , consists of all the (\alpha,\text{MinPts}) -clusters. Note that the noise points do not belong to any cluster. 1.2 Approximate DBSCAN In order to reduce the computational cost, Gan and Tao 2015 have introduced approximate DBSCAN based on the sandwich quality guarantee . For our purpose which will become clear shortly, we generalize their definition by introducing a second approximation parameter \tau (their definition is the special case \tau=0 ): Definition 1.1 (Sandwich Quality Guarantee) . For \rho>1 and 0\leq\tau<\text{MinPts} , a set of clusters \hat{\mathcal{C}} are called (\rho,\tau) -approximate clusters, if the following conditions are satisfied: 1. For each cluster C_{1}\in\mathcal{C}(\alpha,\text{MinPts}) , there exists an approximate cluster \hat{C}\in\hat{\mathcal{C}} such that C_{1}\subseteq\hat{C} . 2. For each approximate cluster \hat{C}\in\hat{\mathcal{C}} , there exists a cluster C_{2}\in\mathcal{C}(\rho\alpha,\text{MinPts}-\tau) such that \hat{C}\subseteq C_{2} . The approximation parameter \rho is critical in the computational complexity of DBSCAN: For any constant \rho>1 and constant d , they present an O(n) -time algorithm that returns (\rho,0) -approximate clusters for any P , while giving an \Omega(n^{4/3}) lower bound for \rho=1,\tau=0 (i.e., accurate clusters) for any d\geq 3 [ 20 ] . They also empirically demonstrate that approximate clusters are very close to the true clusters on most realistic datasets. 1.3 DBSCAN under Differential Privacy As with other learning algorithms, clustering results can contain sensitive information that may expose personal data, posing significant privacy risks. Unsurprisingly, DBSCAN has been studied under differential privacy (DP) [ 15 ] , the de facto standard for personal data privacy. Since publishing any of the input points in P cannot possibly satisfy DP, so existing work [ 42 , 38 , 43 , 29 ] choose to output only the cluster labels, i.e., the DP-DBSCAN output is a vector (c_{1},\dots,c_{n}) such that p_{i} and p_{j} are in the same cluster iff c_{i}=c_{j}>0 , while c_{i}=0 indicates that p_{i} is a noise point. However, we tested the existing DP-DBSCAN algorithms and find that they offer little utility. In all our test datasets, all these algorithms classified all points into a single cluster, which is clearly not informative. Our first result in this paper is a negative result, showing that this lack of utility is not due to the algorithm design, but the output format. Specifically, we prove that, if required to output the cluster labels of the input points, then no DP algorithm can achieve any finite \rho and any \tau<\text{MinPts} with constant probability, i.e., no non-trivial sandwich quality guarantee is achievable. (a) Clusters (Blobs) (b) Cluster spans (Blobs) (c) Clusters (Circles) (d) Cluster spans (Circles) Figure 1: Span of clusters. To get around this negative result, we propose an alternative output format for DP-DBSCAN: For a cluster C , we define its span as \operatorname{Span}(C):=\cup_{p\in C}\mathbf{B}(p,\alpha) , and we aim at outputting the spans of the clusters; please see some illustrations in Figure 1 . Compared with the cluster labels, the spans do not reveal how the input points themselves are clustered, which is impossible by our negative result. However, they serve the more useful functions of DBSCAN: visualization and classification. The visualization result is illustrated in Figure 1 ; more plots are provided in Section 8 . To classify a new point in the feature space, one can simply check which span the given point falls into, or declare it as a noise point if it does not fall into any span. Note that the spans may overlap a little bit, but the overlapping region must have width less than \alpha , and points falling into the overlapping region can be classified into either cluster. Essentially, these spans serve as a classification model, similar to the k centroids in k-means clustering. More importantly, we are able to design DP algorithms that output approximate spans that satisfy the sandwich quality guarantee: Definition 1.2 (Sandwich Quality Guarantee for Spans) . For \rho>0 and 0\leq\tau<\text{MinPts} , a collection of spans \mathcal{S}=\{S_{1},\dots,S_{m}\} are called (\rho,\tau) -approximate spans, if the following conditions are satisfied: 1. For each cluster C_{1}\in\mathcal{C}(\alpha,\text{MinPts}) , there exists a span S\in\mathcal{S} such that C_{1}\subseteq S . 2. For each span S\in\mathcal{S} , there exists a cluster C_{2}\in\mathcal{C}(\rho\alpha,\text{MinPts}-\tau) , such that S\subseteq\operatorname{Span}(C_{2}) . 1.4 Our Contributions Specifically, we make the following contributions in this paper with respect to DP-DBSCAN: (1) A new definition of approximate DP-DBSCAN (Section 3 ) We prove that, using the existing definition of DP-DBSCAN, it is impossible to achieve any meaningful utility guarantee. We then propose a span-based new definition, which not only allows us to achieve the sandwich quality guarantee, but also serves visualization and classification purposes of clustering. (2) Approximation lower bounds (Section 4 ) For the best achievable span-based sandwich quality guarantee, we first prove two lower bounds: \rho\geq 3 and \tau=\Omega(\frac{1}{\varepsilon}\log{\frac{1}{\rho\alpha}}) . Both lower bounds