Title
Improving DBSCANs execution time by using a pruning technique on bit vectors Improving DBSCANs execution time by using a pruning technique on bit vectors
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Pattern recognition letters. - Amsterdam
Volume/pages
32(2011) :13 , p. 1572-1580
ISSN
0167-8655
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Abstract
Clustering is the process of assigning a set of physical or abstract objects into previously unknown groups. The goal of clustering is to group similar objects into the same clusters and dissimilar objects into different clusters. Similarities between objects are evaluated by using the attribute values of objects. There are many clustering algorithms in the literature; among them, DBSCAN is a well known density-based clustering algorithm. We improve DBSCANs execution time performance for binary data sets and Hamming distances. We achieve considerable speed gains by using a novel pruning technique, as well as bit vectors, and binary operations. Our novel method effectively discards distant neighbors of an object and computes only the distances between an object and its possible neighbors. By discarding distant neighbors, we avoid unnecessary distance computations and use less CPU time when compared with the conventional DBSCAN algorithm. However, the accuracy of our method is identical to that of the original DBSCAN. Experimental test results on real and synthetic data sets demonstrate that, by using our pruning technique, we obtain considerably faster execution time results compared to DBSCAN.
E-info
https://repository.uantwerpen.be/docman/iruaauth/130cc0/5f51db1cb4d.pdf