Top

The Journal of Supercomputing

Published in:

07-12-2017

A graph-based cache for large-scale similarity search engines

Authors: Veronica Gil-Costa, Mauricio Marin, Carolina Bonacic, Roberto Solar

Published in: The Journal of Supercomputing | Issue 5/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Large-scale similarity search engines are complex systems devised to process unstructured data like images and videos. These systems are deployed on clusters of distributed processors communicated through high-speed networks. To process a new query, a distance function is evaluated between the query and the objects stored in the database. This process relays on a metric space index distributed among the processors. In this paper, we propose a cache-based strategy devised to reduce the number of computations required to retrieve the top-k object results for user queries by using pre-computed information. Our proposal executes an approximate similarity search algorithm, which takes advantage of the links between objects stored in the cache memory. Those links form a graph of similarity among pre-computed queries. Compared to the previous methods in the literature, the proposed approach reduces the number of distance evaluations up to 60%.

previous article A full adder structure without cross-wiring in quantum-dot cellular automata with energy dissipation analysis

next article Data deduplication techniques for efficient cloud storage management: a systematic review

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Memcached: https://memcached.org.

Redis: http://redis.io.

http://lucene.apache.org.

Al-Fares M, Loukissas A, Vahdat A (2008) A scalable, commodity data center network architecture. SIGCOMM Comput Commun Rev 38(4):63–74CrossRef

Amato G, Esuli A, Falchi F (2013) Pivot selection strategies for permutation-based similarity search. In: SISAP, pp 91–102

Amato G, Esuli A, Falchi E (2015) A comparison of pivot selection techniques for permutation-based indexing. J Inf Syst 52(C):176–188CrossRef

Amato G, Savino P (2008) Approximate similarity search in metric spaces using inverted files. In: InfoScale, pp 28:1–28:10

Andoni A, Indyk P (2008) Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. J Commun ACM 51(1):117–122CrossRef

Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY (1998) An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J ACM 45(6):891–923MathSciNetCrossRefMATH

Baeza-Yates R, Ribeiro-Neto B (2011) Modern information retrieval, 2nd edn. Addison-Wesley Publishing Company, Reading

Brisaboa NR, Cerdeira-Pena A, Gil-Costa V, Marín M, Pedreira O (2015) Efficient similarity search by combining indexing and caching strategies. In: SOFSEM, pp 486–497

Burkhard WA, Keller RM (1973) Some approaches to best-match file searching. J Commun ACM 4(16):230–236CrossRefMATH

10.

Bustos B, Navarro G, Chávez E (2003) Pivot selection techniques for proximity searching in metric spaces. J Pattern Recognit Lett 24(14):2357–2366CrossRefMATH

11.

Bustos B, Pedreira O, Brisaboa N (2008) A dynamic pivot selection technique for similarity search. In: SISAP, pp 394–401

12.

Cao W, Sahin S, Liu L, Bao X (2016) Evaluation and analysis of in-memory key-value systems. In: BigData, pp 26–33

13.

Chávez E, Figueroa K, Navarro G (2008) Effective proximity retrieval by ordering permutations. J Pattern Anal Manag Intell 30:1647–1658CrossRef

14.

Chávez E, Ludueña V, Reyes N, Roggero P (2016) Faster proximity searching with the distal SAT. J Inf Syst 59:15–47CrossRef

15.

Chávez E, Marroquin J, Navarro G (2001) Fixed queries array: a fast and economical data structure for proximity searching. J Multimed Tools Appl 14(2):113–135CrossRefMATH

16.

Chávez E, Navarro G (2005) A compact space decomposition for effective metric indexing. J Pattern Recogn Lett 26(9):1363–1376CrossRef

17.

Chierichetti F, Kumar R, Vassilvitskii S (2009) Similarity caching. In: SIGMOD-SIGACT-SIGART, pp 127–136

18.

Ciaccia P, Patella M (2000) PAC nearest neighbor queries: approximate and controlled search in high-dimensional and metric spaces. In: ICDE, pp 244–255

19.

Ciaccia P, Patella M, Zezula P (1997) M-tree: an efficient access method for similarity search in metric spaces. In: VLDB, pp 426–435

20.

Dehne F, Noltemeier H (1988) Voronoi trees and clustering problems. In: Syntactic and structural, pattern recognition, pp 185–194

21.

Egecioglu Ö, Ferhatosmanoglu H, Ogras ÜY (2004) Dimensionality reduction and similarity computation by inner-product approximations. IEEE Trans Knowl Data Eng 16(6):714–726CrossRef

22.

Esuli A (2009) Mipai: using the pp-index to build an efficient and scalable similarity search system. In: SISAP, pp 146–148

