Article

Optimizing progressive query-by-example over pre-clustered large image databases

Authors:

Anicet Kouomou Choupo,

Laure Berti-Équille,

Annie MorinAuthors Info & Claims

CVDB '05: Proceedings of the 2nd international workshop on Computer vision meets databases

Pages 13 - 20

https://doi.org/10.1145/1160939.1160946

Published: 17 June 2005 Publication History

Abstract

The typical mode for querying in an image content-based information system is query-by-example, which allows the user to provide an image as a query and to search for similar images (i.e., the nearest neighbors) based on one or a combination of low-level multidimensional features of the query example. Off-lime, this requires the time-consuming pre-computing of the whole set of visual descriptors over the image database. On-line, one major drawback is that multidimensional sequential NN-search is usually exhaustive over the whole image set face to the user who has a very limited patience. In this paper, we propose a technique for improving the performance of image query-by-example execution strategies over multiple visual features. This includes first, the pre-clustering of the large image database and then, the scheduling of the processing of the feature clusters before providing progressively the query results (i.e., intermediate results are sent continuously before the end of the exhaustive scan over the whole database). A cluster eligibility criterion and two filtering rules are proposed to select the most relevant clusters to a query-by-example. Experiments over more than 110 000 images and five MPEG-7 global features show that our approach significantly reduces the query time in two experimental cases: the query time is divided by 4.8 for 100 clusters per descriptor type and by 7 for 200 clusters per descriptor type compared to a "blind" sequential NN-search with keeping the same final query result. This constitutes a promising perspective for optimizing image query-by-example execution.

References

[1]

Babu S., Bizarro P., Adaptive Query Processing in the Looking Glass. Proc. of the 2nd Biennial Conf. on Innovative Data Systems Research (CIDR), Jan. 2005.]]

[2]

Bentley J. L., Multidimensional Binary Search in Database Applications. IEEE Trans. on Soft. Eng., 4(5), 1979, 333--340.]]

Digital Library

[3]

Berrani S. A., Amsaleg L., Gros P., Approximate k-Nearest Neighbor Searches: A New Algorithm with Probabilistic Control of the Precision. Tech. Rep. INRIA, n° 4675, 2002.]]

[4]

Beyer K., Goldstein J., Ramakrishnan R., Shaft U., When Is "Nearest Neighbor" Meaningful? Proc. of the 8th Intl. Conf. ICDT, London, U. K., 1999.]]

Digital Library

[5]

Böhm C., Berchtold S., Keim D., Searching in High-dimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases. ACM Comp. Surveys, (33)3, 2001.]]

Digital Library

[6]

Cornacchia R., Ballegooij A., de Vries A. P., A Case Study on Array Query Optimization. Proc. of the 1^st ACM Workshop Computer Vision meets Databases (CVDB), 2004.]]

Digital Library

[7]

Fagin R., Kumar R., Sivakumar D., Efficient Similarity Search and Classification via Rank Aggregation, Proc. of the Conf. ACM SIGMOD, 2003, 301--312.]]

Digital Library

[8]

Jain A. K., Dubes R. C., Algorithms for Clustering Data. Prentice Hall, New Jersey, 1988.]]

Digital Library

[9]

Gounaris A., Paton N., Fernandes A., Sakellariou R., Adaptive Query Processing. Proc. of the Conf. BNCOD, LNCS, vol. 2405, 2002, 11--25.]]

Digital Library

[10]

Guttman A., R-trees: A dynamic Index Structure for Spatial Searching. Proc. of the Conf. ACM SIGMOD, 1984, 47--57.]]

Digital Library

[11]

Kiranyaz S., Gabbouj M., A Novel Multimedia Retrieval Technique: Progressive Query (Why Wait?). Proc. of Intl. Workshop of Image Analysis, Portugal, 2004.]]

[12]

Korn F., Pagel B., Faloutsos C., On the 'Dimensionality Curse' and the 'Self-Similarity Blessing'. IEEE Trans. on Knowledge and Data Engineering 13(1), 2001, 96--111.]]

Digital Library

[13]

Kouomou-Choupo A., Berti-Équille L., Visual Feature Mining for Adapting Query-by-Example over Large Image Databases. Proc. of Intl. Workshop on Multidisciplinary, Video, and Audio retrieval and Mining, Canada, 2004.]]

[14]

Li C., Chang E., Garcia-Molina H., Wiederhold G., Clustering for Approximate Similarity Search in High-Dimensional Spaces. IEEE Trans. on Knowledge and Data Engineering, 14(4), 2002, 792--808.]]

Digital Library

[15]

Nievergelt J., Hinterberger H., Sevcik K. C., The GridFile: An Adaptable, Symmetric Multikey File Structure. ACM Trans. on Database Systems, 9(1), 1984, 38--71.]]

