EI-LSH: An early-termination driven I/O efficient incremental c-approximate nearest neighbor search | springerprofessional.de Skip to main content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: The VLDB Journal 2/2021

30.09.2020 | Regular Paper

EI-LSH: An early-termination driven I/O efficient incremental c-approximate nearest neighbor search

verfasst von: Wanqi Liu, Hanchen Wang, Ying Zhang, Wei Wang, Lu Qin, Xuemin Lin

Erschienen in: The VLDB Journal | Ausgabe 2/2021

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

Nearest neighbor in high-dimensional space has been widely used in various fields such as databases, data mining and machine learning. The problem has been well solved in low-dimensional space. However, when it comes to high-dimensional space, due to the curse of dimensionality, the problem is challenging. As a trade-off between accuracy and efficiency, c-approximate nearest neighbor (c-ANN) is considered instead of an exact NN search in high-dimensional space. A variety of c-ANN algorithms have been proposed, one of the important schemes for the c-ANN problem is called Locality-sensitive hashing (LSH), which projects a high-dimensional dataset into a low-dimensional dataset and can return a c-ANN with a constant probability. In this paper, we propose a new aggressive early-termination (ET) condition which stops the algorithm with LSH scheme earlier under the same theoretical guarantee, leading to a smaller I/O cost and less running time. Unlike the “conservative” early termination conditions used in previous studies, we propose an “aggressive” early termination condition which can stop much earlier. Though it is not absolutely safe and may result in the probability of failure, we can still devise more efficient algorithms under the same theoretical guarantee by carefully considering the failure probabilities brought by LSH scheme and early termination. Furthermore, we also introduce an incremental searching strategy. Unlike the previous LSH methods, which expand the bucket width in an exponential way, we employ a more natural search strategy to incrementally access the hash values of the objects. We also provide a rigorous theoretical analysis to underpin our incremental search strategy and the new early termination technique. Our comprehensive experiment results show that, compared with the state-of-the-art I/O efficient c-ANN techniques, our proposed algorithm, namely EI-LSH, can achieve much better I/O efficiency under the same theoretical guarantee.

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe



 


Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko





Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

Fußnoten
1
Note that each entry takes 8 bytes for one hash value and the object ID.
 
2
Here, it is not necessary that the instance belongs to A.
 
