Sorting and Ranking: Two Unrelated Talks
Marco Bressan

23 April 2013, 14h00 - 23 April 2013, 15h00 Salle/Bat : 2013/DIG-Moulon
Contact :

Activités de recherche :

Résumé :

This seminar consists of two (unrelated) talks discussing the speaker's
latest research activity, plus an overview of the next research directions.
In the rst talk we will dig into psort, a fast, stable sorting software
for large datasets on external memory. According to the Sort Benchmark competition, psort was the fastest sorting library for PC-class machines in 2008, 2009, 2010, 2011 and 2012, ouperforming state-of-the-art external sorting libraries such as nsort and STXXL. At the heart of psort's performance are not its (decades old) sorting algorithms, but its carefully engineered code and its accurate tuning to modern architectures.
In the second talk we will investigate theoretical aspects of ranking
the nodes of a graph according to their PageRank scores. We will discuss if it is possible to compute the relative ranking of a few nodes locally, by exploring only small subgraphs around those nodes and disregarding the most part of the graph. Furthermore, we will see how much" of this ranking is determined by the graph's structure, and how much by an external, arbitrary parameter required by PageRank (the damping factor), with somewhat surprising results.
We will conclude with a short overview of the next research directions, which involve nding in
uential users and maximizing the spread of information in a network { both hot topics in social network mining. To address these problems, we will complement classical" approaches with machine learning techniques.