Fast Searching by Content in Multimedia Databases.

@article{DBLP:journals/debu/Faloutsos95,
  author    = {Christos Faloutsos},
  title     = {Fast Searching by Content in Multimedia Databases},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {18},
  number    = {4},
  year      = {1995},
  pages     = {31-40},
  ee        = {db/journals/debu/Faloutsos95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We describe a domain-independent method to search multimedia databases by content. Examples of these searches include 'find all images that look like this graphic drawing (which is a photograph of a sunset)' in a collection of color images; 'find stocks that move like Motorola's' in a collection of stock price movements; and 'find patterns with stripes containing red and white' in a collection of retail catalog items.

In all these applications, we assume that there exists a distance function, which measures the dis-similarity between two objects. Given that, the idea is to extract f numerical features from each object, effectively mapping it into a point in f-dimensional space. Subsequently, any spatial access method (like the R-trees) can be used to search for similar objects (that is, nearby points in the f-d space). Comparing the features corresponds to a 'quick and dirty' test, which will help us exclude a large number of non-qualifying objects. The test could allow for false alarms, but no false dismissals. This implies that the mapping from objects to f-d points should preserve the distance, or, as we show, it should lower-bound it.

We briefly show how this idea can be applied to achieve fast searching for time sequences and for color images. Experiments on real or realistic databases show that it is much faster than sequential scanning, while not missing any qualifying objects, as expected from the lower-bounding lemma. Thus, this approach can be used for any database of multimedia objects, as long as the lower-bounding lemma is satisfied.

Copyright © 1995 by the author(s). Abstract used with permission.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition:

References

[1]

Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84

[2]

Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994: 487-499

[3]

...

[4]

Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: Extending a DBMS to Support 3D Medical Images. ICDE 1994: 314-325

[5]

...

[6]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331

[7]

Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208

[8]

...

[9]

...

[10]

...

[11]

Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz: Efficient and Effective Querying by Image Content. J. Intell. Inf. Syst. 3(3/4): 231-262(1994)

[12]

Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252

[13]

Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos: Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994: 419-429

[14]

Myron Flickner, Harpreet S. Sawhney, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, David Steele, Peter Yanker: Query by Image and Video Content: The QBIC System. IEEE Computer 28(9): 23-32(1995)

[15]

Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269

[16]

Irene Gargantini: An Effective Way to Represent Quadtrees. Commun. ACM 25(12): 905-910(1982)

[17]

...

[18]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57

[19]

Klaus Hinrichs, Jürg Nievergelt: The Grid File: A Data Structure to Support Proximity Queries on Spatial Objects. WG 1983: 100-113

[20]

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342

[21]

H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217

[22]

Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499

[23]

Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509

[24]

...

[25]

David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)

[26]

A. Desai Narasimhalu, Stavros Christodoulakis: Multimedia Information Systems: The Unfolding of a Reality (Guest Editors' Introduction). IEEE Computer 24(10): 6-8(1991)

[27]

Wayne Niblack, Ron Barber, William Equitz, Myron Flickner, Eduardo H. Glasman, Dragutin Petkovic, Peter Yanker, Christos Faloutsos, Gabriel Taubin: The QBIC Project: Querying Images by Content, Using Color, Texture, and Shape. Storage and Retrieval for Image and Video Databases (SPIE) 1993: 173-187

[28]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)

[29]

...

[30]

Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336

[31]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18

[32]

Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31

[33]

Nick Roussopoulos, Stephen Kelley, Frédéic Vincent: Nearest Neighbor Queries. SIGMOD Conference 1995: 71-79

[34]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518