Literatur
1.
Zurück zum Zitat 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–919 (2018) CrossRef 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–919 (2018) CrossRef
2.
Zurück zum Zitat 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–2178. ACM, New York (2012) 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–2178. ACM, New York (2012)
3.
Zurück zum Zitat 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–15 September 2006, pp. 475–486. ACM, New York (2006) 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–15 September 2006, pp. 475–486. ACM, New York (2006)
5.
Zurück zum Zitat 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—International Conference, ICAIC 2011, Xi’an, China, 20–21 August 2011, Proceedings, Part I, Communications in Computer and Information Science, vol. 224, pp. 38–45. Springer, Berlin (2011) 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—International Conference, ICAIC 2011, Xi’an, China, 20–21 August 2011, Proceedings, Part I, Communications in Computer and Information Science, vol. 224, pp. 38–45. Springer, Berlin (2011)
6.
Zurück zum Zitat 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–262. ACM, New York (2004) 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–262. ACM, New York (2004)
7.
Zurück zum Zitat 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–29 March 2008, ACM International Conference Proceeding Series, vol. 261, pp. 356–367. ACM, New York (2008) 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–29 March 2008, ACM International Conference Proceeding Series, vol. 261, pp. 356–367. ACM, New York (2008)
8.
Zurück zum Zitat Dong, W., Charikar, M., Li, K: Efficient k-nearest neighbor graph construction for generic similarity measures. In: WWW (2011) Dong, W., Charikar, M., Li, K: Efficient k-nearest neighbor graph construction for generic similarity measures. In: WWW (2011)
9.
Zurück zum Zitat Fagin, R.: Combining fuzzy information: an overview. SIGMOD Rec. 31(2), 109–118 (2002) CrossRef Fagin, R.: Combining fuzzy information: an overview. SIGMOD Rec. 31(2), 109–118 (2002) CrossRef
10.
Zurück zum Zitat Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4), 614–656 (2003) MathSciNetCrossRef Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4), 614–656 (2003) MathSciNetCrossRef
11.
Zurück zum Zitat 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–552. ACM, New York (2012) 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–552. ACM, New York (2012)
12.
Zurück zum Zitat 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–1138. ACM, New York (2014) 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–1138. ACM, New York (2014)
13.
Zurück zum Zitat 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) 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)
14.
Zurück zum Zitat Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: ACM SIGKDD, pp. 855–864 (2016) Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: ACM SIGKDD, pp. 855–864 (2016)
15.
Zurück zum Zitat 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–1 (2018) 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–1 (2018)
16.
Zurück zum Zitat 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–755. ACM, New York (2009) 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–755. ACM, New York (2009)
17.
Zurück zum Zitat Holland, S.M.: Principal components analysis (PCA). Department of Geology, University of Georgia, Athens, GA, pp. 30602–2501 (2008) Holland, S.M.: Principal components analysis (PCA). Department of Geology, University of Georgia, Athens, GA, pp. 30602–2501 (2008)
18.
Zurück zum Zitat 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–12 (2015) CrossRef 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–12 (2015) CrossRef
19.
Zurück zum Zitat 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–613 (1998) 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–613 (1998)
20.
Zurück zum Zitat Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011) CrossRef Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011) CrossRef
22.
Zurück zum Zitat Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1097–1105 (2012) Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1097–1105 (2012)
23.
Zurück zum Zitat 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–231. ACM, New York (2009) 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–231. ACM, New York (2009)
24.
Zurück zum Zitat Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement (v1.0). CoRR (2016). arXiv:​1610.​02455 Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement (v1.0). CoRR (2016). arXiv:​1610.​02455
25.
Zurück zum Zitat 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–1673. IEEE (2019) 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–1673. IEEE (2019)
26.
Zurück zum Zitat Liu, Y., Cheng, H., Cui, J.: PQBF: i/o-efficient approximate nearest neighbor search by product quantization. In: CIKM, pp. 667–676 (2017) Liu, Y., Cheng, H., Cui, J.: PQBF: i/o-efficient approximate nearest neighbor search by product quantization. In: CIKM, pp. 667–676 (2017)
27.
Zurück zum Zitat 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–756 (2014) CrossRef 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–756 (2014) CrossRef
28.
Zurück zum Zitat 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–961. VLDB Endowment (2007) 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–961. VLDB Endowment (2007)
29.
Zurück zum Zitat Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR (2016) Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR (2016)
30.
Zurück zum Zitat Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans. Pattern Anal. Mach. Intell. 36(11), 2227–2240 (2014) CrossRef Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans. Pattern Anal. Mach. Intell. 36(11), 2227–2240 (2014) CrossRef
31.
Zurück zum Zitat 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–389. IEEE (2012) 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–389. IEEE (2012)
32.
Zurück zum Zitat 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–1195 (2006) 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–1195 (2006)
33.
Zurück zum Zitat Park, Y., Cafarella, M.J., Mozafari, B.: Neighbor-sensitive hashing. PVLDB 9(3), 144–155 (2015) Park, Y., Cafarella, M.J., Mozafari, B.: Neighbor-sensitive hashing. PVLDB 9(3), 144–155 (2015)
34.
Zurück zum Zitat Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: ACM SIGKDD, pp. 701–710 (2014) Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: ACM SIGKDD, pp. 701–710 (2014)
35.
Zurück zum Zitat 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–31 October 2007, Proceedings, Lecture Notes in Computer Science, vol. 4726, pp. 287–299. Springer, Berlin (2007) 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–31 October 2007, Proceedings, Lecture Notes in Computer Science, vol. 4726, pp. 287–299. Springer, Berlin (2007)
36.
Zurück zum Zitat Silpa-Anan, C., Hartley, R.I.: Optimised kd-trees for fast image descriptor matching. In: CVPR (2008) Silpa-Anan, C., Hartley, R.I.: Optimised kd-trees for fast image descriptor matching. In: CVPR (2008)
37.
Zurück zum Zitat 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–12 (2014) CrossRef 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–12 (2014) CrossRef
38.
Zurück zum Zitat 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–576. ACM, New York (2009) 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–576. ACM, New York (2009)
39.
Zurück zum Zitat 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–115 (2008) CrossRef 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–115 (2008) CrossRef
40.
Zurück zum Zitat 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–848 (2018) 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–848 (2018)
41.
Zurück zum Zitat 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–790 (2018) CrossRef 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–790 (2018) CrossRef
42.
Zurück zum Zitat 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 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
43.
Zurück zum Zitat Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: NIPS, pp. 1753–1760 (2008) Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing. In: NIPS, pp. 1753–1760 (2008)
44.
Zurück zum Zitat Zhang, J., Khoram, S., Li, J.: Efficient large-scale approximate nearest neighbor search on OpenCL FPGA. In: CVPR, pp. 4924–4932 (2018) Zhang, J., Khoram, S., Li, J.: Efficient large-scale approximate nearest neighbor search on OpenCL FPGA. In: CVPR, pp. 4924–4932 (2018)
45.
Zurück zum Zitat 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–2037. ACM, New York (2016) 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–2037. ACM, New York (2016)
Metadaten
Titel
EI-LSH: An early-termination driven I/O efficient incremental c-approximate nearest neighbor search
verfasst von
Wanqi Liu
Hanchen Wang
Ying Zhang
Wei Wang
Lu Qin
Xuemin Lin
Publikationsdatum
30.09.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 2/2021
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-020-00635-4

Weitere Artikel der Ausgabe 2/2021

The VLDB Journal 2/2021 Zur Ausgabe

Premium Partner