{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:49:42Z","timestamp":1776350982511,"version":"3.51.2"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T00:00:00Z","timestamp":1638230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National NSF of China","award":["61872234, 61732010 and 61525204"],"award-info":[{"award-number":["61872234, 61732010 and 61525204"]}]},{"name":"Shanghai Key Laboratory of Scalable Computing and Systems"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2021,11,30]]},"abstract":"<jats:p>Approximate nearest neighbor search is a classical problem in data science, which is widely applied in many fields. With the rapid growth of data in the real world, it becomes more and more important to speed up the nearest neighbor search process. Satellite System Graph (SSG) is one of the state-of-the-art methods to solve the problem. However, with the further increase of the data scale of problems, SSG still needs a considerable amount of time to finish the search due to the limitation of step length and start point locations. To solve the problem, we propose Hierarchical Satellite System Graph (HSSG) and present its index algorithm and search algorithm. The index process can be distributed deployed due to the good parallelism of our designed hierarchical structure. The theoretical analysis reveals that HSSG decreases the search steps and reduces the computational cost and reduces the search time by searching on the hierarchical structure with a similar indexing time compared with SSG, hence reaches a better search efficiency. The experiments on multiple datasets present that HSSG reduces the distance computations, accelerates the search process, and increases the search precision in the real tasks, especially under the tasks with large scale and crowded distributions, which presents a good application prospect of HSSG.<\/jats:p>","DOI":"10.1145\/3488377","type":"journal-article","created":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T09:01:36Z","timestamp":1643878896000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hierarchical Satellite System Graph for Approximate Nearest Neighbor Search on Big Data"],"prefix":"10.1145","volume":"2","author":[{"given":"Jiaru","family":"Zhang","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruhui","family":"Ma","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Song","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Hua","sequence":"additional","affiliation":[{"name":"Queen\u2019s University Belfast, Belfast Northern Ireland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhengui","family":"Xue","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyang","family":"Guan","sequence":"additional","affiliation":[{"name":"Jiangnan University, Wuxi, Jiangsu, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haibing","family":"Guan","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, P.R.China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,2,3]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_3_1_3_2","article-title":"Exploring the limits of transfer learning with a unified text-to-text transformer","volume":"21","author":"Raffel Colin","year":"2020","unstructured":"Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res. 21 (2020), 140:1\u2013140:67.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2953897"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656397"},{"key":"e_1_3_1_10_2","article-title":"Efanna: An extremely fast approximate nearest neighbor search algorithm based on KNN graph","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. arXiv preprint arXiv:1609.07228 (2016).","journal-title":"arXiv preprint arXiv:1609.07228"},{"key":"e_1_3_1_11_2","article-title":"Satellite system graph: Towards the efficiency up-boundary of graph-based approximate nearest neighbor search","author":"Fu Cong","year":"2019","unstructured":"Cong Fu, Changxu Wang, and Deng Cai. 2019. Satellite system graph: Towards the efficiency up-boundary of graph-based approximate nearest neighbor search. arXiv preprint arXiv:1907.06146.","journal-title":"arXiv preprint arXiv:1907.06146"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283615"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/2984093.2984211"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00977785"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00032"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/348.318586"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1162"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2981780.2981999"},{"issue":"8","key":"e_1_3_1_30_2","first-page":"2018","article-title":"C-approximate nearest neighbor query algorithm based on learning for high-dimensional data","volume":"23","author":"Yuan Pei-Sen","year":"2012","unstructured":"Pei-Sen Yuan, Chao-Feng Sha, Xiao-Ling Wang, and Ao-Ying Zhou. 2012. C-approximate nearest neighbor query algorithm based on learning for high-dimensional data. Ruanjian Xuebao\/J. Softw. 23, 8 (2012), 2018\u20132031.","journal-title":"Ruanjian Xuebao\/J. Softw."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00094"}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488377","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:55:32Z","timestamp":1776347732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,30]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,11,30]]}},"alternative-id":["10.1145\/3488377"],"URL":"https:\/\/doi.org\/10.1145\/3488377","relation":{},"ISSN":["2691-1922"],"issn-type":[{"value":"2691-1922","type":"print"}],"subject":[],"published":{"date-parts":[[2021,11,30]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}