DBSCAN Speedup for Time-Serpentine Datasets
References
- M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), AAAI Press, 1996, pp. 226–231. [Online]. Available: https://file.biolab.si/papers/1996-DBSCANKDD.pdf
- R. J. G. B. Campello, D. Moulavi, and J. Sander, “Density-based clustering based on hierarchical density estimates,” in: J. Pei, V. S. Tseng, L. Cao, and H. Motoda (eds.), Advances in Knowledge Discovery and Data Mining, vol. 7819. Springer Berlin Heidelberg, 2013, pp. 160–172. https://doi.org/10.1007/978-3-642-37456-2_14
- J. Sander, Generalized Density-Based Clustering for Spatial Data Mining. München, Herbert Utz Verlag, 1998.
- V. V. Romanuke, “Speedup of the k-means algorithm for partitioning large datasets of flat points by a preliminary partition and selecting initial centroids,” Applied Computer Systems, vol. 28, no. 1, pp. 1–12, Jun. 2023. https://doi.org/10.2478/acss-2023-0001
- E. Schubert, J. Sander, M. Ester, H. P. Kriegel, and X. Xu, “DBSCAN Revisited, revisited: Why and how you should (still) use DBSCAN,” ACM Transactions on Database Systems, vol. 42, no. 3, Jul. 2017, Art. no. 19. https://doi.org/10.1145/3068335
- N. Hanafi and H. Saadatfar, “A fast DBSCAN algorithm for big data based on efficient density calculation,” Expert Systems with Applications, vol. 203, Oct. 2022, Art. no. 117501. https://doi.org/10.1016/j.eswa.2022.117501
- J. Sander, M. Ester, H.-P. Kriegel, and X. Xu, “Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications,” Data Mining and Knowledge Discovery, vol. 2, no. 2, pp. 169–194, Jun. 1998. https://doi.org/10.1023/A:1009745219419
- X. Huang, T. Ma, C. Liu, and S. Liu, “GriT-DBSCAN: A spatial clustering algorithm for very large databases,” Pattern Recognition, vol. 142, Oct. 2023, Art. no. 109658. https://doi.org/10.1016/j.patcog.2023.109658
- S. Pourbahrami, “A neighborhood-based robust clustering algorithm using Apollonius function kernel,” Expert Systems with Applications, vol. 248, Aug. 2024, Art. no. 123407. https://doi.org/10.1016/j.eswa.2024.123407
- J. A. Hartigan and M. A. Wong, “Algorithm AS 136: A k-means clustering algorithm,” Journal of the Royal Statistical Society, Series C, vol. 28, no. 1, pp. 100–108, 1979. https://doi.org/10.2307/2346830
- A. M. Ikotun, A. E. Ezugwu, L. Abualigah, B. Abuhaija, and J. Heming, “K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data,” Information Sciences, vol. 622, pp. 178–210, Apr. 2023. https://doi.org/10.1016/j.ins.2022.11.139
- Z. Wei, Y. Gao, X. Zhang, X. Li, and Z. Han, “Adaptive marine traffic behaviour pattern recognition based on multidimensional dynamic time warping and DBSCAN algorithm,” Expert Systems with Applications, vol. 238, Part E, Mar. 2024, Art. no. 122229. https://doi.org/10.1016/j.eswa.2023.122229
- J. Xie, L. Jiang, S. Xia, X. Xiang, and G. Wang, “An adaptive density clustering approach with multi-granularity fusion,” Information Fusion, vol. 106, 2024, Jun. Art. no. 102273. https://doi.org/10.1016/j.inffus.2024.102273
- B. Ma, C. Yang, A. Li, Y. Chi, and L. Chen, “A faster DBSCAN algorithm based on self-adaptive determination of parameters,” Procedia Computer Science, vol. 221, pp. 113–120, 2023. https://doi.org/10.1016/j.procs.2023.07.017
- Y. Chen, L. Zhou, N. Bouguila, C. Wang, Y. Chen, and J. Du, “BLOCK-DBSCAN: Fast clustering for large scale data,” Pattern Recognition, vol. 109, Jan. 2021, Art. no. 107624. https://doi.org/10.1016/j.patcog.2020.107624
- F. Ros, S. Guillaume, R. Riad, and M. El Hajji, “Detection of natural clusters via S-DBSCAN a self-tuning version of DBSCAN,” Knowledge-Based Systems, vol. 241, Apr. 2022, Art. no. 108288. https://doi.org/10.1016/j.knosys.2022.108288
- D. Luchi, A. L. Rodrigues, and F. M. Varejão, “Sampling approaches for applying DBSCAN to large datasets,” Pattern Recognition Letters, vol. 117, pp. 90–96, 2019. https://doi.org/10.1016/j.patrec.2018.12.010
- N. Newaliya and Y. Singh, “Multivariate hierarchical DBSCAN model for enhanced maritime data analytics,” Data & Knowledge Engineering, vol. 150, Mar. 2024, Art. no. 102282. https://doi.org/10.1016/j.datak.2024.102282
- P. Sadhukhan, L. Halder, and S. Palit, “Approximate DBSCAN on obfuscated data,” Journal of Information Security and Applications, vol. 80, Feb. 2024, Art. no. 103664. https://doi.org/10.1016/j.jisa.2023.103664
- J. Gan and Y. Tao, “DBSCAN revisited: Mis-claim, un-fixability, and approximation,” in Proceedings of the 2015 ACM SIGMOD International Conference on Manage ment of Data, May 2015, pp. 519 –530. https://doi.org/10.1145/2723372.2737792
- T. Boonchoo, X. Ao, Y. Liu, W. Zhao, F. Zhuang, and Q. He, “Grid-based DBSCAN: Indexing and inference,” Pattern Recognition, vol. 90, pp. 271–284, Jun. 2019. https://doi.org/10.1016/j.patcog.2019.01.034
- N. Gholizadeh, H. Saadatfar, and N. Hanafi, “K-DBSCAN: An improved DBSCAN algorithm for big data,” Journal of Supercomputing, vol. 77, no. 6, pp. 6214–6235, June 2021. https://doi.org/10.1007/s11227-020-03524-3
- M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander, “OPTICS: Ordering points to identify the clustering structure,” in ACM SIGMOD International Conference on Management of Data, ACM Press, Jun. 1999, pp. 49–60. https://doi.org/10.1145/304181.304187
- R. J. G. B. Campello, D. Moulavi, A. Zimek, and J. Sander, “A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies,” Data Mining and Knowledge Discovery, vol. 27, no. 3, pp. 344–371, Apr. 2013. https://doi.org/10.1007/s10618-013-0311-4
- M. Al Samara, I. Bennis, A. Abouaissa, and P. Lorenz, “Complete outlier detection and classification framework for WSNs based on OPTICS,” Journal of Network and Computer Applications, vol. 211, Feb. 2023, Art. no. 103563. https://doi.org/10.1016/j.jnca.2022.103563
- J. Wang, Z. Liu, Y. Zhao, Y. Xie, and Y. Xie, “EAST-NBI experimental data processing method based on improved OPTICS algorithm,” Fusion Engineering and Design, vol. 172, Nov. 2021, Art. no. 112737. https://doi.org/10.1016/j.fusengdes.2021.112737
- V. V. Romanuke, “Uniform rectangular array radar optimization for efficient and accurate estimation of target parameters,” Information and Telecommunication Sciences, vol. 13, no. 1, pp. 44–55, 2022. [Online]. Available: http://infotelesc.kpi.ua/article/view/259751/256220
- X. Bai, Z. Xie, X. Xu, and Y. Xiao, “An adaptive threshold fast DBSCAN algorithm with preserved trajectory feature points for vessel trajectory clustering,” Ocean Engineering, vol. 280, Jul. 2023, Art. no. 114930. https://doi.org/10.1016/j.oceaneng.2023.114930
- V. V. Romanuke, “A prototype model for semantic segmentation of curvilinear meandering regions by deconvolutional neural networks,” Applied Computer Systems, vol. 25, no. 1, pp. 62–69, May 2020. https://doi.org/10.2478/acss-2020-0008
- B. Żak and S. Hożyń, “Local image features matching for realtime seabed tracking applications,” Journal of Marine Engineering & Technology, vol. 16, no. 4, pp. 273–282, Oct. 2017. https://doi.org/10.1080/20464177.2017.1386266
- V. V. Romanuke, “Accurate detection of multiple targets by uniform rectangular array radar with threshold soft update and area rescanning,” Information and Telecommunication Sciences, vol. 13, no. 2, pp. 62–71, Dec. 2022. https://doi.org/10.20535/2411-2976.22022.62-71
- V. V. Romanuke, “Optimization of a dataset for a machine learning task by clustering and selecting closest-to-the-centroid objects,” Herald of Khmelnytskyi National University. Technical Sciences, vol. 1, no. 6, pp. 263–265, 2018.
- S. J. Phillips, “Acceleration of K-Means and related clustering algorithms,” in D. M. Mount and C. Stein, Eds., Lecture Notes in Computer Science, vol. 2409, Springer, Jan. 2002, pp. 166–177. https://doi.org/10.1007/3-540-45643-0_13
- V. V. Romanuke, “Parallelization of the traveling salesman problem by clustering its nodes and finding the best route passing through the centroids,” Applied Computer Systems, vol. 28, no. 2, pp. 189–202, Dec. 2023. https://doi.org/10.2478/acss-2023-0019
- C. L. Valenzuela and A. J. Jones, “Evolutionary divide and conquer (I): A novel genetic approach to the TSP,” Evolutionary Computation, vol. 1, no. 4, pp. 313–333, Dec. 1993. https://doi.org/10.1162/evco.1993.1.4.313
- V. V. Romanuke, “Traveling salesman problem parallelization by solving clustered subproblems,” Foundations of Computing and Decision Sciences, vol. 48, no. 4, pp. 453–481, Dec. 2023. https://doi.org/10.2478/fcds-2023-0020
- V. V. Romanuke, “Deep clustering of the traveling salesman problem to parallelize its solution,” Computers & Operations Research, vol. 165, May 2024, Art. no. 106548. https://doi.org/10.1016/j.cor.2024.106548
- T. Gonzalez, “Clustering to minimize the maximum intercluster distance,” Theoretical Computer Science, vol. 38, pp. 293–306, 1985. https://doi.org/10.1016/0304-3975(85)90224-5
- A. Czapiewska, A. Luksza, R. Studanski, and A. Żak, “Reduction of the multipath propagation effect in a hydroacoustic channel using filtration in cepstrum,” Sensors, vol. 20, iss. 3, Jan. 2020, Art. no. 751. https://doi.org/10.3390/s20030751
- Y. Zack, “Cluster analysis for multidimensional objects in fuzzy data conditions,” System research and information technologies, no. 2, pp. 18– 34, Dec. 2021. https://doi.org/10.20535/SRIT.2308-8893.2021.2.02
- G. Grzeczka and M. Klebba, “Automated calibration system for digital multimeters not equipped with a communication interface,” Sensors, 2020, vol. 20, iss. 13, Jun. 2020, Art. no. 3650. https://doi.org/10.3390/s20133650
- J. Zalewski and S. Hożyń, “Computer vision-based position estimation for an autonomous underwater vehicle,” Remote Sensing, vol. 16, iss. 5, Feb. 2024, Art. no. 741. https://doi.org/10.3390/rs16050741
- W. Kaplan, “Maxima and minima with applications: Practical optimization and duality,” in Wiley Series in Discrete Mathematics and Optimization, vol. 51, John Wiley & Sons, 2011, p. 61.
- V. V. Romanuke, “Three-point iterated interval half-cutting for finding all local minima of unknown single-variable function,” Electrical, Control and Communication Engineering, vol. 18, no. 1, pp. 27–36, Jun. 2022. https://doi.org/10.2478/ecce-2022-0004
Language: English
Page range: 14 - 23
Submitted on: Apr 12, 2024
Accepted on: Jul 10, 2024
Published on: Aug 15, 2024
Published by: Riga Technical University
In partnership with: Paradigm Publishing Services
Publication frequency: 1 times per year
Keywords:
Related subjects:
© 2024 Vadim Romanuke, published by Riga Technical University
This work is licensed under the Creative Commons Attribution 4.0 License.