Skip to main content

2016 | OriginalPaper | Buchkapitel

Evaluation of Static/Dynamic Cache for Similarity Search Engines

verfasst von : R. Solar, V. Gil-Costa, M. Marín

Erschienen in: SOFSEM 2016: Theory and Practice of Computer Science

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In large scale search systems, where it is important to achieve a high query throughput, cache strategies are a feasible tool to achieve this goal. A number of efficient cache strategies devised for exact query search in different application domains have been proposed so far. In similarity query search on metric spaces it is necessary to consider additional design requirements devised to produce good quality approximate results from the cache content. In this paper, we propose a Static/Dynamic cache strategy for metric spaces which takes advantage of results of static cache miss operations and their associated distance evaluations for increasing the overall performance of the cache. We present an experimental evaluation of the performance obtained with our strategy for different query selection/replacement strategies.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 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 Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Amato, G., Gennaro, C., Savino, P.: MI-File: using inverted files for scalable approximate similarity search. Multimedia Tools Appl. 71(3), 1333–1362 (2014)CrossRef Amato, G., Gennaro, C., Savino, P.: MI-File: using inverted files for scalable approximate similarity search. Multimedia Tools Appl. 71(3), 1333–1362 (2014)CrossRef
2.
Zurück zum Zitat Bolettieri, P., Esuli, A., Falchi, F., Lucchese, C., Perego, R., Piccioli, T., Rabitti, F.: CoPhIR: a Test Collection for Content-Based Image Retrieval. CoRR, abs/0905.4627v2 (2009). http://cophir.isti.cnr.it Bolettieri, P., Esuli, A., Falchi, F., Lucchese, C., Perego, R., Piccioli, T., Rabitti, F.: CoPhIR: a Test Collection for Content-Based Image Retrieval. CoRR, abs/0905.4627v2 (2009). http://​cophir.​isti.​cnr.​it
3.
Zurück zum Zitat Brisaboa, N.R., Cerdeira-Pena, A., Gil-Costa, V., Marin, M., Pedreira, O.: Efficient similarity search by combining indexing and caching strategies. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 486–497. Springer, Heidelberg (2015) Brisaboa, N.R., Cerdeira-Pena, A., Gil-Costa, V., Marin, M., Pedreira, O.: Efficient similarity search by combining indexing and caching strategies. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 486–497. Springer, Heidelberg (2015)
4.
Zurück zum Zitat Chavez, E., Navarro, G.: An effective clustering algorithm to index high dimensional metric spaces. In: SPIRE, p. 75 (2000) Chavez, E., Navarro, G.: An effective clustering algorithm to index high dimensional metric spaces. In: SPIRE, p. 75 (2000)
5.
Zurück zum Zitat Chierichetti, F., Kumar, R., Vassilvitskii, S.: similarity caching. In: PODS, pp. 127–136 (2009) Chierichetti, F., Kumar, R., Vassilvitskii, S.: similarity caching. In: PODS, pp. 127–136 (2009)
6.
Zurück zum Zitat Esuli, A.: Use of permutation prefixes for efficient and scalable approximate similarity search. IPM J. 48, 889–902 (2012) Esuli, A.: Use of permutation prefixes for efficient and scalable approximate similarity search. IPM J. 48, 889–902 (2012)
7.
Zurück zum Zitat Falchi, F., Lucchese, C., Orlando, S., Perego, R., Rabitti, F.: A metric cache for similarity search. In: LSDS-IR, pp. 43–50 (2008) Falchi, F., Lucchese, C., Orlando, S., Perego, R., Rabitti, F.: A metric cache for similarity search. In: LSDS-IR, pp. 43–50 (2008)
8.
Zurück zum Zitat Falchi, F., Lucchese, C., Orlando, S., Perego, R., Rabitti, F.: Similarity caching in large-scale image retrieval. IPM J. 48, 803–818 (2012) Falchi, F., Lucchese, C., Orlando, S., Perego, R., Rabitti, F.: Similarity caching in large-scale image retrieval. IPM J. 48, 803–818 (2012)
9.
Zurück zum Zitat Gil-Costa, V., Marin, M.: Approximate distributed metric-space search. In: LSDS-IR, pp. 15–20 (2011) Gil-Costa, V., Marin, M.: Approximate distributed metric-space search. In: LSDS-IR, pp. 15–20 (2011)
10.
Zurück zum Zitat Mohamed, H., Marchand-Maillet, S.: Permutation-based pruning for approximate K-NN search. In: Decker, H., Lhotská, L., Link, S., Basl, J., Tjoa, A.M. (eds.) DEXA 2013, Part I. LNCS, vol. 8055, pp. 40–47. Springer, Heidelberg (2013)CrossRef Mohamed, H., Marchand-Maillet, S.: Permutation-based pruning for approximate K-NN search. In: Decker, H., Lhotská, L., Link, S., Basl, J., Tjoa, A.M. (eds.) DEXA 2013, Part I. LNCS, vol. 8055, pp. 40–47. Springer, Heidelberg (2013)CrossRef
11.
Zurück zum Zitat Pandey, S., Broder, A., Chierichetti, F., Josifovski, V., Kumar, R., Vassilvitskii, S.: Nearest-neighbor caching for content-match applications. In: WWW, pp. 441–450 (2009) Pandey, S., Broder, A., Chierichetti, F., Josifovski, V., Kumar, R., Vassilvitskii, S.: Nearest-neighbor caching for content-match applications. In: WWW, pp. 441–450 (2009)
12.
Zurück zum Zitat Silva, E., Teixeira, T., Teodoro, G., Valle, E.: Large-scale distributed locality-sensitive hashing for general metric data. In: Traina, A.J.M., Traina, Jr., C., Cordeiro, R.L.F. (eds.) SISAP 2014. LNCS, vol. 8821, pp. 82–93. Springer, Heidelberg (2014) Silva, E., Teixeira, T., Teodoro, G., Valle, E.: Large-scale distributed locality-sensitive hashing for general metric data. In: Traina, A.J.M., Traina, Jr., C., Cordeiro, R.L.F. (eds.) SISAP 2014. LNCS, vol. 8821, pp. 82–93. Springer, Heidelberg (2014)
13.
Zurück zum Zitat Skopal, T., Lokoc, J., Bustos, B.: D-Cache: universal distance cache for metric access methods. TKDE 24, 868–881 (2012) Skopal, T., Lokoc, J., Bustos, B.: D-Cache: universal distance cache for metric access methods. TKDE 24, 868–881 (2012)
14.
Zurück zum Zitat Walters-Williams, J., Li, Y.: Comparative study of distance functions for nearest neighbors. In: Advanced Techniques in Computing Sciences and Software Engineering, pp. 79–84 (2010) Walters-Williams, J., Li, Y.: Comparative study of distance functions for nearest neighbors. In: Advanced Techniques in Computing Sciences and Software Engineering, pp. 79–84 (2010)
Metadaten
Titel
Evaluation of Static/Dynamic Cache for Similarity Search Engines
verfasst von
R. Solar
V. Gil-Costa
M. Marín
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-49192-8_50