Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing
This work addresses speed bottlenecks in kNN for handling large-scale data, representing an incremental improvement by combining existing techniques like granular-balls and HNSW with quantization.
The paper tackles the high time complexity of k-Nearest Neighbors (kNN) algorithms for large datasets by proposing GB-QkNN, which uses granular-balls to reduce data size and quantizes HNSW for faster distance calculations, resulting in significantly reduced time complexity as shown in analysis.
High time complexity is one of the biggest challenges faced by $k$-Nearest Neighbors ($k$NN). Although current classical and quantum $k$NN 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 $k$NN(GB-Q$k$NN). 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 $k$NN-like algorithms, as revealed by a comprehensive complexity analysis.