User Models Mediation – Prof. Tsvi Kuflik – Martedì 15 dicembre 2015

Martedì 15 dicembre – Ore 16:00-18:00

Aula N13,  piano terra, Dipartimento di Ingegneria Roma Tre

Via della Vasca Navale, 79, Roma

 

Provision of personalized recommendations to users requires accurate modeling of their interests and needs. This work proposes a general framework and specific methodologies for enhancing the accuracy of user modeling in recommender systems by importing and integrating data collected by other recommender systems. Such a process is defined as user models mediation. The work discusses the details of such a generic user modeling mediation framework. It provides a generic user modeling data representation model, demonstrates its compatibility with existing recommendation techniques, and discusses the general steps of the mediation. Specifically, four major types of mediation are presented: cross-user, cross-item, cross-context, and cross-representation. Finally, the work reports the application of the mediation framework and illustrates it with practical mediation scenarios. Evaluations of these scenarios demonstrate the potential benefits of user modeling data mediation, as in certain conditions it allows improving the quality of the recommendations provided to the users.

Schema Extraction – Divesh Srivastava – Giovedì 22 Ottobre 2015 Ore 11:00-12:30

Giovedì 22 Ottobre 2015 Ore 11:00-12:30

Sala Riunioni, 1° piano, Dipartimento di Ingegneria Roma Tre

Via della Vasca Navale, 79, Roma

 

—————————————————————————–

Schema Extraction

Abstract: Increasingly complex databases need ever more sophisticated tools to help users understand their schemas and interact with the data.  This is challenging since complex databases often have thousands of tables and inadequate schemas, with little indication of the important tables or the main concepts.  We address these challenges and describe techniques to extract an understandable schema from a complex database. We first present a robust algorithm to discover foreign/primary key relationships between tables, based on a general rule, termed Randomness.  We then describe an information-theoretic approach that takes a set of tables linked using foreign/primary keys to identify important tables and cluster tables into the main concepts of the schema.  Finally, we propose summary graphs that meet specified size constraints and preserve the most informative join paths between tables of user interest.
Bio: Divesh Srivastava is the head of Database Research at AT&T Labs-Research.  He is an ACM fellow, on the board of trustees of the VLDB Endowment, the managing editor of the Proceedings of the VLDB Endowment (PVLDB) and an associate editor of the ACM Transactions on Database Systems (TODS).  His research interests and publications span a variety of topics in data management.

Big Data Integration – Divesh Srivastava – martedi’ 20 ottobre 2015 ore 14:00

Martedì 20 Ottobre 2015 Ore 14:00-15:30
Sala Riunioni, 1° piano, Dipartimento di Ingegneria
Via della Vasca Navale, 79, Roma
——————————————————————
Abstract: The Big Data era is upon us: data are being generated, collected and analyzed at an unprecedented scale, and data-driven decision making is sweeping through all aspects of society. Since the value of data explodes when it can be linked and fused with other data, addressing the big data integration (BDI) challenge is critical to realizing the promise of Big Data. BDI differs from traditional data integration in many dimensions: (i) the number of data sources, even for a single domain, has grown to be in the tens of thousands, (ii) many of the data sources are very dynamic, as a huge amount of newly collected data are continuously made available, (iii) the data sources are extremely heterogeneous in their structure, with considerable variety even for substantially similar entities, and (iv) the data sources are of widely differing qualities, with significant differences in the coverage, accuracy and timeliness of data provided. This talk presents techniques to address these novel challenges faced by big data integration, and identifies a range of open problems for the community.
Bio: Divesh Srivastava is the head of Database Research at AT&T Labs-Research.  He is an ACM fellow, on the board of trustees of the VLDB Endowment, the managing editor of the Proceedings of the VLDB Endowment (PVLDB) and an associate editor of the ACM Transactions on Database Systems (TODS).  His research interests and publications span a variety of topics in data management.

BitConeView: Visualization of Flows in the Bitcoin Transaction Graph – Wednesday, Oct 21st

=== When ===
Wednesday, Oct 21st at 4:00 PM

=== Where ===
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

=== Title ===
BitConeView: Visualization of Flows in the Bitcoin Transaction Graph

=== Speaker ===
Valentino Di Donato
Ph.D. student at the Department of Engineering
Roma Tre University
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=didonato

