Faloutsos began his tuto- or Hadoop that supports data- large-scale social and information
rial, “Graph Mining: Laws, intensive distributed computa- networks available, however,
Generators, and Tools,” by tions running on large clusters generative models that are struc-
motivating the problem of data of hundreds, thousands, or even turally or syntactically more flex-
analysis on graphs. He described hundreds of thousands of com- ible are increasingly necessary.
a wide range of applications in modity computers. By introducing a small exten-
which graphs arise naturally, and sion in the parameters of a gen-
he reminded the audience that
Algorithmic Approaches
erative model, of course, one can
large graphs that arise in modern to Networked Data observe a large increase in the
informatics applications have
Milena Mihail of the Georgia
observed properties of generated
structural properties that are very
Institute of Technology described
graphs. This observation raises
different from traditional Erdös-
algorithmic perspectives on devel-
interesting statistical questions
Rényi random graphs. Although
oping better models for data in her
about model overfitting, and
these structural properties have
tutorial, “Models and Algorithms
it argues for more refined and
been studied extensively in
for Complex Networks.” She
systematic methods of model
recent years and used to devel-
noted that a rich theory of power
parameterization. This observa-
op numerous well-publicized
law random graphs has been
tion also leads to new algorith-
models, Faloutsos also described
developed in recent years. With
mic questions, which were the
empirically observed properties
the increasingly wide range of
topic of Mihail’s talk.
that are not well reproduced by
existing models. Building on
this, Faloutsos spent much of
his talk describing several graph-
mining applications of recent
and ongoing interest.
Edward Chang described
other developments in web-
scale data analysis in his tuto-
rial, “Mining Large-Scale Social
Networks: Challenges and
Scalable Solutions.” After review-
ing emerging applications—such
as social network analysis and per-
sonalized information retrieval—
Chang covered several other appli-
cations in detail. In all these cases,
he emphasized that the main per-
formance requirements were “scal-
ability, scalability, scalability.”
Modern informatics applica-
tions such as web search afford
easy parallelization (e.g., the
overall index can be partitioned
such that even a single query
can use multiple processors).
Moreover, the peak performance
of a machine is less important
than the price-performance ratio.
In this environment, scalability
up to petabyte-sized data often
means working in a software
framework such as MapReduce
JUNE 2009 AmstAt News 17
Page 1 |
Page 2 |
Page 3 |
Page 4 |
Page 5 |
Page 6 |
Page 7 |
Page 8 |
Page 9 |
Page 10 |
Page 11 |
Page 12 |
Page 13 |
Page 14 |
Page 15 |
Page 16 |
Page 17 |
Page 18 |
Page 19 |
Page 20 |
Page 21 |
Page 22 |
Page 23 |
Page 24 |
Page 25 |
Page 26 |
Page 27 |
Page 28 |
Page 29 |
Page 30 |
Page 31 |
Page 32 |
Page 33 |
Page 34 |
Page 35 |
Page 36 |
Page 37 |
Page 38 |
Page 39 |
Page 40 |
Page 41 |
Page 42 |
Page 43 |
Page 44 |
Page 45 |
Page 46 |
Page 47 |
Page 48 |
Page 49 |
Page 50 |
Page 51 |
Page 52 |
Page 53 |
Page 54 |
Page 55 |
Page 56 |
Page 57 |
Page 58 |
Page 59 |
Page 60 |
Page 61 |
Page 62 |
Page 63 |
Page 64 |
Page 65 |
Page 66 |
Page 67 |
Page 68 |
Page 69 |
Page 70 |
Page 71 |
Page 72 |
Page 73 |
Page 74 |
Page 75 |
Page 76 |
Page 77 |
Page 78 |
Page 79 |
Page 80 |
Page 81 |
Page 82 |
Page 83 |
Page 84 |
Page 85 |
Page 86 |
Page 87 |
Page 88 |
Page 89 |
Page 90 |
Page 91 |
Page 92 |
Page 93 |
Page 94 |
Page 95 |
Page 96 |
Page 97 |
Page 98 |
Page 99 |
Page 100