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

作　　者：Houji ZHOU Yi LI Xiangshui MIAO 

机构地区：[1]Wuhan National Laboratory for Optoelectronics,School of Optical and Electronic Information,Huazhong University of Science and Technology,Wuhan 430074,China

出　　处：《Science China(Information Sciences)》2022年第2期221-230,共10页中国科学（信息科学）（英文版）

基　　金：supported by National Key Research and Development Plan of MOST of China(Grant No.2019YFB2205100);National Natural Science Foundation of China(Grant Nos.61874164,92064012,61841404);the support of Hubei Key Laboratory for Advanced Memories,Hubei Engineering Research Center on Microelectronics,and Chua Memristor Institute。

摘　　要：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·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.

关 键 词：linear-time clustering cosine similarity spherical K-means MEMRISTOR in-memory computing 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]