A parallel varied density-based clustering algorithm with optimized data partition. Issue 1 (2nd January 2018)

• Record Type: Journal Article
• Authors: Gu, Yuhua; Ye, Xinyue; Zhang, Feng; Du, Zhenhong; Liu, Renyi; Yu, Lifeng
• Is Part Of: Journal of spatial science. Volume 63:Issue 1(2018)
• Page Start: 93
• Page End: 114
• Publication Date: 2018-01-02
• Subjects: Data mining -- varied density-based clustering -- parallel clustering -- data partition -- layered grouping grid-based k nearest neighbour searching; Geographic information systems -- Periodicals; Cartography -- Periodicals; Surveying -- Periodicals; Geodesy -- Periodicals; Photogrammetry -- Periodicals; Cartography; Geodesy; Geographic information systems; Photogrammetry; Surveying; Periodicals; 526.05
• DOI: 10.1080/14498596.2017.1352542
• Languages: English
• ISSNs: 1449-8596

Abstract

Abstract: This paper presents a parallel varied density-based clustering algorithm with optimized data partition (PVDB). First, we improve the partition with reduced boundary points algorithm using shared nearest neighbour (SNN) methods and propose the reachable partition with reduced boundary points algorithm. Second, we introduce a layered grouping grid structure and propose an efficient k nearest neighbour (kNN) search method. This method enhances the efficiency of kNN searches and determines whether kNNs are in their own partitions. Third, we propose a new merging strategy for connecting clusters in different partitions, based on the reachable point concept. Meanwhile, the strategy avoids connecting clusters with varying densities by SNN as occurs with SNN-based clustering methods. Our algorithm is implemented and compared with DBSCAN-MR and GriDBSCAN using the MapReduce paradigm and shows better varied density clustering capability and scalability. In addition, varied applications show our algorithm's capability of discerning spatial patterns and extending to many fields.