CNPq: IMiMD-Indexing and Data Mining in Multimedia Databases

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This is a joint effort with Prof. Caetano Traina from the University of Sao Paulo, Brazil. It strengthens the existing collaboration between Prof. Christos Faloutsos at CMU and Prof. Traina and his group, which has already contributed fast indexing methods for metric and video datasets. CMU brings expertise in video indexing (the Informedia DL-II project), in power laws, and in data mining. The benefit of the collaboration will be faster methods for indexing multimedia and metric datasets, and for finding patterns in such collections. This project focuses on indexing multimedia data and on developing new tools to find patterns and correlations in such data. Multimedia objects can often be mapped to n-dimensional points through feature extraction. If not, then they can be treated as metric data, when we are provided a pair-wise distance function. The methods will be applicable to multimedia, metric and spatial data alike. Typical questions include: "find video clips similar to a given video clip"; "how strong is the correlation (or anti-correlation) between the locations of schools and the locations of libraries?"; "how many schools are within 5 miles from libraries?". For indexing, the goals are (a) to provide formulas to estimate the selectivities for similarity queries and (b) to build faster searching structures. Preliminary joint work showed that the distribution of distances in spatial and metric datasets often follows a "power-law", which are useful to design better search strategies. For data mining, the goals are to provide tools for detection of spatial correlations and to develop fast visualization algorithms for spatial and multimedia datasets. The developed tools will be able to show whether there are clusters in a dataset, how many they are, and whether two groups of points (e.g. "schools" and "libraries") are "attracting" or "repelling" each other.