中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
NetSHa: In-Network Acceleration of LSH-Based Distributed Search

文献类型：期刊论文

作者Zhang, Penghao1,2; Pan, Heng1,3; Li, Zhenyu1,3; Cui, Penglai1,2; Jia, Ru1,2; He, Peng4; Zhang, Zhibin1; Tyson, Gareth5; Xie, Gaogang6
刊名IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
出版日期2022-09-01
卷号33期号:9页码:2213-2229
关键词Servers Indexes Costs Task analysis Hash functions Concurrent computing Aggregates Local sensitive hashing distributed search in-network computation
ISSN号1045-9219
DOI10.1109/TPDS.2021.3135842
英文摘要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 similar to 10 times and improves the search efficiency by least 3x in comparison with typical LSH-based distributed search frameworks.
资助项目National Key R&D Program of China[2020YFB1805600] ; National Natural Science Foundation of China[61725206] ; National Natural Science Foundation of China[U20A20180] ; National Natural Science Foundation of China[62002344] ; Informatization Plan of Chinese Academy of Sciences[CAS-WX2021SF-0506] ; CAS-Austria Joint Project[171111KYSB20200001]
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:000757848700004
出版者IEEE COMPUTER SOC
源URL[http://119.78.100.204/handle/2XEOYT63/18984]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Li, Zhenyu; Xie, Gaogang
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
3.Purple Mt Labs, Nanjing 211111, Peoples R China
4.ByteDance Inc, Beijing 100089, Peoples R China
5.Queen Mary Univ London, London E1 4NS, England
6.Chinese Acad Sci, Comp Network Informat Ctr, Beijing 100045, Peoples R China
推荐引用方式
GB/T 7714		 Zhang, Penghao,Pan, Heng,Li, Zhenyu,et al. NetSHa: In-Network Acceleration of LSH-Based Distributed Search[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2022,33(9):2213-2229.
APA Zhang, Penghao.,Pan, Heng.,Li, Zhenyu.,Cui, Penglai.,Jia, Ru.,...&Xie, Gaogang.(2022).NetSHa: In-Network Acceleration of LSH-Based Distributed Search.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,33(9),2213-2229.
MLA Zhang, Penghao,et al."NetSHa: In-Network Acceleration of LSH-Based Distributed Search".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 33.9(2022):2213-2229.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。