23.

Esuli A (2010) Pp-index: using permutation prefixes for efficient and scalable similarity search. In: SEBD, pp 318–325

24.

Falchi F, Lucchese C, Orlando S, Perego R, Rabitti F (2008) A metric cache for similarity search. In: LSDS-IR, pp 43–50

25.

Falchi F, Lucchese C, Orlando S, Perego R, Rabitti F (2009) Caching content-based queries for robust and efficient image retrieval. In: EDBT, pp 780–790

26.

Falchi F, Lucchese C, Orlando S, Perego R, Rabitti F (2011) Similarity caching in large-scale image retrieval. J Inf Process Manag 48(5):803–818

27.

Faloutsos C, Lin K-I (1995) Fastmap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: SIGMOD, pp 163–174

28.

Ferhatosmanoglu H, Tuncel E, Agrawal D, El Abbadi A (2001) Approximate nearest neighbor searching in multimedia databases. In: ICDE, pp 503–511

29.

Figueroa K, Paredes R (2015) Boosting the permutation based index for proximity searching. In: MCPR, pp 103–112

30.

Gennaro C, Amato G, Bolettieri P, Savino P (2010) An approach to content-based image retrieval based on the lucene search engine library. In: ECDL, pp 55–66

31.

Gessert F, Wingerath W, Friedrich S, Ritter N (2017) Nosql database systems: a survey and decision guidance. J Comput Sci R&D 32(3–4):353–365

32.

Gil-Costa V, Marin M (2011) Approximate distributed metric-space search. In: LSDS-IR, pp 15–20

33.

Gil-Costa V, Marin M, Reyes N (2009) Parallel query processing on distributed clustering indexes. J Discrete Algorithms 7(1):3–17MathSciNetCrossRefMATH

34.

Gil-Costa V, Santos RLT, Macdonald C, Ounis I (2013) Modelling efficient novelty-based search result diversification in metric spaces. J Discrete Algorithms 18:75–88MathSciNetCrossRefMATH

35.

Hersh W, Turpin A, Price S, Chan B, Kramer D, Sacherek L, Olson D (2000) Do batch and user evaluations give the same results? In: SIGIR, pp 17–24

36.

Indyk P, Motwani R (1998) Approximate nearest neighbors: towards removing the curse of dimensionality. In: ACM Symposium on Theory of Computing, pp 604–613

37.

Ingwersen P, Järvelin K (2005) The turn: integration of information seeking and retrieval in context (The Information Retrieval Series). Springer, New York Inc, SecaucusMATH

38.

Johnston N, Vincent D, Minnen D, Covell M, Singh S, Chinen TT, Hwang SJ, Shor J, Toderici G (2017) Improved lossy image compression with priming and spatially adaptive bit rates for recurrent networks. CoRR, arXiv:abs/1703.10114

39.

Karypis G (2003) Cluto-software for clustering high-dimensional datasets, version 2.1.1. http://glaros.dtc.umn.edu/gkhome/views/cluto

40.

Lux M, Chatzichristofis SA (2008) Lire: lucene image retrieval: an extensible java cbir library. In: Conference on Multimedia, pp 1085–1088

41.

MacQueen JB (1967) Some methods for classification and analysis of multivariate observations. In: Berkeley Symposium on Mathematical Statistics and Probability, vol 1, pp 281–297

42.

Mancini V, Bustos F, Gil-Costa V, Printista AM (2012) Data partitioning evaluation for multimedia systems in hybrid environments. In: 3PGCIC, pp 321–326

43.

Marin M, Ferrarotti F, Gil-Costa V (2010) Distributing a metric-space search index onto processors. In: ICPP, pp 13–16

44.

Marin M, Gil-Costa V, Uribe R (2008) Hybrid index for metric space databases. In: ICCS, pp 327–336

45.

Matej A, Vlastislav D (2016) Optimizing query performance with inverted cache in metric spaces. In: ADBIS, pp 60–73

46.

Micó ML, Oncina J, Vidal E (1994) A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. J Pattern Recognit Lett 15(1):9–17CrossRef

47.

Navarro G (2002) Searching in metric spaces by spatial approximation. In: VLDB, pp 28–46

48.

Navarro G, Reyes N (2002) Fully dynamic spatial approximation trees. In: SPIRE, pp 254–270

49.

Navarro G, Reyes N (2009) Dynamic spatial approximation trees for massive data. In: SISAP, pp 81–88

50.

Novak D, Batko M (2009) Metric index: an efficient and scalable solution for similarity search. In: SISAP, pp 65–73

51.

