A Novel Approach for Parallel Document Clustering Using an Enhanced Parallel WAND Algorithm

Abstract

Document clustering is crucial for managing a large textual data available on the Internet, even though it is computationally costly to cluster high dimensional and large datasets. To tackle these obstacles, a widely used information retrieval method called the weighted AND (WAND) algorithm is utilized as an essential stage in a document clustering process to make it more effective. WAND uses an efficient data structure known as an inverted index to determine document scores and ranks, allowing it to extract the topK documents that are most similar to a given query. Owing to its effectiveness, several versions of parallel algorithms have been proposed to enhance it. However, challenges in document clustering increase since it requires retrieving a higher number of topK and processing longer queries. So, in this paper, an enhanced parallel version of the WAND algorithm (PWAND) is proposed. PWAND divides the inverted index into partitions, each is assigned a specific percentage of topK according to its relevance to the given query. Furthermore, a novel PWAND-based Parallel PArtitional Clustering (PWPPAC) approach that combines the parallel execution of clustering stages with PWAND is proposed. Based on the practical results across a variety of datasets, PWAND is a promising method since it produces results that are extremely match to those obtained by WAND, but with a significant speedup, where the maximum recorded speedup is 85.7x on AG-News dataset. Moreover, the results show that employing the PWAND algorithm in the clustering process makes it more efficient, while maintaining accuracy and quality of clustering.