NetSHa: In-Network Acceleration of LSH-Based Distributed Search
Lists
Only you see this
Abstract
Locality Sensitive Hashing (LSH) is widely adopted to index similar data in high-dimensional space for approximate nearest neighbor search. Demanding applications (e.g. web search) mean that LSH must exhibit low response times and high throughput. To achieve this, they tend to load balance between multiple machines. However, as the scale of concurrent queries and the volume of data grow, large numbers of index messages are required. Hence, the network is a key bottleneck. To address this gap, we propose NetSHa, which exploits the computational capacity of programmable switches. Specifically, we introduce a heuristic sort-reduce approach to drop potentially poor candidate answers while preserving search quality. Then, NetSHa aggregates good candidate answers from different index messages when transmitting them. Through this, it reduces the network communication cost. Furthermore, we introduce a best-effort replacement mechanism to improve its concurrency. We implement NetSHa on a Barefoot Tofino programmable switch and evaluate it using 7 real-world datasets. The experimental results show that NetSHa reduces the packet volume by $4\sim 10$ times and improves the search efficiency by least 3× in comparison with typical LSH-based distributed search frameworks.
BibTeX
@article{zhang2022netsha,
author = {Penghao Zhang and Heng Pan and Zhenyu Li and Penglai Cui and Ru Jia and Peng He and Zhibin Zhang and Gareth Tyson and Gaogang Xie},
title = {{NetSHa: In-Network Acceleration of LSH-Based Distributed Search}},
journal = {IEEE Trans. Parallel Distributed Syst.},
year = {2022},
doi = {10.1109/tpds.2021.3135842},
}Loading related content...