Instructor: Christos Faloutsos ( CMU )
Title: Next generation data mining tools, using SVD and fractals.

ABSTRACT

What patterns can we find in a bursty web traffic?
On the web graph itself?
How about the distributions of galaxies in the sky, or
the distribution of a company's customers in geographical space?
How long should we expect a nearest-neighbor search to take,
when there are 100 attributes per patient or customer record? 
The traditional assumptions (uniformity, independence, Poisson arrivals,
Gaussian distributions), often fail miserably.
Should we give up trying to find patterns in such settings?

This tutorial focuses on two powerful but less known tools,
namely on the Singular Value Decomposition (SVD) and  on Fractals.
SVD is a provably optimal method for dimensionality reduction
and feature selection; it is the engine-under-the hood for breakthrough
concepts like the Latent Semantic Indexing (LSI),
the Karhunen-Loeve transform and the Kleinberg algorithm
for web-site importance ranking, to name a few.
Fractals, self-similarity and power laws are extremely successful
in describing real datasets (coast-lines, rivers basins,
stock-prices, brain-surfaces, web and disk traffic, to name a few).

Although both tools are impressively general and useful,
their introductory papers are typically not tailored 
towards a database audience, rendering them inaccessible.
This tutorial exactly tries to remedy the situation.
Specifically, it has two goals:
(a) to introduce the most useful concepts from SVD and Fractals,
    emphasizing the intuition behind them, 
    and avoiding the unnecessary mathematical intricacies and
(b) to illustrate the usefulness of SVD and fractals 
    for a variety of data base and data mining applications.

TARGET AUDIENCE: Researchers working on  spatial access methods,
on query optimization, and on data mining.

PREREQUISITES: None. 

BENEFITS TO PARTICIPANTS: The participants will gain 
the intuition behind these powerful tools, and they will get exposed 
to numerous settings where SVD and fractals solved 
the data mining/data base problem at hand.

INSTRUCTOR'S BIOGRAPHICAL NOTE

Christos Faloutsos received the B.Sc. degree in Electrical Engineering (1981)
from the National Technical University of Athens, Greece and
the M.Sc. and Ph.D. degrees in Computer Science 
from the University of Toronto, Canada.
He is currently a professor at Carnegie Mellon University.

He has received the Presidential Young Investigator Award by 
the National Science Foundation (1989),
two ``best paper'' awards (SIGMOD 94, VLDB 97),
and four teaching awards.
He has published over 90 refereed articles,
one monograph, and holds four patents.
His research interests include data mining,
indexing in relational and
multimedia databases, and database performance.