The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates
Abstract
A new density-based clustering algorithm, RNN-DBSCAN, is presented which uses reverse nearest neighbor counts as an estimate of observation density. Clustering is performed using a DBSCAN-like approach based on k nearest neighbor graph traversals through dense observations. RNN-DBSCAN is preferable to the popular density-based clustering algorithm DBSCAN in two aspects. First, problem complexity is reduced to the use of a single parameter (choice of k nearest neighbors), and second, an improved ability for handling large variations in cluster density (heterogeneous density). The superiority of RNN-DBSCAN is demonstrated on several artificial and real-world datasets with respect to prior work on reverse nearest neighbor based clustering approaches (RECORD, IS-DBSCAN, and ISB-DBSCAN) along with DBSCAN and OPTICS. Each of these clustering approaches is described by a common graph-based interpretation wherein clusters of dense observations are defined as connected components, along with a discussion on their computational complexity. Heuristics for RNN-DBSCAN parameter selection are presented, and the effects of k on RNN-DBSCAN clusterings discussed. Additionally, with respect to scalability, an approximate version of RNN-DBSCAN is presented leveraging an existing approximate k nearest neighbor technique.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Scikit-learn: Machine Learning in Python
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Müller, A., Nothman, J., Louppe, G., et al. (2012) · arXiv · doi:10.48550/arxiv.1201.0490 · Cited by 71,016
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 25,387
(1996) · Cited by 20,179
Hubert, L., & Arabie, P. (1985) · Journal of Classification · doi:10.1007/bf01908075 · Cited by 8,219
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
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
Ankerst, M. (1999) · doi:10.1145/304181.304187 · Cited by 3,982
Density-Based Clustering Based on Hierarchical Density Estimates
Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-37456-2_14 · Cited by 2,680
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · ACM SIGMOD Record · doi:10.1145/93605.98741 · Cited by 1,424
Density-Based Clustering over an Evolving Data Stream with Noise
Cao, F., Estert, M., Qian, W., & Zhou, A. (2006) · Proceedings of the 2006 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.29 · Cited by 1,016
SCAN: a structural clustering algorithm for networks
Xu, X., Yuruk, N., Feng, Z., & Schweiger, T. A. J. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281280 · Cited by 842
Cover 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
Efficient k-nearest neighbor graph construction for generic similarity measures
Dong, W., Moses, C., & Li, K. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963487 · Cited by 673
Texture classification: are filter banks necessary?
Varma, M., & Zisserman, A. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211534 · Cited by 421
Density-Based Clustering Validation
Moulavi, D., Jaskowiak, P. A., Campello, R. J. G. B., Zimek, A., & Sander, J. (2014) · Proceedings of the 2014 SIAM International Conference on Data Mining · doi:10.1137/1.9781611973440.96 · Cited by 275
A local-density based spatial clustering algorithm with noise
Duan, L., Xu, L., Guo, F., Lee, J., & Yan, B. (2007) · Information Systems · doi:10.1016/j.is.2006.10.006 · Cited by 266
Lyon, R. J., Stappers, B. W., Cooper, S., Brooke, J. M., & Knowles, J. D. (2016) · Monthly Notices of the Royal Astronomical Society · doi:10.1093/mnras/stw656 · Cited by 236
DBSCAN 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
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
An efficient and scalable density-based clustering algorithm for datasets with complex structures
Lv, Y., Ma, T., Tang, M., Cao, J., Tian, Y., Al-Dhelaan, A., & Al-Rodhaan, M. (2016) · Neurocomputing · doi:10.1016/j.neucom.2015.05.109 · Cited by 176
A General Approach to Clustering in Large Databases with Noise
Hinneburg, A., & Keim, D. A. (2003) · Knowledge and Information Systems · doi:10.1007/s10115-003-0086-9 · Cited by 157
Enhancing density-based clustering: Parameter reduction and outlier detection
Cassisi, C., Ferro, A., Giugno, R., Pigola, G., & Pulvirenti, A. (2012) · Information Systems · doi:10.1016/j.is.2012.09.001 · Cited by 125
On the Hardness and Approximation of Euclidean DBSCAN
Gan, J., & Tao, Y. (2017) · ACM Transactions on Database Systems · doi:10.1145/3083897 · Cited by 85
Lulli, A., Dell’Amico, M., Pietro Michiardi, A., & Ricci, L. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021932 · Cited by 70
A Simple Yet Effective Data Clustering Algorithm
Vadapalli, S., Valluri, S. R., & Karlapalem, K. (2006) · Proceedings · doi:10.1109/icdm.2006.9 · Cited by 51
Welton, B., Samanas, E., & Miller, B. P. (2013) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/2503210.2503262 · Cited by 44
TOSCA: two-steps clustering algorithm for personal locations detection
Guidotti, R., Trasarti, R., & Nanni, M. (2015) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2820783.2820818 · Cited by 30
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
- Bryant, A., & Cios, K.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2018-06-01
- Volume
- 30
- Issue
- 6
- Pages
- 1109-1121
- ISSN
- 1041-4347 (ISSN-L)
- 1558-2191
- 2326-3865
- OpenAlex
- W2779640815
- Cited by
- 273
- References
- 30
- FWCI
- 10.00
- 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.