Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

High time complexity is one of the biggest challenges faced by k-Nearest Neighbors (kNN). Although current classical and quantum kNN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum kNN(GB-QkNN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the kNN-like algorithms, as revealed by a comprehensive complexity analysis.

Authors

• Shuyin Xia Key Laboratory of Big Data Intelligent Computing Chongqing Key Laboratory of Computational Intelligence Chongqing University of Posts and Telecommunications, Chongqing, China Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education
• Xiaojiang Tian
• Suzhen Yuan
• Jeremiah D. Deng

Keywords

• Machine Learning: ML: Classification
• Machine Learning: ML: Clustering
• Machine Learning: ML: Other
• Search: S: Search and machine learning