Novak D, Batko M, Zezula P (2012) Large-scale similarity data management with distributed metric index. J Inf Process Manag 48(5):855–872CrossRef

52.

Novak D, Zezula P (2016) PPP-codes for large-scale similarity searching. In: Database and expert-systems applications on transactions on large-scale data- and knowledge-centered systems, pp 61–87

53.

Pedreira O, Brisaboa NR (2007) Sofsem. In: Theory and practice of computer science, pp 434–445

54.

Ogras ÜY, Ferhatosmanoglu H (2003) Dimensionality reduction using magnitude and shape approximations. In: CIKM, pp 99–107

55.

Pan Z, Lei J, Zhang Y, Sun X, Kwong S (2016) Fast motion estimation based on content property for low-complexity H.265/HEVC encoder. J IEEE Trans Broadcast 62(3):675–684CrossRef

56.

Pandey S, Broder A, Chierichetti F, Josifovski V, Kumar R, Vassilvitskii S (2009) Nearest-neighbor caching for content-match applications. In: WWW, pp 441–450

57.

Pramanik S, Alexander S, Li J (1999) An efficient searching algorithm for approximate nearest neighbor queries in high dimensions. IEEE Multimed Comput Syst 1:865–869

58.

Raghavendra S, Nithyashree K, Geeta CM, Buyya R, Venugopal KR, Iyengar SS, Patnaik LM (2016) RSSMSO rapid similarity search on metric space object stored in cloud environment. J Organ Collect Intell 6(3):33–49CrossRef

59.

Ruqeishi K, Koneuay M (2015) Regrouping metric-space search index for search engine size adaptation. In: Similarity search and applications, pp 271–282

60.

Saavedra JM, Barrios JM (2015) Sketch based image retrieval using learned keyshapes (LKS). In: British Machine Vision Conference, pp 164.1–164.11

61.

Skala M (2009) Counting distance permutations. J Discrete Algorithms 7(1):49–61CrossRef

62.

Skillicorn DB, Hill JMD, McColl WF (2000) Mpeg-7. Multimedia content description interfaces, part 3: visual. Technical Report ISO/IEC 15938-3

63.

Skopal T, Lokoc J, Bustos B (2012) D-cache: universal distance cache for metric access methods. J Trans Knowl Data Eng 24(5):868–881CrossRef

64.

Solar R, Gil-Costa V, Marín M (2016) Evaluation of static/dynamic cache for similarity search engines. In: SOFSEM, pp 615–627

65.

Sadit Tellez E, Chvez E (2012) The list of clusters revisited. In: Pattern recognition, pp 187–196

66.

Wang X, Wang JTL, Lin K-I, Shasha D, Shapiro BA, Zhang K (2000) An index structure for data mining and clustering. J Knowl Inf Syst 2:161–184CrossRefMATH

67.

Weber R, Böhm K (2000) Trading quality for time with nearest neighbor search. In: Extending database technology: advances in database technology, pp 21–35

68.

Wei W, Fan X, Song H, Fan X, Yang J (2017) Imperfect information dynamic stackelberg game based resource allocation using hidden Markov for cloud computing. J IEEE Trans Serv Comput PP(99):1–1

69.

White D, Jain R (1996) Algorithms and strategies for similarity retrieval. Technical Report VCL-96-101, Visual Computing Laboratory, University of California San Diego

70.

Xia Z, Wang X, Zhang L, Qin Z, Sun X, Ren K (2016) A privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing. J IEEE Trans Inf Forensics Secur 11(11):2594–2608CrossRef

71.

Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search: the metric space approach, advances in database systems. Springer, BerlinMATH

72.

Zhou Z, Wang Y, Wu QMJ, Yang CN, Sun X (2017) Effective and efficient global context verification for image copy detection. J IEEE Trans Inf Forensics Secur 12(1):48–63CrossRef

73.

Zhou Z, Wu QMJ, Huang F, Sun X (2017) Fast and accurate near-duplicate image elimination for visual sensor networks. J Distrib Sens Netw 13(2):1–1

Title: A graph-based cache for large-scale similarity search engines
Authors: Veronica Gil-Costa
Mauricio Marin
Carolina Bonacic
Roberto Solar
Publication date: 07-12-2017
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 5/2018
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-017-2207-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 5/2018

Correction to: New algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance

An election protocol based on group membership detection algorithm in mobile ad hoc distributed systems

Preemptive cloud resource allocation modeling of processing jobs

A survey of graph processing on graphics processing units

Analysis of large deviations behavior of multi-GPU memory access in deep learning

HYSTERY: a hybrid scheduling and mapping approach to optimize temperature, energy consumption and lifetime reliability of heterogeneous multiprocessor systems

Premium Partner