Searching, Data Mining
and Visualization of Multimedia Data
by Christos Faloutsos
Abstract
The talk describes methods for similarity search and for rule discovery in multimedia
databases.
Keywords
Data Mining, Multimedia, Indexing
The talk focuses on the following two problems: Given a collection of traditional or multimedia records, (a) find records that are similar to a given record (b) find "interesting" patterns within the collection. Thus, the talk is divided in two parts.
The first part examines the indexing problem. The typical example query is: "given a collection of stock price movements, find stocks that move like IBM". We assume that a distance function is given by a domain expert. Our goal is to find quickly the desirable records. We describe the GEMINI methodology, which is typically used for such environments: The idea is to extract a few (say, n) numerical features out of every multimedia record, map it to a point in n-d space, and then use off-the-shelf spatial access methods for fast insertion and search. We give the condition under which the above method guarantees no false dismissals, and we describe several settings where it performed well (time sequences, color images, medical images etc).
Moreover, we examine user-friendly ways of posing queries. Suppose that the user wants to find stock-price movements that have the 'head and shoulder' pattern. There is no straightforward extension to SQL that could handle such queries. We present 'MindReader', a system which allows the user to specify multiple examples of desirable objects; then, the MindReader studies these objects, figures out common characteristics and tries to second-guess what the user really wants.
The second part of the talk describes tools to find patterns in a collection of multimedia records. The first such tool is 'FastMap', which automatically extracts n features from each record, trying to preserve the distances. This is useful both for indexing, as well as for visual data mining: the n multimedia objects are mapped into points in a low dimensionality space, where clusters and other regularities can be found visually. We show how FastMap was applied to text documents, to time sequences, and to video clips.
Finally, we discuss the powerful Singular Value Decomposition (SVD): When the input records are vectors and their distance is the Euclidean distance, the optimal dimensionality reduction method is SVD. We show how SVD can be used for visual data mining, for compression and for rule detection, on multimedia real datasets.