More Web Proxy on the site http://driver.im/

research-article

Free access

Caching content-based queries for robust and efficient image retrieval

Authors:

Fabrizio Falchi,

Claudio Lucchese,

Salvatore Orlando,

Raffaele Perego,

Fausto RabittiAuthors Info & Claims

EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology

Pages 780 - 790

https://doi.org/10.1145/1516360.1516450

Published: 24 March 2009 Publication History

Abstract

In order to become an effective complement to traditional Web-scale text-based image retrieval solutions, content-based image retrieval must address scalability and efficiency issues. In this paper we investigate the possibility of caching the answers to content-based image retrieval queries in metric space, with the aim of reducing the average cost of query processing, and boosting the overall system throughput. Our proposal exploits the similarity between the query object and the cache content, and allows the cache to return approximate answers with acceptable quality guarantee even if the query processed has never been encountered in the past. Moreover, since popular images that are likely to be used as query have several near-duplicate versions, we show that our caching algorithm is robust, and does not suffer of cache pollution problems due to near-duplicate query objects. We report on very promising results obtained with a collection of one million high-quality digital photos. We show that it is worth pursuing caching strategies also in similarity search systems, since the proposed caching techniques can have a significant impact on performance, like caching on text queries has been proven effective for traditional Web search engines.

References

[1]

C. Böhm, S. Berchtold, and D. A. Keim. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv., 33(3):322--373, 2001.

Digital Library

[2]

T. Bozkaya and M. Ozsoyoglu. Indexing large metric spaces for similarity search queries. ACM Trans. Database Syst., 24(3):361--404, 1999.

Digital Library

[3]

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

Digital Library

[4]

E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquín. Searching in metric spaces. ACM Computing Surveys (CSUR), 33(3):273--321, 2001.

Digital Library

[5]

P. Ciaccia, M. Patella, and P. Zezula. M-Tree: An efficient access method for similarity search in metric spaces. In Proceedings of VLDB'97, August 25--29, 1997, Athens, Greece, pages 426--435, 1997.

Digital Library

[6]

R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys, 2007.

Digital Library

[7]

T. Fagni, R. Perego, F. Silvestri, and S. Orlando. Boosting the performance of web search engines: Caching and prefetching query results by exploiting historical usage data. ACM Trans. Inf. Syst., 24(1):51--78, 2006.

Digital Library

[8]

