KNN-BLOCK DBSCAN: Fast Clustering for Large-Scale Data
The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Abstract
Large-scale data clustering is an essential key for big data problem. However, no current existing approach is “optimal” for big data due to high complexity, which remains it a great challenge. In this article, a simple but fast approximate DBSCAN, namely, KNN-BLOCK DBSCAN, is proposed based on two findings: 1) the problem of identifying whether a point is a core point or not is, in fact, a kNN problem and 2) a point has a similar density distribution to its neighbors, and neighbor points are highly possible to be the same type (core point, border point, or noise). KNN-BLOCK DBSCAN uses a fast approximate kNN algorithm, namely, FLANN, to detect core-blocks (CBs), noncore-blocks, and noise-blocks within which all points have the same type, then a fast algorithm for merging CBs and assigning noncore points to proper clusters is also invented to speedup the clustering process. The experimental results show that KNN-BLOCK DBSCAN is an effective approximate DBSCAN algorithm with high accuracy, and outperforms other current variants of DBSCAN, including ρ-approximate DBSCAN and AnyDBC.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1996) · Cited by 20,179
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199 · cited 1×
“According to Jain et al. [12], different categories of these clustering approaches are recognized: centroid-based clustering, partitioning clustering, density-based clustering etc.”
BackgroundThe Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
A tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
Data clustering: 50 years beyond K-means
Jain, A. K. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2009.09.011 · Cited by 9,368
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520 · cited 1×
“Therefore, many techniques of this field, such as FLANN [18], kd -tree [19], cover tree [20], etc., can be utilized.”
MethodClustering by fast search and find of density peaks
Rodriguez, A., & Laio, A. (2014) · Science · doi:10.1126/science.1242072 · Cited by 4,942 · cited 2×
“To speedup the range query process, it uses kd -trees [14] for indexing data, and performs substantially fewer range queries compared to DBSCAN while still guaranteeing the exact final result of DBSCAN.”
MethodAnkerst, M. (1999) · doi:10.1145/304181.304187 · Cited by 3,982
Mean shift, mode seeking, and clustering
Cheng, Y. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.400568 · Cited by 3,856 · cited 2×
“There are many algorithms of this kind, such as DBSCAN [4], OPTICS [13], DPeak [14]–[16], mean shift [3], DCore [11], etc.”
BackgroundMethodThe global k-means clustering algorithm
Likas, A., Vlassis, N., & J. Verbeek, J. (2003) · Pattern Recognition · doi:10.1016/s0031-3203(02)00060-2 · Cited by 3,733 · cited 1×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k-means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirichlet model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
BackgroundFAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640 · cited 1×
“For example, FLANN [18], [38] uses the priority search k -means tree or the multiple randomized kd forest [39] which can give the best performance on a wide range of dimensional data space.”
MethodScalable Nearest Neighbor Algorithms for High Dimensional Data
Muja, M., & Lowe, D. G. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2321376 · Cited by 1,407 · cited 7×
“For example, in original DBSCAN, a data point p may be classified into one cluster, while in approximate Algorithm 1 [18] SearchKmeansTree 1: Input: query point q ; the K value of kNN; the maximum number of examined points L ; k -means tree T ; 2: count : = 0; 3: PQ : = empty priority queue 4: R : =…”
BackgroundMethodInfluentialOPTICS: ordering points to identify the clustering structure
Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999) · Proceedings of the 1999 ACM SIGMOD international conference on Management of data · doi:10.1145/304182.304187 · Cited by 1,335 · cited 2×
“…n / MinPts ) , where β is a factor about the distribution of the data, and b 0 is usually far less than n provided [ (cid:3), MinPts] are well chosen (how to choose good parameters for DBSCAN is another big topic, such as OPTICS [13] and others [41]–[43], which is out of the scope of this article).”
BackgroundMethodCover trees for nearest neighbor
Beygelzimer, A., Kakade, S., & Langford, J. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143857 · Cited by 813 · cited 1×
“Therefore, many techniques of this field, such as FLANN [18], kd -tree [19], cover tree [20], etc., can be utilized.”
MethodOptimised KD-trees for fast image descriptor matching
Silpa-Anan, C., & Hartley, R. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587638 · Cited by 677 · cited 1×
“For example, FLANN [18], [38] uses the priority search k -means tree or the multiple randomized kd forest [39] which can give the best performance on a wide range of dimensional data space.”
MethodRobust path-based spectral clustering
Chang, H., & Yeung, D.-Y. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2007.04.010 · Cited by 565
Cluster ensembles: a knowledge reuse framework for combining partitionings
Strehl, A. L., & Ghosh, J. (2002) · National Conference on Artificial Intelligence · doi:10.5555/777092.777110 · Cited by 379
RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates
Bryant, A., & Cios, K. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2787640 · Cited by 273 · cited 1×
“A scalable RNN-DBSCAN [32] solution was investigated to improve DBSCAN by using an approximate kNN algorithm.”
MethodFast density peak clustering for large scale data based on kNN
Chen, Y., Hu, X., Fan, W., Shen, L., Zhang, Z., Liu, X., Du, J., Li, H., Chen, Y., & Li, H. (2020) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.06.032 · Cited by 234
Self-citationDBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation
Gan, J., & Tao, Y. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2737792 · Cited by 221 · cited 2×
“We also concentrate on comparing our algorithm with DBSCAN, ρ -approximate DBSCAN [17], and AnyDBC.”
MethodResultMTFH: A Matrix Tri-Factorization Hashing Framework for Efficient Cross-Modal Retrieval
Liu, X., Hu, Z., Ling, H., & Cheung, Y.-M. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2019.2940446 · Cited by 220
Self-citationPattern Recognition Algorithms for Data Mining
Pal, S. K., & Mitra, P. (2004) · Chapman & Hall/CRC eBooks · doi:10.1201/9780203998076 · Cited by 183
Chen, Y., Tang, S., Bouguila, N., Wang, C., Du, J., & Li, H. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2018.05.030 · Cited by 169 · cited 1×
“2) In the case of the grid technique is used, the side length of each cell is fixed to (cid:3)/ √ D , which implies that it is almost useless in high dimension [40].”
MethodSelf-citationGionis, A., Mannila, H., & Tsaparas, P. (2005) · 21st International Conference on Data Engineering (ICDE'05) · doi:10.1109/icde.2005.34 · Cited by 169
Choosing DBSCAN Parameters Automatically using Differential Evolution
Karami, A., & Johansson, R. (2014) · International Journal of Computer Applications · doi:10.5120/15890-5059 · Cited by 164 · cited 1×
“…n / MinPts ) , where β is a factor about the distribution of the data, and b 0 is usually far less than n provided [ (cid:3), MinPts] are well chosen (how to choose good parameters for DBSCAN is another big topic, such as OPTICS [13] and others [41]–[43], which is out of the scope of this article).”
BackgroundCollins, L. M., & Dent, C. W. (1988) · Multivariate Behavioral Research · doi:10.1207/s15327906mbr2302_6 · Cited by 161 · cited 1×
“Omega-Index [45] and normalized mutual information (NMI) [46] are two well known methods to evaluate clustering result, then similar to [47], we use them to make comparisons for KNN-BLOCK DBSCAN and ρ -approximate DBSCAN.”
MethodVehicle Re-Identification Using Quadruple Directional Deep Learning Features
Zhu, J., Zeng, H., Huang, J., Liao, S., Lei, Z., Cai, C., & Zheng, L. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2901312 · Cited by 158
Clustering with Local Density Peaks-Based Minimum Spanning Tree
Cheng, D., Zhu, Q., Huang, J., Wu, Q., & Yang, L. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2930056 · Cited by 142 · cited 1×
“There are many algorithms of this kind, such as DBSCAN [4], OPTICS [13], DPeak [14]–[16], mean shift [3], DCore [11], etc., where DBSCAN [4] is the most famous one and has been widely used.”
MethodA Novel Cluster Validity Index Based on Local Cores
Cheng, D., Zhu, Q., Huang, J., Wu, Q., & Yang, L. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2853710 · Cited by 133 · cited 1×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k -means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirich-let model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
BackgroundPrivacy-preserving public auditing for secure data storage in fog-to-cloud computing
Tian, H., Nan, F., Chang, C., Huang, Y., Lu, J., & Du, Y. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.12.004 · Cited by 115
Fast neighbor search by using revised k-d tree
Chen, Y., Zhou, L., Tang, Y., Singh, J. P., Bouguila, N., Wang, C., Wang, H., & Du, J. (2018) · Information Sciences · doi:10.1016/j.ins.2018.09.012 · Cited by 112 · cited 1×
“For example, partition trees ( kd -tree [34], [35], semi-convex hull tree [36]), hashing techniques such as ANN based on trinary-project tree [37].”
MethodSelf-citationMining Cluster-Based Temporal Mobile Sequential Patterns in Location-Based Service Environments
Lu, E. H.-C., Tseng, V. S., & Yu, P. S. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.155 · Cited by 98
Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs
Gieseke, F. C., Heinermann, J., Oancea, C. E., & Igel, C. (2014) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 97
Trinary-Projection Trees for Approximate Nearest Neighbor Search
Wang, J., Wang, N., Jia, Y., Li, J., Zeng, G., Zha, H., & Hua, X. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.125 · Cited by 91 · cited 1×
“For example, partition trees ( kd -tree [34], [35], semi-convex hull tree [36]), hashing techniques such as ANN based on trinary-project tree [37].”
MethodPublic auditing for shared cloud data with efficient and secure group management
Tian, H., Nan, F., Jiang, H., Chang, C., Ning, J., & Huang, Y. (2018) · Information Sciences · doi:10.1016/j.ins.2018.09.009 · Cited by 84
Using grid for accelerating density-based clustering
Mahran, S., & Mahar, K. (2008) · IEEE International Conference on Computer and Information Technology (CIT) · doi:10.1109/cit.2008.4594646 · Cited by 79 · cited 1×
“MahranandMahar [25] introduced an algorithm named GriDBSCAN to enhance the performance of DBSCAN by using grid partitioning and merging, yielding a high performance with the advantage of a high degree of parallelism.”
MethodLulli, A., Dell’Amico, M., Pietro Michiardi, A., & Ricci, L. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021932 · Cited by 70 · cited 1×
“NG-DBSCAN [33] is an approximate density-based clustering algorithm that operates on arbitrary data and any symmetric distance measure.”
Decentralized Clustering by Finding Loose and Distributed Density Cores
Chen, Y., Tang, S., Zhou, L., Wang, C., Du, J., Wang, T., & Pei, S. (2016) · Information Sciences · doi:10.1016/j.ins.2016.08.009 · Cited by 69 · cited 3×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k -means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirich-let model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
BackgroundMethodSelf-citationScalable parallel OPTICS data clustering using graph algorithmic techniques
Patwary, M. A., Palsetia, D., Agrawal, A., Liao, W., Manne, F., & Choudhary, A. (2013) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2503210.2503255 · Cited by 63 · cited 1×
“Omega-Index [45] and normalized mutual information (NMI) [46] are two well known methods to evaluate clustering result, then similar to [47], we use them to make comparisons for KNN-BLOCK DBSCAN and ρ -approximate DBSCAN.”
MethodGMDBSCAN: Multi-Density DBSCAN Cluster Based on Grid
Xiaoyun, C., Min, Y., Yan, Z., & Wang, P. (2008) · IEEE International Conference on e-Business Engineering (ICEBE) · doi:10.1109/icebe.2008.54 · Cited by 60 · cited 1×
“Besides, parallel GridDBSCAN [26] and GMDBSCAN [27] are also grid-based DBSCAN.”
MethodGunawan, A. (2013) · TU/e Research Portal · Cited by 54
Axially Symmetric Data Clustering Through Dirichlet Process Mixture Models of Watson Distributions
Fan, W., Bouguila, N., Du, J., & Liu, X. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2872986 · Cited by 41 · cited 1×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k -means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirich-let model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
BackgroundSelf-citationFan, W., Sallay, H., & Bouguila, N. (2016) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2574500 · Cited by 37 · cited 1×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k -means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirich-let model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
BackgroundPublic audit for operation behavior logs with error locating in cloud storage
Tian, H., Chen, Z., Chang, C., Huang, Y., Wang, T., Huang, Z., Cai, Y., & Chen, Y. (2018) · Soft Computing · doi:10.1007/s00500-018-3038-8 · Cited by 33
Self-citationMulti-label learning with multi-label smoothing regularization for vehicle re-identification
Hou, J., Zeng, H., Cai, L., et al. (2019) · Neurocomputing · doi:10.1016/j.neucom.2018.11.088 · Cited by 32 · cited 1×
“3) Apply it in our other researches, such as image retrieval [50], vehicle reidentification [51], [52], vehicle crushing analysis [53], and auditing for shared cloud data [54]–[56].”
BackgroundSPARCL: Efficient and Effective Shape-Based Clustering
Chaoji, V., Hasan, M. A., Salem, S., & Zaki, M. J. (2008) · Proceedings · doi:10.1109/icdm.2008.73 · Cited by 30 · cited 1×
“Unfortunately, this misclaim is widely accepted as a building brick in many research papers and textbooks, e.g., [22]–[24], etc.”
BackgroundKIDBSCAN: A New Efficient Data Clustering Algorithm
Tsai, C.-F., & Li, Y. (2006) · Lecture notes in computer science · doi:10.1007/11785231_73 · Cited by 29 · cited 1×
“KIDBSCAN [30] presents a new technique based on the concept of IDBSCAN, in which k -means is used to find the high-density center points and then IDBSCAN is used to expand clusters from these high-density center points.”
MethodDHeat: A Density Heat-Based Algorithm for Clustering With Effective Radius
Chen, Y., Tang, S., Pei, S., Wang, C., Du, J., & Xiong, N. N. (2017) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2017.2745493 · Cited by 28 · cited 1×
“label sets, which has been used in [11] and [49].”
MethodSelf-citationSemi-Convex Hull Tree: Fast Nearest Neighbor Queries for Large Scale Data on GPUs
Chen, Y., Zhou, L., Bouguila, N., Zhong, B., Wu, F. Q., Lei, Z., Du, J., & Li, H. (2018) · Proceedings · doi:10.1109/icdm.2018.00110 · Cited by 18 · cited 1×
“For example, partition trees ( kd -tree [34], [35], semi-convex hull tree [36]), hashing techniques such as ANN based on trinary-project tree [37].”
MethodSelf-citationClustering Based on Supervised Learning of Exemplar Discriminative Information
Duan, L., Cui, S., Qiao, Y., & Yuan, B. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2018.2870549 · Cited by 10 · cited 1×
“Currently, there are thousands of clustering algorithms have been proposed, for example, k -means [2], mean shift [3], DBSCAN [4], spectral clustering [5], [6], mixtures of dirich-let model [7], [8], clustering based on supervised learning [9], and clustering by local cores [10], [11].”
Background
Cited by
Feature weighting in DBSCAN using reverse nearest neighbours
Chowdhury, S., Helian, N., & Cordeiro de Amorim, R. (2023) · Pattern Recognition · doi:10.1016/j.patcog.2023.109314 · Cited by 39
Metadata
- Authors
- Chen, Y., Zhou, L., Pei, S., Yu, Z., Chen, Y., Liu, X., Du, J., & Xiong, N.
- Venue
- IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Published
- 2021-06
- Volume
- 51
- Issue
- 6
- Pages
- 3939-3953
- ISSN
- 2168-2216 (ISSN-L)
- 2168-2232
- OpenAlex
- W2996027253
- Cited by
- 204
- References
- 50
- FWCI
- 6.68
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.