DBSCAN-MS: Distributed Density-Based Clustering in Metric Spaces
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1346-1357
Abstract
DBSCAN is one of important density-based clustering methods, which has a wide range of applications in machine learning and data mining, to name but a few. However, the rapid growing volume and variety of data nowadays challenges traditional DBSCAN, and thus, distributed DBSCAN in metric spaces is required. In this paper, we propose DBSCAN-MS, a distributed density-based clustering in metric spaces. To ensure load balancing, we present a k-d tree based partitioning approach. It utilizes pivots to map the data in metric spaces to vector spaces, and employs k-d tree partitioning technique to equally divide the data. To avoid unnecessary computation and communication cost, we propose a framework that divides data into partitions, find out local DBSCAN result, and merge local result based on a merging graph. In addition, the pivot filtering and the sliding window techniques are also used in the framework for pruning. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and scalability of our proposed DBSCAN-MS.Keywords
This publication has 24 references indexed in Scilit:
- MR-DBSCAN: a scalable MapReduce-based DBSCAN algorithm for heavily skewed dataFrontiers of Computer Science, 2013
- ST-DBSCAN: An algorithm for clustering spatial–temporal dataData & Knowledge Engineering, 2007
- Approximate Similarity Search2006
- Survey of Clustering AlgorithmsIEEE Transactions on Neural Networks, 2005
- Biclustering algorithms for biological data analysis: a surveyIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- Scalable Density-Based Distributed Clustering2004
- Similarity Join in Metric Spaces Using eD-Index2003
- A comparison of clustering algorithms applied to color image quantizationPattern Recognition Letters, 1997
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973