Digital Library

[16]

Obeid M., Jedynak B., Daoudi M., Image Indexing and Retrieval Using Intermediate Features. Proc. of the 9^th ACM Intl. Conference on Multimedia, 2001, 531--533.]]

Digital Library

[17]

Rijsbergen C. V., Information Retrieval, Butterworth, 1979.]]

Digital Library

[18]

Schmid C., Mohr R., Local Grayvalue Invariants for Image Retrieval, IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(5), 1997, 530--534.]]

Digital Library

[19]

Siguroardottir R., Hauksson H., Pór-Jónsson B., Amsaleg L., A Case Study of the Quality vs. Time Trade-off for Approximate Image Descriptor Search. Proc. of the 1 st IEEE Intl. Workshop on Managing Data for Emerging Multimedia Applications (EMMA), Tokyo, Japan, 2005.]]

[20]

Smeulders A., Worring M., Santini S., Gupta A., and Jain R. Content-based Image Retrieval at the End of the Early Years. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22, 12 (Dec. 2000), 1349--1380.]]

Digital Library

[21]

Tao Y., Grosky W., Object-Based image retrieval using point feature maps. Proc. of the Intl. Conf. on Database Semantics (DS-8), 1999, 59--73.]]

[22]

Tuytelaars T., Van Gool L., Content-Based Image Retrieval Based on Local Affinely Invariant Regions. Proc. of the 3^rd Intl. Conf. on Visual Inf. Syst. (Visual'99), 1999, 493--500.]]

Digital Library

[23]

Weber R., Bohm K., Trading Quality for Time with Nearest Neighbor Search. Proc. of the 7th Intl. Conf. on EDBT, Konstanz, Germany, 2000.]]

Digital Library

[24]

Weber R., Schek H., Blott S., A Quantitative Analysis of Performance Study for Similarity-Search Methods in High-Dimensional Spaces. Proc. of the 24th Intl. Conf. on VLDB, New-York, US, 1998, 194--205.]]

Digital Library

[25]

Yamane Y., Hoshiai T., Tsuda H., Katayama K., Ohta M., Ishikawa H., Multi-Vector Feature Space Based on Pseudo-Euclidean Space and Oblique Basis for Similarity Searches of Images. Proc. of the 1^st ACM Workshop Computer Vision meets Databases (CVDB), 2004.]]

Digital Library

Cited By

Lim LWang HWang MGuerrini GPaton N(2013)Semantic queries by exampleProceedings of the 16th International Conference on Extending Database Technology10.1145/2452376.2452417(347-358)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2452376.2452417
Leszczuk MGrega M(2010)Prototype Software for Video Summary of Bronchoscopy Procedures with the Use of Mechanisms Designed to Identify, Index and SearchInformation Technologies in Biomedicine10.1007/978-3-642-13105-9_58(587-598)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13105-9_58

Optimizing progressive query-by-example over pre-clustered large image databases
1. Information systems
  1. Information retrieval

Recommendations

Image retrieval on large-scale image databases
CIVR '07: Proceedings of the 6th ACM international conference on Image and video retrieval

Online image repositories such as Flickr contain hundreds of millions of images and are growing quickly. Along with that the needs for supporting indexing, searching and browsing is becoming more and more pressing. In this work we will employ the image ...
An Adaptive Fuzzy Clustering Method for Query-by-Multiple-Example Image Retrieval
SITIS '07: Proceedings of the 2007 Third International IEEE Conference on Signal-Image Technologies and Internet-Based System

Content-based image retrieval (CBIR) methods usually adopt color, texture and structure as image feature vector. Recent research indicates that since these features are not exactly associated with image semantic meaning, Query-By-One-Example (QBOE), ...
Improving image retrieval effectiveness in query-by-example environment
SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

Query-by-example is the most popular query model for today's image retrieval systems. A typical query image contains not only relevant objects (e.g., Eiffel Tower), but also irrelevant image areas (e.g., the background). The latter, referred to as noise ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

CVDB '05: Proceedings of the 2nd international workshop on Computer vision meets databases

June 2005

75 pages

ISBN:1595931511

DOI:10.1145/1160939

Copyright © 2005 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: 17 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CVDB05

CVDB05: 2nd Computer Vision Meets Databases Workshop

June 17, 2005

MD, Baltimore, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
297
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lim LWang HWang MGuerrini GPaton N(2013)Semantic queries by exampleProceedings of the 16th International Conference on Extending Database Technology10.1145/2452376.2452417(347-358)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2452376.2452417
Leszczuk MGrega M(2010)Prototype Software for Video Summary of Bronchoscopy Procedures with the Use of Mechanisms Designed to Identify, Index and SearchInformation Technologies in Biomedicine10.1007/978-3-642-13105-9_58(587-598)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13105-9_58

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents