ES4D: Accelerating Exact Similarity Search for High-Dimensional Vectors via Vector Slicing and In-SSD Computation
Juhwan Kim, Jongseon Seo, Jong-Hyeok Park, Sangwon Lee, Hongchan Roh, Hyungmin Cho · 2022 IEEE 40th International Conference on Computer Design (ICCD) · 2022
Searching top-k nearest neighbor (kNN) based on the vector similarity is a common problem in many domains. Unlike approximate kNN search, exact kNN needs to check a large portion of the dataset, if not the entire set. When the data volume is large, the dataset cannot fit in the main memory and has to be stored on a storage device such as flash drive. ES4D is a kNN search platform implemented near-data on the solid-state drive (SSD). ES4D accelerates kNN search by using two levels of early termination, using pre-clustering of the dataset vectors and vector sharding. ES4D incorporates several optimization techniques to aid such early terminations. Using near-data processing, ES4D further enhances performance and reduces energy consumption. Performing the kNN search on the SSD side not only improves energy efficiency but also enables ES4D to optimize the physical page placement of dataset vectors on SSD to maximize the search throughput. We evaluated ES4D using various vector datasets. ES4D achieves 1.9× search performance improvement over existing exact kNN search mechanisms. Also, by off-loading the distance calculation to the SSD side, ES4D reduces energy consumption for kNN search by 8.1×.