{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:46:26Z","timestamp":1787017586625,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,2,11]]},"DOI":"10.1145\/3488560.3498425","type":"proceedings-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T16:42:57Z","timestamp":1644943377000},"page":"1395-1405","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["GraSP"],"prefix":"10.1145","author":[{"given":"Minjia","family":"Zhang","sequence":"first","affiliation":[{"name":"Microsoft, Bellevue, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenhan","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft, Bellevue, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuxiong","family":"He","sequence":"additional","affiliation":[{"name":"Microsoft, Bellevue, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM","author":"Andoni Alexandr","year":"2008","unstructured":"Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM (2008)."},{"key":"e_1_3_2_2_2_1","volume-title":"Practical and Optimal LSH for Angular Distance. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015a. Practical and Optimal LSH for Angular Distance. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015. 1225--1233."},{"key":"e_1_3_2_2_3_1","unstructured":"Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya P. Razenshteyn and Ludwig Schmidt. 2015b. Practical and Optimal LSH for Angular Distance. In NeurIPS. 1225--1233."},{"key":"e_1_3_2_2_4_1","volume-title":"Razenshteyn","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Piotr Indyk, and Ilya P. Razenshteyn. 2018. Approximate Nearest Neighbor Search in High Dimensions . CoRR , Vol. abs\/1806.09823 (2018)."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_3_2_2_6_1","volume-title":"Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR 2016 . 2055--2063","author":"Babenko Artem","unstructured":"Artem Babenko and Victor S. Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR 2016 . 2055--2063."},{"key":"e_1_3_2_2_7_1","volume-title":"Towards Similarity Graphs Constructed by Deep Reinforcement Learning. arxiv","author":"Baranchuk Dmitry","year":"1911","unstructured":"Dmitry Baranchuk and Artem Babenko. 2019. Towards Similarity Graphs Constructed by Deep Reinforcement Learning. arxiv: 1911.12122 [cs.LG]"},{"key":"e_1_3_2_2_8_1","volume-title":"Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In ECCV 2018 . 209--224","author":"Baranchuk Dmitry","year":"2018","unstructured":"Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In ECCV 2018 . 209--224."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_2_11_1","volume-title":"Steven H Strogatz, and Duncan J Watts.","author":"Callaway Duncan S","year":"2000","unstructured":"Duncan S Callaway, Mark EJ Newman, Steven H Strogatz, and Duncan J Watts. 2000. Network robustness and fragility: Percolation on random graphs . Physical review letters , Vol. 85, 25 (2000), 5468."},{"key":"e_1_3_2_2_12_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search.","author":"Chen Qi","year":"2018","unstructured":"Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2959100.2959190"},{"key":"e_1_3_2_2_14_1","volume-title":"Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character","volume":"112","author":"Maurice Dirac Paul Adrien","year":"1926","unstructured":"Paul Adrien Maurice Dirac. 1926. On the theory of quantum mechanics . Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character , Vol. 112, 762 (1926), 661--677."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1646396.1646421"},{"key":"e_1_3_2_2_16_1","volume-title":"Link and Code: Fast Indexing With Graphs and Compact Regression Codes. In CVPR","author":"Douze Matthijs","year":"2018","unstructured":"Matthijs Douze, Alexandre Sablayrolles, and Herv\u00e9 J\u00e9 gou. 2018. Link and Code: Fast Indexing With Graphs and Compact Regression Codes. In CVPR 2018."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368303"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486014"},{"key":"e_1_3_2_2_19_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph . CoRR","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph . CoRR , Vol. abs\/1609.07228 (2016)."},{"key":"e_1_3_2_2_20_1","volume-title":"2019 a. Satellite System Graph: Towards the Efficiency Up-Boundary of Graph-Based Approximate Nearest Neighbor Search. CoRR","author":"Fu Cong","year":"2019","unstructured":"Cong Fu, Changxu Wang, and Deng Cai. 2019 a. Satellite System Graph: Towards the Efficiency Up-Boundary of Graph-Based Approximate Nearest Neighbor Search. CoRR , Vol. abs\/1907.06146 (2019)."},{"key":"e_1_3_2_2_21_1","volume-title":"Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. In VLDB'19 .","author":"Fu Cong","year":"2019","unstructured":"Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019 b. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. In VLDB'19 ."},{"key":"e_1_3_2_2_22_1","volume-title":"Distilling the Knowledge in a Neural Network. CoRR","author":"Hinton Geoffrey E.","year":"2015","unstructured":"Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. 2015. Distilling the Knowledge in a Neural Network. CoRR , Vol. abs\/1503.02531 (2015)."},{"key":"e_1_3_2_2_23_1","volume-title":"Product Quantization for Nearest Neighbor Search. In TPAMI 2011 .","author":"Jegou Herve","year":"2011","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. In TPAMI 2011 ."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_3_2_2_25_1","volume-title":"Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR 2014 .","author":"Kalantidis Yannis","unstructured":"Yannis Kalantidis and Yannis S. Avrithis. 2014. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR 2014 ."},{"key":"e_1_3_2_2_26_1","volume-title":"Distributed Representations of Sentences and Documents. In ICML 2014","volume":"32","author":"Quoc","unstructured":"Quoc V. Le and Tom\u00e1 s Mikolov. 2014. Distributed Representations of Sentences and Documents. In ICML 2014 , Vol. 32. JMLR.org, 1188--1196."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263763"},{"key":"e_1_3_2_2_28_1","volume-title":"Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement","author":"Li Wen","year":"2019","unstructured":"Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Wenjie Zhang, and Xuemin Lin. 2019. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement . IEEE Transactions on Knowledge and Data Engineering (2019)."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000029664.99615.94"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_3_2_2_31_1","volume-title":"Growing homophilic networks are natural optimal navigable small worlds. CoRR","author":"Malkov Yury A.","year":"2015","unstructured":"Yury A. Malkov. 2015. Growing homophilic networks are natural optimal navigable small worlds. CoRR , Vol. abs\/1507.06529 (2015)."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_3_2_2_33_1","volume-title":"Efficient Estimation of Word Representations in Vector Space. In ICLR 2013 , , Yoshua Bengio and Yann LeCun (Eds.).","author":"Mikolov Tom\u00e1","year":"2013","unstructured":"Tom\u00e1 s Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. In ICLR 2013 , , Yoshua Bengio and Yann LeCun (Eds.)."},{"key":"e_1_3_2_2_34_1","volume-title":"Nitesh V. Chawla, and Francisco Herrera.","author":"Moreno-Torres Jose G.","year":"2012","unstructured":"Jose G. Moreno-Torres, Troy Raeder, Roc'i o Ala'i z-Rodr'i guez, Nitesh V. Chawla, and Francisco Herrera. 2012. A unifying view on dataset shift in classification. Pattern Recognit. (2012), 521--530."},{"key":"e_1_3_2_2_35_1","volume-title":"TPAMI 2014","volume":"36","author":"Muja Marius","year":"2014","unstructured":"Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data . TPAMI 2014 , Vol. 36, 11 (2014), 2227--2240."},{"key":"e_1_3_2_2_36_1","volume-title":"Semantic Product Search. In KDD 2019 , , Ankur Teredesai, Vipin Kumar, Ying Li, R\u00f3 mer Rosales, Evimaria Terzi, and George Karypis (Eds.). ACM, 2876--2885","author":"Nigam Priyanka","year":"2019","unstructured":"Priyanka Nigam, Yiwei Song, Vijai Mohan, Vihan Lakshman, Weitian Allen Ding, Ankit Shingavi, Choon Hui Teo, Hao Gu, and Bing Yin. 2019 a. Semantic Product Search. In KDD 2019 , , Ankur Teredesai, Vipin Kumar, Ying Li, R\u00f3 mer Rosales, Evimaria Terzi, and George Karypis (Eds.). ACM, 2876--2885."},{"key":"e_1_3_2_2_37_1","volume-title":"Semantic Product Search. In KDD 2019 , , Ankur Teredesai, Vipin Kumar, Ying Li, R\u00f3 mer Rosales, Evimaria Terzi, and George Karypis (Eds.). ACM, 2876--2885","author":"Nigam Priyanka","year":"2019","unstructured":"Priyanka Nigam, Yiwei Song, Vijai Mohan, Vihan Lakshman, Weitian Allen Ding, Ankit Shingavi, Choon Hui Teo, Hao Gu, and Bing Yin. 2019 b. Semantic Product Search. In KDD 2019 , , Ankur Teredesai, Vipin Kumar, Ying Li, R\u00f3 mer Rosales, Evimaria Terzi, and George Karypis (Eds.). ACM, 2876--2885."},{"key":"e_1_3_2_2_38_1","volume-title":"Cartesian K-Means. In CVPR 2013 .","author":"Norouzi Mohammad","unstructured":"Mohammad Norouzi and David J. Fleet. 2013. Cartesian K-Means. In CVPR 2013 ."},{"key":"e_1_3_2_2_39_1","volume-title":"Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems","author":"Norouzi Mohammad","year":"2012","unstructured":"Mohammad Norouzi, David J. Fleet, and Ruslan Salakhutdinov. 2012. Hamming Distance Metric Learning. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3--6, 2012, Lake Tahoe, Nevada, United States. 1070--1078."},{"key":"e_1_3_2_2_40_1","volume-title":"Manning","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation . In EMNLP. 1532--1543."},{"key":"e_1_3_2_2_41_1","volume-title":"Web Pages and Wikipedia Concepts. In WSDM '14","author":"Ren Xiang","year":"2014","unstructured":"Xiang Ren, Yujing Wang, Xiao Yu, Jun Yan, Zheng Chen, and Jiawei Han. 2014. Heterogeneous Graph-based Intent Learning with Queries, Web Pages and Wikipedia Concepts. In WSDM '14 (New York, New York, USA). 23--32."},{"key":"e_1_3_2_2_42_1","volume-title":"Herrmann","author":"Schneider Christian M.","year":"2011","unstructured":"Christian M. Schneider, Andr\u00e9 A. Moreira, Jos\u00e9 S. Andrade Jr., Shlomo Havlin, and Hans J. Herrmann. 2011. Mitigation of Malicious Attacks on Networks. CoRR , Vol. abs\/1103.1741 (2011). arxiv: 1103.1741"},{"key":"e_1_3_2_2_43_1","volume-title":"Very deep convolutional networks for large-scale image recognition . arXiv preprint arXiv:1409.1556","author":"Simonyan Karen","year":"2014","unstructured":"Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition . arXiv preprint arXiv:1409.1556 (2014)."},{"key":"e_1_3_2_2_44_1","volume-title":"Ravishankar Krishnawamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS . 13748--13758."},{"key":"e_1_3_2_2_45_1","volume-title":"FAQ: All about the Google RankBrain algorithm. https:\/\/searchengineland.com\/faq-all-about-the-new-google-rankbrain-algorithm-234440 .","author":"Sullivan Danny","year":"2018","unstructured":"Danny Sullivan. 2018. FAQ: All about the Google RankBrain algorithm. https:\/\/searchengineland.com\/faq-all-about-the-new-google-rankbrain-algorithm-234440 ."},{"key":"e_1_3_2_2_46_1","volume-title":"Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. In KDD 2018 . 839--848","author":"Wang Jizhe","year":"2018","unstructured":"Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. 2018. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. In KDD 2018 . 839--848."},{"key":"e_1_3_2_2_47_1","volume-title":"End-to-End Neural Ad-hoc Ranking with Kernel Pooling. In SIGIR 2017 . 55--64","author":"Xiong Chenyan","year":"2017","unstructured":"Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. 2017. End-to-End Neural Ad-hoc Ranking with Kernel Pooling. In SIGIR 2017 . 55--64."},{"key":"e_1_3_2_2_48_1","volume-title":"Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In SODA '93","author":"Yianilos Peter N.","year":"1993","unstructured":"Peter N. Yianilos. 1993. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In SODA '93. 311--321."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271800"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00517"},{"key":"e_1_3_2_2_51_1","first-page":"1673","article-title":"GRIP: Multi-Store Capacity-Optimized High-Performance Nearest Neighbor Search for Vector Search Engine","volume":"2019","author":"Zhang Minjia","year":"2019","unstructured":"Minjia Zhang and Yuxiong He. 2019. GRIP: Multi-Store Capacity-Optimized High-Performance Nearest Neighbor Search for Vector Search Engine. In CIKM 2019. 1673--1682.","journal-title":"CIKM"},{"key":"e_1_3_2_2_52_1","volume-title":"Visual Search at Alibaba. CoRR","author":"Zhang Yanhao","year":"2021","unstructured":"Yanhao Zhang, Pan Pan, Yun Zheng, Kang Zhao, Yingya Zhang, Xiaofeng Ren, and Rong Jin. 2021. Visual Search at Alibaba. CoRR , Vol. abs\/2102.04674 (2021). arxiv: 2102.04674"}],"event":{"name":"WSDM '22: The Fifteenth ACM International Conference on Web Search and Data Mining","location":"Virtual Event AZ USA","acronym":"WSDM '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488560.3498425","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488560.3498425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:18:51Z","timestamp":1750177131000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488560.3498425"}},"subtitle":["Optimizing Graph-based Nearest Neighbor Search with Subgraph Sampling and Pruning"],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":52,"alternative-id":["10.1145\/3488560.3498425","10.1145\/3488560"],"URL":"https:\/\/doi.org\/10.1145\/3488560.3498425","relation":{},"subject":[],"published":{"date-parts":[[2022,2,11]]},"assertion":[{"value":"2022-02-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}