Paper reading # 2 ｜基于NVM的高性能向量检索方案HM-ANN

1 .Paper reading # 2 基于NVM的高性能向量检索方案 HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogenous Memory 

2 .Introduction 

3 .Speaker bio Jigao Luo Research Intern • Master Student @ TU Munich • Github: https://github.com/cakebytheoceanLuo • Blog: https://cakebytheoceanluo.github.io/ 

4 .Structure 01 Background 02 HM-ANN 03 Evaluation 04 Summary + Q&A Paper Info Motivation 1B: Build HNSW Build Algorithm 1B: Search HM Search Algorithm 1M: Search Price Comparison 

5 .Background 

6 .Paper Info Jie Ren, PhD @ University of California, Merced: https://jren73.github.io/ Minjia Zhang, Principal Researcher @ Microsoft Research: https://www.microsoft.com/en-us/research/people/minjiaz/ Dong Li, AP @ University of California, Merced: https://faculty.ucmerced.edu/dong-li/ [NeurIPS 2020] 

7 .Intro to HNSW Hierarchical Navigable Small World (HNSW): • similarity graphs • the best-in-class latency-vs-accuracy trade-off • major limitation: memory consuming Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs: https://arxiv.org/abs/1603.09320 

8 .Intel® Optane™ Persistent Memory • Durable as SSD (up to 512GiB per DIMM) • Directly addressable by CPU as DRAM https://www.intel.com/content/www/us/en/products/d ocs/memory-storage/optane-persistent- • Two modes memory/optane-dc-persistent-memory-brief.html • Memory mode without persistence • DRAM as L4 cache • App-direct mode as memory-mapped files • Implementation intensive Memory Hierarchy with PMem in https://software.intel.com/content/www/us/en/develo Memory Mode p/articles/intel-optane-persistent-memory-decision- guide.html 

9 .Heterogeneous Memory HM := DRAM + PMAM • HM := fast memory + slow memory • DRAM := expensive, fast but small capacity • PMem := relative cheap, relative fast and extremely large • PRAM performs in terms of random access latency • ∼80X times faster than SSD • ∼3X slower than DRAM • HM-ANN works in App-direct Mode in billion-scale dataset search. 

10 .HM-ANN 

11 .Motivation of HM-ANN • Goal • indices in DRAM for fast query response • raw uncompressed vector for high accuracy • Reality • Graph-based indexes (e.g. HNSW) needs large amount DRAM. • Compression of vectors drops recall & accuracy • => High Recall, Low Latency, Low Memory Cost in billion scale • HM-ANN: a graph-based similarity search algorithm without compression • with DRAM & PMem => HM • enables billion-scale similarity search with high recall and fast runtime on a single node without compression 

12 .HM-ANN • HM-ANN takes both hardware and data heterogeneity into consideration. • The key idea: • to build high-quality upper layers to take most memory accesses and provide better navigation for search at L0 • to reduce memory accesses in slow memory. 

13 .HM-ANN’s Build 

14 .HM-ANN’s Search 

15 . Price Comparison • Testing bed of the paper • Intel Xeon Gold 6252 CPU@2.3GHz. • DDR4 (96GB) as fast memory and Optane DC PMM (1.5TB) 128GB Optane 256GB Optane 512GB Optane 4*64GB DIMM DIMM DIMM DDR4 DRAM Price $ 1000 $ 2616 $ 8505 $ 12371 Price / GB 7.8125 10.2031 16.6113 48.32 $ / 1.5TiB --- --- $ 25515 $ 74226 #DIMM / 1.5TiB --- --- 3 24 (Full in a rack) https://buy.hpe.com/us/en/options/enterprise-memory/persistent-memory/persistent-memory/intel-optane-persistent-memory-for-hpe/p/1011306266 https://buy.hpe.com/us/en/options/enterprise-memory/enterprise-ddr4-memory/integrity-superdome-ddr4-memory/hpe-integrity-superdome-ddr4-memory/p/1008537056?q=1008537056%3Aname-asc&pageSize=100 https://www.intel.com/content/www/us/en/products/d ocs/memory-storage/optane-persistent- memory/optane-dc-persistent-memory-brief.html 

16 .07 Evaluation 

17 .Evaluation 1B: Build • HNSW takes the shortest time to build the graph. • HM-ANN takes 8% longer time: the bottom-up promotion. • HM-ANN indexes are 5–13% larger than HSNW: high promotion rate from L0 to L1 

18 .Evaluation 1B: Search • top-1 recall of > 95% within 1 ms • top-100 recall of > 90% within 4 ms 

19 .Evaluation 1M: Search • obtaining 46% higher recall under the same search latency 

20 .Summary & Q&A 

21 .Warp up HNSW HM-ANN [Build] Storage Pure in-memory L0 on PMem [Build] # Passes 1 2 [Build] Promotion Rate Low High (L0 to L1) [Build] Promotion Strategy L1 Random High-degree Promotion Strategy [Build] L1 Size & Quality Low High to fullfill DRAM [Search] Strategy in L1 1-greedy search efSearchL1-greedy search [Search] # entry points to L0 1 efSearchL1 > 1 [Search] Tricks from L1 to L0 None Multi-threads, prefetching to DRAM buffer [Search] Where is the majority of seach in the L0 in fast memory, not in L0 

22 .Conclusion • HM-ANN, a hierarchical graph-based similarity search algorithm to leverage emerging heterogeneous memory, aiming to serve extremely large-scale data points on a single node. • => High Recall, Low Latency, Low Memory Cost in billion scale • Releasing full power of heterogeneous memory sometimes requires a co-design of algorithm and system. • HM-ANN maps the hierarchical design of the graph-based ANNs to memory heterogeneity in Optane-based heterogeneous memory. • Combined with a set of system-level techniques, HM-ANN avoids expensive accesses in slow memory without sacrificing accuracy. 

23 .References • HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory: • https://www.microsoft.com/en-us/research/publication/hm-ann-efficient-billion-point-nearest-neighbor-search-on-heterogeneous- memory/ • HM-ANN’s Slide: • http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf • Poster: • http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf 

24 .Thank You https://milvus.io https://github.com/milvus-io/milvus 扫码加入直播交流群 关注 Milvus 视频号 https://twitter.com/milvusio 与讲师实时QA 直播视频早知道