F. Falchi, C. Lucchese, S. Orlando, R. Perego, and F. Rabitti. A metric cache for similarity search. In 6th Workshop on Large-Scale Distributed Systems for Information Retrieval (LSDS-IR'08) - in conjunction with ACM CIKM'08, October 2008.

Digital Library

[9]

H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. El Abbadi. Approximate nearest neighbor searching in multimedia databases. In Data Engineering, 2001. Proceedings. 17th International Conference on, 2001.

Digital Library

[10]

J. J. Foo, J. Zobel, R. Sinha, and S. M. M. Tahaghoghi. Detection of near-duplicate images for web search. In CIVR '07: Proceedings of the 6th ACM international conference on Image and video retrieval, pages 557--564, New York, NY, USA, 2007. ACM.

Digital Library

[11]

J. J. Foo, J. Zobel, R. Sinha, and S. M. M. Tahaghoghi. Detection of near-duplicate images for web search. In CIVR '07: Proceedings of the 6th ACM international conference on Image and video retrieval, pages 557--564, New York, NY, USA, 2007. ACM.

Digital Library

[12]

G. R. Hjaltason and H. Samet. Index-driven similarity search in metric spaces (survey article). ACM Trans. Database Syst., 28(4):517--580, 2003.

Digital Library

[13]

ISO/IEC. Information technology - Multimedia content description interfaces. Part 6: Reference Software, 2003. 15938- 6:2003.

[14]

R. Lempel and S. Moran. Predictive caching and prefetching of query results in search engines. In WWW '03: Proceedings of the 12th international conference on World Wide Web, pages 19--28, New York, NY, USA, 2003. ACM Press.

Digital Library

[15]

P. Lyman and H. R. Varian. How much information, 2003. retrieved from http://www.sims.berkeley.edu/how-much-info-2003.

[16]

E. P. Markatos. On Caching Search Engine Query Results. Computer Communications, 24(2):137--143, 2001.

Digital Library

[17]

P. Salembier and T. Sikora. Introduction to MPEG-7: Multimedia Content Description Interface. John Wiley & Sons, Inc., New York, NY, USA, 2002.

Digital Library

[18]

H. Samet. Foundations of Multidimensional and Metric Data Structures. Computer Graphics and Geometric Modeling. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2006.

Digital Library

[19]

C. Silverstein, H. Marais, M. Henzinger, and M. Moricz. Analysis of a very large web search engine query log. SIGIR Forum, 33(1):6--12, 1999.

Digital Library

[20]

R. van Zwol. Flickr: Who is looking? In In proceedings of the 2007 IEEE / WIC / ACM International Conference on Web Intelligence (WI 2007), November 2007.

Digital Library

[21]

R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In A. Gupta, O. Shmueli, and J. Widom, editors, VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24--27, 1998, New York City, New York, USA, pages 194--205. Morgan Kaufmann, 1998.

Digital Library

[22]

R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proc. 24th Int. Conf. Very Large Data Bases, VLDB, pages 194--205, 1998.

Digital Library

[23]

Y. Xie and D. O'Hallaron. Locality in search engine queries and its implications for caching. In Proceedings of IEEE INFOCOM 2002, The 21^st Annual Joint Conference of the IEEE Computer and Communications Societies, 2002.

[24]

P. Zezula, G. Amato, V. Dohnal, and M. Batko. Similarity Search The Metric Space Approach, volume 32 of Advances in Database Systems. 233 Spring Street, New York, NY 10013, USA, 2006.

Digital Library

Cited By

Sponner MWaschneck BKumar A(2024)Adapting Neural Networks at Runtime: Current Trends in At-Runtime Optimizations for Deep LearningACM Computing Surveys10.1145/365728356:10(1-40)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3657283
Frieder OMele IMuntean CNardini FPerego RTonellotto N(2022)Caching Historical Embeddings in Conversational SearchACM Transactions on the Web10.1145/357851918:4(1-19)Online publication date: 29-Dec-2022
https://dl.acm.org/doi/10.1145/3578519
Zeng MYao BWang ZShen YLi FZhang JLin HGuo M(2019)CATIRI: An Efficient Method for Content-and-Text Based Image RetrievalJournal of Computer Science and Technology10.1007/s11390-019-1911-234:2(287-304)Online publication date: 22-Mar-2019
https://doi.org/10.1007/s11390-019-1911-2
Show More Cited By

Index Terms

Caching content-based queries for robust and efficient image retrieval
1. Information systems
  1. Information retrieval
    1. Information retrieval query processing

Recommendations

Query Reformulation for Content Based Multimedia Retrieval in MARS
ICMCS '99: Proceedings of the IEEE International Conference on Multimedia Computing and Systems - Volume 2

Unlike traditional database management systems, in content-based multimedia retrieval databases, it is difficult for users to express their exact information need directly in a precise query. A typical interface allows users to express their information ...
IR principles for content-based indexing and retrieval of functional brain images
CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management

In this paper, we explore the concept of a "library of brain images", which implies not only a repository of brain images, but also efficient search and retrieval mechanisms that are based on models derived from IR practice. As a preliminary study, we ...
Localized Content-Based Image Retrieval

We define localized content-based image retrieval as a CBIR task where the user is only interested in a portion of the image, and the rest of the image is irrelevant. In this paper we present a localized CBIR system, Accio, that uses labeled images in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology

March 2009

1180 pages

ISBN:9781605584225

DOI:10.1145/1516360

Editors:
Martin Kersten
CWI, The Netherlands
,
Boris Novikov
University of Saint Petersburg, Russia
,
Jens Teubner
ETH Zurich, Switzerland
,
Vladimir Polutin
HP Labs, Russia
,
Stefan Manegold
CWI, The Netherlands

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

EDBT/ICDT '09

EDBT/ICDT '09: EDBT/ICDT '09 joint conference

March 24 - 26, 2009

Saint Petersburg, Russia

Acceptance Rates

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
400
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)13

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sponner MWaschneck BKumar A(2024)Adapting Neural Networks at Runtime: Current Trends in At-Runtime Optimizations for Deep LearningACM Computing Surveys10.1145/365728356:10(1-40)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3657283
Frieder OMele IMuntean CNardini FPerego RTonellotto N(2022)Caching Historical Embeddings in Conversational SearchACM Transactions on the Web10.1145/357851918:4(1-19)Online publication date: 29-Dec-2022
https://dl.acm.org/doi/10.1145/3578519
Zeng MYao BWang ZShen YLi FZhang JLin HGuo M(2019)CATIRI: An Efficient Method for Content-and-Text Based Image RetrievalJournal of Computer Science and Technology10.1007/s11390-019-1911-234:2(287-304)Online publication date: 22-Mar-2019
https://doi.org/10.1007/s11390-019-1911-2
Lovagnini LZhang WBijarbooneh FHui PBoll SMu Lee KLuo JZhu WByun HWen Chen CLienhart RMei T(2018)CIRCEProceedings of the 26th ACM international conference on Multimedia10.1145/3240508.3240697(346-354)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3240508.3240697
Antol MDohnal V(2018)Towards Artificial Priority Queues for Similarity Query Execution2018 IEEE 34th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW.2018.00020(78-83)Online publication date: Apr-2018
https://doi.org/10.1109/ICDEW.2018.00020
Gil-Costa VMarin MBonacic CSolar R(2018)A graph-based cache for large-scale similarity search enginesThe Journal of Supercomputing10.1007/s11227-017-2207-374:5(2006-2034)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11227-017-2207-3
Tang BYiu MHua K(2017)Exploit every bit: Effective caching for high-dimensional nearest neighbor search (extended abstract)2017 IEEE 33rd International Conference on Data Engineering (ICDE)10.1109/ICDE.2017.29(45-46)Online publication date: Apr-2017
https://doi.org/10.1109/ICDE.2017.29
Tang BYiu MHua K(2016)Exploit Every BitIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.251560328:5(1175-1188)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TKDE.2016.2515603
Brisaboa NCerdeira-Pena AGil-Costa VMarin MPedreira O(2015)Efficient Similarity Search by Combining Indexing and Caching StrategiesProceedings of the 41st International Conference on SOFSEM 2015: Theory and Practice of Computer Science - Volume 893910.1007/978-3-662-46078-8_40(486-497)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1007/978-3-662-46078-8_40
Barrios JBustos BSkopal T(2014)Analyzing and dynamically indexing the query setInformation Systems10.1016/j.is.2013.05.01045(37-47)Online publication date: Sep-2014
https://doi.org/10.1016/j.is.2013.05.010
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents