Low-time-complexity document clustering using memristive dot product engine

doi:10.1007/s11432-021-3316-x

Low-time-complexity document clustering using memristive dot product engine

2022-01-14

11

PRE

AI

DOI：10.1007/s11432-021-3316-x

Original

Original request for help

Save

Abstract

En 中文

Document clustering has been commonly accepted in the field of data analysis. Nevertheless, the challenging issues for the clustering are the massive similarity measurement operations in the von Neumann architecture which result in huge time consumption. Memristive in-memory computing provides a brand-new path to solve this problem. In this article, utilizing the memristive dot product engine, we demonstrate a cosine similarity accelerated document clustering method for the first time. The memristor-based clustering method lowers the time complexity from O(N center dot d) of the conventional algorithm to O(N) by executing similarity measurement in one step. Focused on the unit-length vectors, an in-situ normalization scheme for the stored vectors in the crossbar array is proposed to provide an efficient hardware training scheme and reduce the normalization steps during the clustering. Utilizing the BBCSport dataset as a benchmark, we further discussed the impact of the non-ideal factors in the memristors, including the available quantized states, the inevitable programming noise, and the device failure. Simulation results indicate that the 6-bit quantized states and 5% programming noise are acceptable for the document clustering tasks. Besides, high resistance states of the failure cells are recommended for higher performance clustering results.

Keywords:

linear-time clustering

cosine similarity

spherical K-means

memristor

in-memory computing

Low-time-complexity document clustering using memristive dot product engine

Abstract

Journal

Organization