{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:39Z","timestamp":1779174759956,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T00:00:00Z","timestamp":1601424000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s00778-020-00635-4","type":"journal-article","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T22:37:36Z","timestamp":1601505456000},"page":"215-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["EI-LSH: An early-termination driven I\/O efficient incremental c-approximate nearest neighbor search"],"prefix":"10.1007","volume":"30","author":[{"given":"Wanqi","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3158-9586","authenticated-orcid":false,"given":"Hanchen","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,30]]},"reference":[{"issue":"8","key":"635_CR1","doi-asserted-by":"publisher","first-page":"906","DOI":"10.14778\/3204028.3204034","volume":"11","author":"A Arora","year":"2018","unstructured":"Arora, A., Sinha, S., Kumar, P., Bhattacharya, A.: Hd-index: pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. Proce. VLDB Endow. 11(8), 906\u2013919 (2018)","journal-title":"Proce. VLDB Endow."},{"key":"635_CR2","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Goel, A., Shinde R.: Efficient distributed locality sensitive hashing. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 2174\u20132178. ACM, New York (2012)","DOI":"10.1145\/2396761.2398596"},{"key":"635_CR3","unstructured":"Bast, H., Majumdar, D., Schenkel, R., Theobald, M., Weikum, G.: Io-top-k: index-access optimized top-k query processing. In: Dayal, U., Whang, K., Lomet, D.B., Alonso, G., Lohman, G.M., Kersten, M.L., Cha, S.K., Kim, Y. (eds.) Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, 12\u201315 September 2006, pp. 475\u2013486. ACM, New York (2006)"},{"key":"635_CR4","unstructured":"Bernhardsson,E.: Annoy at github. https:\/\/github.com\/spotify\/annoy (2015)"},{"key":"635_CR5","doi-asserted-by":"crossref","unstructured":"Chen, D., Sun, G., Gong, N.Z., Zhong, X.: Efficient top-k query algorithms using density index. In: Zeng, D. (ed.) Applied Informatics and Communication\u2014International Conference, ICAIC 2011, Xi\u2019an, China, 20\u201321 August 2011, Proceedings, Part I, Communications in Computer and Information Science, vol. 224, pp. 38\u201345. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-23214-5_6"},{"key":"635_CR6","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 253\u2013262. ACM, New York (2004)","DOI":"10.1145\/997817.997857"},{"key":"635_CR7","doi-asserted-by":"crossref","unstructured":"Deshpande, P.M., Padmanabhan, D., Kummamuru, K.: Efficient online top-k retrieval with arbitrary similarity measures. In: Kemper, A., Valduriez, P., Mouaddib, N., Teubner, J., Bouzeghoub, M., Markl, V., Amsaleg, L., Manolescu, I. (eds.) Proceedings of EDBT 2008, 11th International Conference on Extending Database Technology, Nantes, France, 25\u201329 March 2008, ACM International Conference Proceeding Series, vol. 261, pp. 356\u2013367. ACM, New York (2008)","DOI":"10.1145\/1353343.1353388"},{"key":"635_CR8","doi-asserted-by":"crossref","unstructured":"Dong, W., Charikar, M., Li, K: Efficient k-nearest neighbor graph construction for generic similarity measures. In: WWW (2011)","DOI":"10.1145\/1963405.1963487"},{"issue":"2","key":"635_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1145\/565117.565143","volume":"31","author":"R Fagin","year":"2002","unstructured":"Fagin, R.: Combining fuzzy information: an overview. SIGMOD Rec. 31(2), 109\u2013118 (2002)","journal-title":"SIGMOD Rec."},{"issue":"4","key":"635_CR10","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/S0022-0000(03)00026-6","volume":"66","author":"R Fagin","year":"2003","unstructured":"Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4), 614\u2013656 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"635_CR11","doi-asserted-by":"crossref","unstructured":"Gan, J., Feng, J., Fang, Q., Ng, W.: Locality-sensitive hashing scheme based on dynamic collision counting. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 541\u2013552. ACM, New York (2012)","DOI":"10.1145\/2213836.2213898"},{"key":"635_CR12","unstructured":"Gao, J., Jagadish, H.V., Lu, W., Ooi, B.C.: DSH: data sensitive hashing for high-dimensional k-nnsearch. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 1127\u20131138. ACM, New York (2014)"},{"key":"635_CR13","doi-asserted-by":"crossref","unstructured":"Gao, J., Jagadish, H.V., Ooi, B.C., Wang, S.: Selective hashing: closing the gap between radius search and k-nn search. In: SIGKDD (2015)","DOI":"10.1145\/2783258.2783284"},{"key":"635_CR14","doi-asserted-by":"crossref","unstructured":"Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: ACM SIGKDD, pp. 855\u2013864 (2016)","DOI":"10.1145\/2939672.2939754"},{"key":"635_CR15","first-page":"1","volume":"1","author":"Y Gu","year":"2018","unstructured":"Gu, Y., Guo, Y., Song, Y., Zhou, X., Yu, G.: Approximate order-sensitive k-nn queries over correlated high-dimensional data. IEEE Trans. Knowl. Data Eng. 1, 1\u20131 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"635_CR16","doi-asserted-by":"crossref","unstructured":"Haghani, P.,Michel, S., Aberer, K.: Distributed similarity search in high dimensions using locality sensitive hashing. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 744\u2013755. ACM, New York (2009)","DOI":"10.1145\/1516360.1516446"},{"key":"635_CR17","unstructured":"Holland, S.M.: Principal components analysis (PCA). Department of Geology, University of Georgia, Athens, GA, pp. 30602\u20132501 (2008)"},{"issue":"1","key":"635_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.14778\/2850469.2850470","volume":"9","author":"Q Huang","year":"2015","unstructured":"Huang, Q., Feng, J., Zhang, Y., Fang, Q., Ng, W.: Query-aware locality-sensitive hashing for approximate nearest neighbor search. Proc. VLDB Endow. 9(1), 1\u201312 (2015)","journal-title":"Proc. VLDB Endow."},{"key":"635_CR19","doi-asserted-by":"crossref","unstructured":"Indyk, P. Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23-26 May 1998, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"issue":"1","key":"635_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H J\u00e9gou","year":"2011","unstructured":"J\u00e9gou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117\u2013128 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"635_CR21","unstructured":"Johnson, J., Douze, M., J\u00e9gou, H.: Billion-scale similarity search with gpus. CoRR (2017) arXiv:1702.08734"},{"key":"635_CR22","unstructured":"Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1097\u20131105 (2012)"},{"key":"635_CR23","doi-asserted-by":"crossref","unstructured":"Kumar, R., Punera, K., Suel, T., Vassilvitskii, S.: Top-k aggregation using intersections of ranked inputs. In: Baeza-Yates, R., Boldi, P., Ribeiro-Neto, B.A., Cambazoglu, B.B. (eds.) Proceedings of the Second International Conference on Web Search and Web Data Mining, WSDM 2009, Barcelona, Spain, 9-11 February 2009, pp. 222\u2013231. ACM, New York (2009)","DOI":"10.1145\/1498759.1498830"},{"key":"635_CR24","unstructured":"Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement (v1.0). CoRR (2016). arXiv:1610.02455"},{"key":"635_CR25","doi-asserted-by":"crossref","unstructured":"Liu, W., Wang, H., Zhang, Y., Wang, W., Qin, L.: I-lsh: I\/o efficient c-approximate nearest neighbor search in high-dimensional space. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1670\u20131673. IEEE (2019)","DOI":"10.1109\/ICDE.2019.00169"},{"key":"635_CR26","doi-asserted-by":"crossref","unstructured":"Liu, Y., Cheng, H., Cui, J.: PQBF: i\/o-efficient approximate nearest neighbor search by product quantization. In: CIKM, pp. 667\u2013676 (2017)","DOI":"10.1145\/3132847.3132901"},{"issue":"9","key":"635_CR27","doi-asserted-by":"publisher","first-page":"745","DOI":"10.14778\/2732939.2732947","volume":"7","author":"Y Liu","year":"2014","unstructured":"Liu, Y., Cui, J., Huang, Z., Li, H., Shen, H.T.: Sk-lsh: an efficient index structure for approximate nearest neighbor search. Proc. VLDB Endow. 7(9), 745\u2013756 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"635_CR28","unstructured":"Lv, Q., Josephson, W., Wang, Z., Charikar, M., Li, K.: Multi-probe lsh: efficient indexing for high-dimensional similarity search. In: Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 950\u2013961. VLDB Endowment (2007)"},{"key":"635_CR29","unstructured":"Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR (2016)"},{"issue":"11","key":"635_CR30","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans. Pattern Anal. Mach. Intell. 36(11), 2227\u20132240 (2014)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"635_CR31","doi-asserted-by":"crossref","unstructured":"Pan, J., Manocha, D.: Bi-level locality sensitive hashing for k-nearest neighbor computation. In: Data Engineering (ICDE), 2012 IEEE 28th International Conference on, pp. 378\u2013389. IEEE (2012)","DOI":"10.1109\/ICDE.2012.40"},{"key":"635_CR32","doi-asserted-by":"crossref","unstructured":"Panigrahy, R.: Entropy based nearest neighbor search in high dimensions. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, 22-26 January 2006, pp. 1186\u20131195 (2006)","DOI":"10.1145\/1109557.1109688"},{"issue":"3","key":"635_CR33","first-page":"144","volume":"9","author":"Y Park","year":"2015","unstructured":"Park, Y., Cafarella, M.J., Mozafari, B.: Neighbor-sensitive hashing. PVLDB 9(3), 144\u2013155 (2015)","journal-title":"PVLDB"},{"key":"635_CR34","doi-asserted-by":"crossref","unstructured":"Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: ACM SIGKDD, pp. 701\u2013710 (2014)","DOI":"10.1145\/2623330.2623732"},{"key":"635_CR35","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Broschart, A., Hwang, S., Theobald, M., Weikum, G.: Efficient text proximity search. In: Ziviani, N., Baeza-Yates, R.A. (eds.) String Processing and Information Retrieval, 14th International Symposium, SPIRE 2007, Santiago, Chile, 29\u201331 October 2007, Proceedings, Lecture Notes in Computer Science, vol. 4726, pp. 287\u2013299. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-75530-2_26"},{"key":"635_CR36","doi-asserted-by":"crossref","unstructured":"Silpa-Anan, C., Hartley, R.I.: Optimised kd-trees for fast image descriptor matching. In: CVPR (2008)","DOI":"10.1109\/CVPR.2008.4587638"},{"issue":"1","key":"635_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.14778\/2735461.2735462","volume":"8","author":"Y Sun","year":"2014","unstructured":"Sun, Y., Wang, W., Qin, J., Zhang, Y., Lin, X.: SRS: solving c-approximate nearest neighbor queries in high dimensional Euclidean space with a tiny index. Proc. VLDB Endow. 8(1), 1\u201312 (2014)","journal-title":"Proc. VLDB Endow."},{"key":"635_CR38","doi-asserted-by":"crossref","unstructured":"Tao, Y., Yi, K., Sheng, C., Kalnis, P.: Quality and efficiency in high dimensional nearest neighbor search. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 563\u2013576. ACM, New York (2009)","DOI":"10.1145\/1559845.1559905"},{"issue":"1","key":"635_CR39","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00778-007-0072-z","volume":"17","author":"M Theobald","year":"2008","unstructured":"Theobald, M., Bast, H., Majumdar, D., Schenkel, R., Weikum, G.: Topx: efficient and versatile top- k query processing for semistructured data. VLDB J. 17(1), 81\u2013115 (2008)","journal-title":"VLDB J."},{"key":"635_CR40","doi-asserted-by":"crossref","unstructured":"Wang, J., Huang, P.,Zhao, H., Zhang, Z., Zhao, B., Lee, D.L.: Billion-scale commodity embedding for e-commerce recommendation in Alibaba. In: ACM SIGKDD, pp. 839\u2013848 (2018)","DOI":"10.1145\/3219819.3219869"},{"issue":"4","key":"635_CR41","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1109\/TPAMI.2017.2699960","volume":"40","author":"J Wang","year":"2018","unstructured":"Wang, J., Zhang, T., Song, J., Sebe, N., Shen, H.T.: A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell. 40(4), 769\u2013790 (2018)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"635_CR42","doi-asserted-by":"crossref","unstructured":"Wang, Y., Shrivastava, A., Ryu, J.: Flash: randomized algorithms accelerated over CPU-GPU for ultra-high dimensional similarity search (2017). arXiv preprint arXiv:1709.01190","DOI":"10.1145\/3183713.3196925"},{"key":"635_CR43","unstructured":"Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: NIPS, pp. 1753\u20131760 (2008)"},{"key":"635_CR44","doi-asserted-by":"crossref","unstructured":"Zhang, J., Khoram, S., Li, J.: Efficient large-scale approximate nearest neighbor search on OpenCL FPGA. In: CVPR, pp. 4924\u20134932 (2018)","DOI":"10.1109\/CVPR.2018.00517"},{"key":"635_CR45","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Guo, Q., Tung, A.K., Wu, S.: Lazylsh: approximate nearest neighbor search for multiple distance functions with a single index. In: Proceedings of the 2016 International Conference on Management of Data, pp. 2023\u20132037. ACM, New York (2016)","DOI":"10.1145\/2882903.2882930"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00635-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-020-00635-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00635-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T12:40:47Z","timestamp":1669034447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-020-00635-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,30]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["635"],"URL":"https:\/\/doi.org\/10.1007\/s00778-020-00635-4","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,30]]},"assertion":[{"value":"21 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}