Hill climbing algorithms for content-based retrieval of similar configurations
Inhaltsverzeichnis
Referenz
D. Papadias: Hill climbing algorithms for content-based retrieval of similar configurations. Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval
DOI
http://dx.doi.org/10.1145/345508.345587
Abstract
The retrieval of stored images matching an input configuration is an important form of content-based retrieval. Exhaustive processing (i.e., retrieval of the best solutions) of configuration similarity queries is, in general, exponential and fast search for sub-optimal solutions is the only way to deal with the vast (and ever increasing) amounts of multimedia information in several real-time applications. In this paper we discuss the utilization of hill climbing heuristics that can provide very good results within limited processing time. We propose several heuristics, which differ on the way that they search through the solution space, and identify the best ones depending on the query and image characteristics. Finally we develop new algorithms that take advantage of the specific structure of the problem to improve performance.
Extended Abstract
Bibtex
@inproceedings{Papadias:2000:HCA:345508.345587,
author = {Papadias, Dimitris},
title = {Hill Climbing Algorithms for Content-based Retrieval of Similar Configurations},
booktitle = {Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval},
series = {SIGIR '00},
year = {2000},
isbn = {1-58113-226-3},
location = {Athens, Greece},
pages = {240--247},
numpages = {8},
url = {http://doi.acm.org/10.1145/345508.345587 http://de.evo-art.org/index.php?title=Hill_climbing_algorithms_for_content-based_retrieval_of_similar_configurations&action=edit},
doi = {10.1145/345508.345587},
acmid = {345587},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {MMIR (general), content-based indexing\&slash;retrieval (general), efficient search over non-textual information, image indexing\&slash;retrieval},
}
Used References
1 James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 http://doi.acm.org/10.1145/182.358434
2 Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, USA http://doi.acm.org/10.1145/276304.276318
3 Chang S., Jungert E., Li. T. Representation and Retrieval of Symbolic Pictures Using Generalized 2D Strings. SPIE Visual Communications and Image Processing IV, 1989.
4 S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987 http://dx.doi.org/10.1109/TPAMI.1987.4767923
5 Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997 http://dl.acm.org/citation.cfm?id=671005&CFID=558819604&CFTOKEN=68186175
6 Egenhofer M. Query Processing in Spatial-Query-by-Sketch. Journal of Visual Languages and Computing, 8, 403-424, 1997.
7 César A. Galindo-Legaria , Arjan Pellenkoft , Martin L. Kersten, Fast, Randomized Join-Order Selection - Why Use Transformations?, Proceedings of the 20th International Conference on Very Large Data Bases, p.85-95, September 12-15, 1994 http://dl.acm.org/citation.cfm?id=672975&CFID=558819604&CFTOKEN=68186175
8 Ian P. Gent , Ewan MacIntyre , Patrick Prosser , Toby Walsh, The constrainedness of search, Proceedings of the thirteenth national conference on Artificial intelligence, p.246-252, August 04-08, 1996, Portland, Oregon http://dl.acm.org/citation.cfm?id=1892912&CFID=558819604&CFTOKEN=68186175
9 Venkat N. Gudivada , Vijay V. Raghavan, Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Transactions on Information Systems (TOIS), v.13 n.2, p.115-144, April 1995 http://doi.acm.org/10.1145/201040.201041
10 Haralick R.M., Elliot G.L. Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artificial Intelligence, 14, 263-313, 1980.
11 Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, USA http://doi.acm.org/10.1145/253260.253340
12 Suh-Yin Lee , Fang-Jung Hsu, Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation, Pattern Recognition, v.25 n.3, p.305-318, March 1992 http://dx.doi.org/10.1016/0031-3203(92)90112-V
13 Lee S, Yang M, Chert J. Signature File as a Spatial Filter for Iconic Image Database. Journal of Visual Languages and Computing, 3, 373-397, 1992.
14 Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.1-12, May 31-June 03, 1999, Philadelphia, Pennsylvania, USA http://doi.acm.org/10.1145/304182.304183
15 Steven Minton , Mark D. Johnston , Andrew B. Philips , Philip Laird, Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, v.58 n.1-3, p.161-205, Dec. 1992 http://dx.doi.org/10.1016/0004-3702(92)90007-K
16 Mohammad Nabil , Anne H. H. Ngu , John Shepherd, Picture Similarity Retrieval Using the 2D Projection Interval Representation, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.533-539, August 1996 http://dx.doi.org/10.1109/69.536246
17 Dimitris Papadias , Nikos Mamoulis , Vasilis Delis, Algorithms for Querying by Spatial Structure, Proceedings of the 24rd International Conference on Very Large Data Bases, p.546-557, August 24-27, 1998 http://dl.acm.org/citation.cfm?id=671163&CFID=558819604&CFTOKEN=68186175
18 Dimitris Papadias , Nikos Mamoulis , Dimitris Meretakis, Image similarity retrieval by spatial constraints, Proceedings of the seventh international conference on Information and knowledge management, p.289-296, November 02-07, 1998, Bethesda, Maryland, USA http://doi.acm.org/10.1145/288627.288669
19 Dimitris Papadias , Marios Mantzourogiannis , Panos Kalnis , Nikos Mamoulis , Ishfaq Ahmad, Content-based retrieval using heuristic search, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, August 15-19, 1999, Berkeley, California, USA http://doi.acm.org/10.1145/312624.312673
20 Papadias D., Sellis T. A Pictorial Query-By-Example Language. Journal of Visual Languages and Computing, 6(1), 53-72, 1995.
21 Euripides G. M. Petrakis , Christos Faloutsos, Similarity Searching in Medical Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.435-447, May 1997 http://dx.doi.org/10.1109/69.599932
22 Euripides G. M. Petrakis , Christos Faloutsos , King-Ip (David) Lin, ImageMap: An Image Indexing Method Based on Spatial Similarity, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.979-987, September 2002 http://dx.doi.org/10.1109/TKDE.2002.1033768
23 Smith J., Chang S.-F. VisualSeek: A fully automated content-based image query system. International Conference on Image Processing, 1996.
24 John R. Smith , Shih-Fu Chang, Integrated spatial and feature image query, Multimedia Systems, v.7 n.2, p.129-140, March 1999 http://dx.doi.org/10.1007/s005300050116
25 A. Soffer , H. Samet, Pictorial Queries by Image Similarity, Proceedings of the International Conference on Pattern Recognition (ICPR '96) Volume III-Volume 7276, p.114, August 25-29, 1996 http://dl.acm.org/citation.cfm?id=842186&CFID=558819604&CFTOKEN=68186175
Links
Full Text
http://www.cs.ust.hk/faculty/dimitris/PAPERS/sigir00.pdf
