Welcome to DiSC 2003
SIGMOD 2002
PODS 2002
SIGMOD RECORD 2002
ADBIS 2002
CIKM 2002
= CIKM'02 Website
<<< = CIKM'02 Papers>>>
= CIKM Workshop_1
= GIS'02 Papers
= CIKM Workshop_2
= DOLAP'02 Papers
= CIKM Workshop_3
= WIDM'02 Papers
CoopIS 2002
EDBT 2002
ER 2002
Data Engineering Bul
DEXA_EC-WEB 2002
DMKD 2002
DPDJ 2002
HYPERTEXT 2002
ICDE 2002
ICDM 2002
JCDL 2002
KDD 2002
KDD_EXPLORATIONS 20
KRDB 2002
MDM 2002
MIS 2002
RIDE 2002
SBBD 2002
SIGIR 2002
SIGIR FORUM 2002
SSDBM 2002
TODS 2002
TIME 2002
VLDB 2002
VLDBJ 2002

Future directions in data mining: streams, networks, self-similarity and power laws


Christos Faloutsos

  View Paper (PDF)  

Return to Data warehousing and OLAP


Abstract

How to spot abnormalities in a stream of temperature data from a sensor? Or from a network of sensors? How does the Internet look like? Are there 'abnormal' sub-graphs in a given social network, possibly indicating, e.g., money-laundering rings?We present some recent work and list many remaining challenges for these two fascinating issues in data mining, namely, streams and networks. Streams appear in numerous settings, in the form of, e.g., temperature readings, road traffic data, series of video frames for surveillance, patient physiological data. In all these settings, we want to equip the sensors with nimble, but powerful enough algorithms to look for patterns and abnormalities (a) on a semi-infinite stream, (b) using finite memory, and (c) without human intervention. For networks, the applications are also numerous: social networks recording who knows/calls/emails whom; the Internet itself, as well as the Web, with routers and links, or pages and hyper-links; the genes and how they are related; customers and products they buy. In fact, any "many-to-many" database relationship eventually leads to a graph/network. In all these settings we want to find patterns and 'abnormalities'; the most central/important nodes; we also want to predict how the network will evolve; and we want to tackle huge graphs, with millions or billions of nodes and edges.As a promising direction towards these problems, we present some surprising tools from the theory of fractals, self-similarity and power laws. We show how the 'intrinsic' or 'fractal' dimension can help us find patterns, when traditional tools and assumptions fail. We show that self-similarity and power laws models work well in an impressive variety of settings, including real, bursty disk and web traffic; skewed distributions of click-streams; and multiple, real Internet graphs.


DiSC'03 © 2003 Association for Computing Machinery