A fast clustering algorithm based on pruning unnecessary distance computations in DBSCAN for high-dimensional data
Open accessThe DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Abstract
Abstract Clustering is an important technique to deal with large scale data which are explosively created in internet. Most data are high-dimensional with a lot of noise, which brings great challenges to retrieval, classification and understanding. No current existing approach is “optimal” for large scale data. For example, DBSCAN requires O(n2) time, Fast-DBSCAN only works well in 2 dimensions, and ρ-Approximate DBSCAN runs in O(n) expected time which needs dimension D to be a relative small constant for the linear running time to hold. However, we prove theoretically and experimentally that ρ-Approximate DBSCAN degenerates to an O(n2) algorithm in very high dimension such that 2D > > n. In this paper, we propose a novel local neighborhood searching technique, and apply it to improve DBSCAN, named as NQ-DBSCAN, such that a large number of unnecessary distance computations can be effectively reduced. Theoretical analysis and experimental results show that NQ-DBSCAN averagely runs in O(n*log(n)) with the help of indexing technique, and the best case is O(n) if proper parameters are used, which makes it suitable for many realtime data.
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
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
(1996) · Cited by 20,179
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956
Chameleon: hierarchical clustering using dynamic modeling
Karypis, G., Han, E.-H., & Kumar, V. (1999) · Computer · doi:10.1109/2.781637 · Cited by 2,097
International Encyclopedia of Statistical Science
(2011) · Springer eBooks · doi:10.1007/978-3-642-04898-2 · Cited by 1,653
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437 · cited 2×
“Therefore, in future work, we will try to improve quadtree-like hierarchical tree grid, by combining the merits of other techniques, such as product quantization for nearest neighbor search [52], LSH (Locality-Sensitive Hashing) [53], FLANN [54] etc.”
MethodST-DBSCAN: An algorithm for clustering spatial–temporal data
Birant, D., & Kut, A. (2007) · Data & Knowledge Engineering · doi:10.1016/j.datak.2006.01.013 · Cited by 1,430 · cited 1×
“Grid-based technique and approximation techniques are also popular, such as Fast-DBSCAN [45] and others [46, 47].”
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
Black hole: A new heuristic optimization approach for data clustering
Hatamlou, A. (2013) · Information Sciences · doi:10.1016/j.ins.2012.08.023 · Cited by 1,370
Trajectory clustering: a partition-and-group framework
Lee, J.-G., Han, J., & Whang, K.-Y. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247546 · Cited by 1,363 · cited 1×
“Innovative clustering methods [28, 29, 30] and parallel implementation frameworks [31, 32] have been proposed.”
MethodGionis, A., Mannila, H., & Tsaparas, P. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217303 · Cited by 819 · cited 1×
“which is a 2-dimensional data set with cardinality 8,000, and the other is Aggregation [58], which is a 2-dimensional data set with cardinality 788.”
BackgroundMORPH: A Longitudinal Image Database of Normal Adult Age-Progression
Ricanek, K., & Tesafaye, T. (2006) · 7th International Conference on Automatic Face and Gesture Recognition (FGR06) · doi:10.1109/fgr.2006.78 · Cited by 778
Parallel Spectral Clustering in Distributed Systems
Chen, W.-Y., Song, Y., Bai, H., Lin, C.-J., & Chang, E. Y. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.88 · Cited by 603
1985 ACM-SIGMOD international conference on management of data
(1985) · Information & Management · doi:10.1016/0378-7206(85)90026-6 · Cited by 485
Fuzzy clustering algorithms for unsupervised change detection in remote sensing images
Ghosh, A., Mishra, N. S., & Ghosh, S. (2011) · Information Sciences · doi:10.1016/j.ins.2010.10.016 · Cited by 345 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
Method2012 IEEE 12th International Conference on Data Mining
(2012) · doi:10.1109/icdm21070.2012 · Cited by 332
A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method
Mahesh Kumar, K., & Rama Mohan Reddy, A. (2016) · Pattern Recognition · doi:10.1016/j.patcog.2016.03.008 · Cited by 308 · cited 1×
“[34, 35, 36, 37], and has been widely applied in many applications, such as astronomy [38], neuroscience [39].”
BackgroundDBSCAN 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
Enhanced soft subspace clustering integrating within-cluster and between-cluster information
Deng, Z., Choi, K., Chung, F.-L., & Wang, S. (2009) · Pattern Recognition · doi:10.1016/j.patcog.2009.09.010 · Cited by 216
MR-DBSCAN: An Efficient Parallel Density-Based Clustering Algorithm Using MapReduce
He, Y., Tan, H., Luo, W., Mao, H., Ma, D., Feng, S., & Fan, J. (2011) · 2011 IEEE 17th International Conference on Parallel and Distributed Systems · doi:10.1109/icpads.2011.83 · Cited by 209
2006 IEEE International Conference on Systems, Man, and Cybernetics
(2006) · 2006 IEEE International Conference on Systems, Man and Cybernetics · doi:10.1109/icsmc.2006.384675 · Cited by 190
Fast density clustering strategies based on the k-means algorithm
Bai, L., Cheng, X., Liang, J., Shen, H., & Guo, Y. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2017.06.023 · Cited by 178 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundRough-DBSCAN: A fast hybrid density based clustering method for large data sets
Pulabaigari, V., & Babu, V. S. (2009) · Pattern Recognition Letters · doi:10.1016/j.patrec.2009.08.008 · Cited by 157 · cited 1×
“Grid-based technique and approximation techniques are also popular, such as Fast-DBSCAN [45] and others [46, 47].”
MethodTrajectory Clustering: A Partition-and-Group Framework
Lee, J.-G., Han, J., & Whang, K.-Y. (2007) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 155
A Multi-Task Learning Framework for Head Pose Estimation under Target Motion
Yan, Y., Ricci, E., Subramanian, R., Liu, G., Lanz, O., & Sebe, N. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2477843 · Cited by 141 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundKernel-induced fuzzy clustering of image pixels with an improved differential evolution algorithm
Das, S., & Kar, S. S. (2009) · Information Sciences · doi:10.1016/j.ins.2009.11.041 · Cited by 135 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
MethodOptimized Graph Learning Using Partial Tags and Multiple Features for Image and Video Annotation
Song, J., Gao, L., Nie, F., Shen, H. T., Yan, Y., & Sebe, N. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2601260 · Cited by 130 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundA survey on soft subspace clustering
Deng, Z., Choi, K., Jiang, Y., Wang, J., & Wang, S. (2016) · Information Sciences · doi:10.1016/j.ins.2016.01.101 · Cited by 128 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundBúza, K. (2013) · Studies in classification, data analysis, and knowledge organization · doi:10.1007/978-3-319-01595-8_16 · Cited by 120 · cited 1×
“The third, BlogFeedback [55] also comes from the UCI archive.”
BackgroundTransfer Prototype-Based Fuzzy Clustering
Deng, Z., Jiang, Y., Chung, F.-L., Ishibuchi, H., Choi, K., & Wang, S. (2015) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2015.2505330 · Cited by 116 · cited 1×
“For example, Wang and Deng developed a serial of important work on soft subspace clustering and fuzzy clustering for high dimensional data [41, 42, 43, 44], which overcome the drawbacks of utilizing only one distance function in most of existing clustering algorithms, and adaptively learn the distance functions suitab…”
BackgroundC-DBSCAN: Density-Based Clustering with Constraints
Ruiz, C., Spiliopoulou, M., & Menasalvas, E. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72530-5_25 · Cited by 110 · cited 1×
“DBSCAN has a large amount of extensions, e.g. [34, 35, 36, 37], and has been widely applied in many applications, such as astronomy [38], neuroscience [39].”
BackgroundAffective Visualization and Retrieval for Music Video
Zhang, S., Huang, Q., Jiang, S., Gao, W., & Tian, Q. (2010) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2010.2059634 · Cited by 98 · cited 1×
“S Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundCluster Prototypes and Fuzzy Memberships Jointly Leveraged Cross-Domain Maximum Entropy Clustering
Qian, P., Jiang, Y., Deng, Z., Hu, L., Sun, S., Wang, S., & Muzic, R. F. (2015) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2015.2399351 · Cited by 98 · cited 1×
“For example, Wang and Deng developed a serial of important work on soft subspace clustering and fuzzy clustering for high dimensional data [41, 42, 43, 44], which overcome the drawbacks of utilizing only one distance function in most of existing clustering algorithms, and adaptively learn the distance functions suitab…”
BackgroundGRIDBSCAN: GRId Density-Based Spatial Clustering of Applications with Noise
Uncu, O., Gruver, W. A., Kotak, D. B., Sabaz, D., Alibhai, Z., & Ng, C. (2006) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2006.384571 · Cited by 85 · cited 1×
“[48, 49, 50, 51], divide the data space by grids, perform clustering in each cell locally and merge the results thereby saving runtime.”
BackgroundUsing 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×
“Grid-based techniques, e.g. [48, 49, 50, 51], divide the data space by grids, perform clustering in each cell locally and merge the results saving runtime.”
MethodDecentralized 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 2×
“labels, which has been used in our previous works [61, 62].”
MethodSelf-citationChameleon based on clustering feature tree and its application in customer segmentation
Li, J., Wang, K., & Xu, L. (2008) · Annals of Operations Research · doi:10.1007/s10479-008-0368-4 · Cited by 67 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
MethodSatellite image segmentation with Shadowed C-Means
Mitra, S., & Kundu, P. P. (2011) · Information Sciences · doi:10.1016/j.ins.2011.04.027 · Cited by 63 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
MethodRajagopal, A. K., Subramanian, R., Ricci, E., Vieriu, R. L., Lanz, O., Ramakrishnan, K., & Sebe, N. (2013) · International Journal of Computer Vision · doi:10.1007/s11263-013-0692-2 · Cited by 62
GMDBSCAN: 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
Towards parameter-independent data clustering and image segmentation
Hou, J., Liu, W., Xu, E., & Cui, H. (2016) · Pattern Recognition · doi:10.1016/j.patcog.2016.04.015 · Cited by 56 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
MethodA Distance-Computation-Free Search Scheme for Binary Code Databases
Song, J., Shen, H. T., Wang, J., Huang, Z. H., Sebe, N., & Wang, J. (2016) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2016.2515990 · Cited by 55 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundGunawan, A. (2013) · TU/e Research Portal · Cited by 54
Data Analysis, Machine Learning and Knowledge Discovery
Spiliopoulou, M., Schmidt-Thieme, L., & Janning, R. (2013) · Studies in classification, data analysis, and knowledge organization · doi:10.1007/978-3-319-01595-8 · Cited by 54
Scalable Feature Matching by Dual Cascaded Scalar Quantization for Image Retrieval
Zhou, W., Yang, M., Wang, X., Li, H., Lin, Y., & Tian, Q. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2430329 · Cited by 52 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundSelf-citationA new fuzzy clustering algorithm for the segmentation of brain tumor
Ananthi, V. P., Balasubramaniam, P., & Kalaiselvi, T. (2015) · Soft Computing · doi:10.1007/s00500-015-1775-5 · Cited by 50 · cited 1×
“Numerous clustering algorithms have been used in many areas such as image processing [17, 18, 19], geophysics [20, 21], customer and marketing analysis [22, 23], crime detection [24], medicine [25, 26] and agriculture [27].”
MethodYousri, N. A., Kamel, M. S., & Ismail, M. A. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2008.08.037 · Cited by 46 · cited 1×
“Many researches are launched in this area to deal with this kind of data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
BackgroundLimwattanapibool, O., & Arch‐int, S. (2017) · Expert Systems · doi:10.1111/exsy.12204 · Cited by 34
DHeat: 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 2×
“labels, which has been used in our previous works [61, 62].”
MethodSelf-citationDeep and fast: Deep learning hashing with semi-supervised graph construction
Song, J., Gao, L., Zou, F., Yan, Y., & Sebe, N. (2016) · Image and Vision Computing · doi:10.1016/j.imavis.2016.02.005 · Cited by 27
A Similarity Model and Segmentation Algorithm for White Matter Fiber Tracts
Mai, S. T., Goebl, S., & Plant, C. (2012) · Proceedings · doi:10.1109/icdm.2012.95 · Cited by 26 · cited 1×
“DBSCAN has a large amount of extensions, e.g. [34, 35, 36, 37], and has been widely applied in many applications, such as astronomy [38], neuroscience [39].”
BackgroundAlgorithms and applications for spatial data mining
Miller, H. J., & Han, J. (2001) · CRC Press eBooks · doi:10.1201/b12382-17 · Cited by 12
Cited by
KNN-BLOCK DBSCAN: Fast Clustering for Large-Scale Data
Chen, Y., Zhou, L., Pei, S., Yu, Z., Chen, Y., Liu, X., Du, J., & Xiong, N. (2021) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2019.2956527 · Cited by 204
“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-citation
Metadata
- Authors
- Chen, Y., Tang, S., Bouguila, N., Wang, C., Du, J., & Li, H.
- Venue
- Pattern Recognition
- Publisher
- Elsevier BV
- Published
- 2018-11
- Volume
- 83
- Pages
- 375-387
- ISSN
- 0031-3203 (ISSN-L)
- OpenAlex
- W2806337402
- Cited by
- 169
- References
- 55
- FWCI
- 11.03
- Type
- journal article
- Language
- en
- Open access
- bronze
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.