BiMass: An approximate batch-incremental clustering using mass-based dissimilarity

Abstract Usage of non-incremental clustering algorithms for dynamic data may lead towards issues such as increased consumption of resources, higher latency and greater execution time. To address such bottlenecks, these algorithms need to be transformed into intelligent algorithms capable of processing the continuously changing data. MBSCAN is a robust non-incremental clustering algorithm that leverages the idea of data dependent dissimilarity to find clusters. An incremental version of MBSCAN viz. iMass was designed to handle single point insertions. However, with increase in number of updates, the iMass algorithm gradually loses its efficiency over MBSCAN due to repeated singular insertions on a larger dataset. We propose an alternative approximate incremental extension to MBSCAN known as BiMass (Batch incremental mass-based clustering to overcome such issues. Our BiMass algorithm facilitates addition of points in batch-mode while building the expensive components of MBSCAN incrementally. Experiments on real world and synthetic datasets showed that our BiMass algorithm achieved a maximum efficiency of around 5.77x over MBSCAN and 2.16x over iMass respectively at a cost of about 7.07% and 13.82% mean memory overhead.