=== Abstract ===
Bitcoin is a digital currency whose transactions are stored into a
public ledger, called blockchain, that can be viewed as a
directed graph with more than 70 million nodes, where each node
represents a transaction and each edge represents Bitcoins flowing
from one transaction to another one. We describe a system for the visual
analysis of how and when a flow of Bitcoins mixes with
other flows in the transaction graph. Such a system relies on high-level
metaphors for the representation of the graph and the size
and characteristics of transactions, allowing for high level analysis of
big portions of it.

Joint work with Giuseppe Di Battista, Maurizio Patrignani,
Maurizio Pizzonia, Vincenzo Roselli, and Roberto Tamassia.

The paper will be presented at the forthcoming IEEE VizSec 2015 – “IEEE
Symposium on Visualization for Cyber Security” October 26, 2015 –
Chicago, Illinois, USA (http://vizsec.org/)

Intersection-Link Representations of Graphs – Sept 11th

=== When ===
Friday, Sept 11th at 6:00 PM

=== Where ===
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

=== Title ===
Intersection-Link Representations of Graphs

=== Speaker ===
Giordano Da Lozzo
Postdoc fellow at the Department of Engineering
Roma Tre University
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=giordano

=== Abstract ===
We consider drawings of graphs that contain dense subgraphs. We
introduce intersection-link representations for such graphs, in which each vertex
u is represented by a geometric object R(u) and in which each edge (u, v) is
represented by the intersection between R(u) and R(v) if it belongs to a dense
subgraph or by a curve connecting the boundaries of R(u) and R(v) otherwise.
We study a notion of planarity, called CLIQUE PLANARITY , for intersection-link
representations of graphs in which the dense subgraphs are cliques.

Joint work with Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Ignaz Rutter.

The paper will be presented at the forthcoming 23rd International Symposium on Graph Drawing & Network Visualization September 24-26, 2015, Los Angeles, CA, USA (http://www.csun.edu/gd2015/)

Venerdì 26 giugno – Is It Really Worth to Peer At IXPs? A Comparative Study

=== When === 
    Friday, June 26th at 2:30 PM 
 
=== Where === 
    Department of Engineering 
    Section of Computer Science and Automation 
    Via della Vasca Navale, 79 
    Meeting room (1.10) on 1st floor 
 
=== Title === 
    Is It Really Worth to Peer At IXPs? A Comparative Study 
 
=== Speaker === 
    Roberto di Lallo 
    PhD Student in Computer Science and Automation 
    Roma Tre University 
    http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=roberto 
 
=== Abstract === 
Internet Exchange Points (IXPs) play a crucial role in the Internet ecosystem. 
However, existing literature fails in quantitatively assessing the advantage for 
an Internet Service Provider (ISP) to peer at an IXP. We give a contribution to bridge
such a gap by collaborating with three medium-sized ISPs in Italy to compare key performance
indicators (round-trip delay, hop count, packet loss, and jitter) as measured from several
vantage points in presence and absence of IXP peerings. Our findings are that IXP-based paths
exhibit better and more stable performance, whereas avoiding IXPs introduces performance
deterioration and higher variability. Moreover, our measurements confirm that IXP-based paths 
tend to preserve the locality of traffic. 
 
Joint work with M. Di Bartolomeo, G. Di Battista, and C. Squarcella. 
 
The paper will be presented at the forthcoming IEEE ISCC 2015 (http://www.ieee-iscc.org/)

Venerdì 3 luglio – Discovering High-Impact Routing Events Using Traceroutes

=== When ===

Friday, July 3rd at 2:30 PM

=== Where ===

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

=== Title ===

Discovering High-Impact Routing Events Using Traceroutes

=== Speaker ===

Valentino Di Donato
PhD Student in Computer Science and Automation
Roma Tre University
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=didonato

=== Abstract ===

With the increasing diffusion of Internet probing technologies, a large amount of regularly collected traceroutes are available for Internet Service Providers (ISPs) at low cost.
We introduce a practically applicable methodology and algorithm that, given solely an arbitrary set of traceroutes, spot routing paths that change similarly over time, aggregate them into inferred events, and report each event along with the impacted observation points and a small set of IP addresses that can help identify its cause. The formal model at the basis of our methodology revolves around the notion of /empathy/, a relation that binds similarly behaving traceroutes. The correctness and completeness of our approach are based on structural properties that are easily expressed in terms of empathic measurements.
We perform experiments with data from public measurement infrastructures like RIPE Atlas, showing the effectiveness of our algorithm in distilling events from a large amount of traceroute data. We also validate the accuracy of the inferred events against ground-truth knowledge of routing changes originating
from induced and spontaneous routing events. Given these promising results, we believe our methodology can be an effective aid for ISPs to detect and track routing changes affecting many users (with potentially adverse effects on their connection quality).

Joint work with M. Di Bartolomeo, M. Pizzonia, C. Squarcella, and M. Rimondini.

The paper will be presented at the forthcoming IEEE ISCC 2015 (http://www.ieee-iscc.org/)

Mercoledì 10 giugno ore 15:00 – On the Knapsack Problem with a Conflict Graph

When:

Wednesday June 10th at 10:00

Where

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

Title:

On the Knapsack Problem with a Conflict Graph

Abstract:

We consider the classical 0-1 Knapsack Problem with additional conflict restrictions on pairs of items, which state that for certain pairs of items at most one item can be contained in any feasible solution. This can also be seen as a Maximum Weight Independent Set Problem with an additional budget constraint. The conflicts between items can be represented by a conflict graph. We will give an overview on the status of approximability for different graph classes. In particular, we will describe an FPTAS for graphs of bounded treewidth and for (weakly) chordal graphs and a PTAS for planar graphs. Also modular and clique decompositions will be discussed leading to an FPTAS for certain graph classes characterized by forbidden subgraphs. (joint work with Joachim Schauer)

Lunedì 18 maggio – Planarity of Streamed Graphs

=== When ===

Monday May 18th at 11:00

 

=== Where ===

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

=== Title ===

Planarity of Streamed Graphs

=== Speaker ===

Giordano Da Lozzo
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=giordano

=== Abstract ===

Abstract.  In this work we introduce a notion of planarity for graphs that are presented in a streaming fashion.  A streamed graph is a stream of edges $e_1,e_2,…,e_m$ on a vertex set $V$.  A streamed graph is $\omega$-stream planar with respect to a positive integer window size $\omega$ if there exists a sequence of planar topological drawings $\Gamma_i$ of the graphs $G_i=(V,\{e_j \mid  i\leq j < i+\omega\})$ such that the common graph  $G^{i}_\cap=G_i\cap G_{i+1}$ is drawn the same in $\Gamma_i$ and in $\Gamma_{i+1}$, for $1\leq i < m-\omega$. The Streamed Planarity Problem with window size $\omega$ asks whether a given streamed graph is $\omega$-streamed planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step.
These problems are related to several well-studied planarity problems.

We show that the Streamed Planarity Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all $\omega \ge 2$.  On the positive side, we provide $O(n+\omega{}m)$-time algorithms for (i) the case $\omega = 1$ and (ii) all values of $\omega$ provided the backbone graph consists of one $2$-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style $O((nm)^3)$-time algorithm proposed by Schaefer~[GD’14] for $\omega=1$.

Joint work with Ignaz Rutter.
This work will be presented at CIAC ’15, the 9th International Conference on Algorithms and Complexity, May 20-22, 2015 Paris, France.

Martedì 19 maggio – Arc diagrams, flip distances, and Hamiltonian triangulations

=== When ===

Tuesday May 19th at 12:00

 

=== Where ===

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

 

=== Title ===

Arc diagrams, flip distances, and Hamiltonian triangulations

 

=== Speaker ===

Dr. Michael Hoffmann, ETH Zürich
http://www.inf.ethz.ch/personal/hoffmann/

 

=== Abstract ===

A flip is a local operation on a triangulation (maximal planar graph) that switches the diagonal of a 4-cycle. The flip graph is a graph whose vertices are all triangulations on n vertices and two triangulations are adjacent if they differ by exactly one flip. These graphs have been studied in various settings and have proven to be a very useful and versatile tool to analyze the structure of triangulations, both combinatorially and algorithmically.

In this talk I will present recently improved bounds concerning the combinatorial flip graph, where triangulations are considered to be abstract graphs (rather than, for instance, geometric realizations on a concrete point set). Specifically we show that from every triangulation on n>=6 vertices we can reach a Hamiltonian triangulation by a sequence of less than n/2 flips. An interesting bit about this bound is that it was known that 3n/5-c flips are always sufficient and sometimes necessary to reach a 4-connected triangulation (which by Tutte’s/Whitney’s Theorem is Hamiltonian). As a byproduct we improve the upper bound on the diameter of the flip graph from ~5.2n to ~5n. Finally, I will discuss an application of our result to a graph drawing problem, showing that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3n-6) edges the resulting graph admits a 2-page book embedding.

(joint work with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein)