Rapporto sulle attività dal 9/2/2008
Work Part 2:
Algoritmi per domini applicativi
specifici
Camil Demetrescu
Università di Roma “La Sapienza”
[email protected]
Task Tree
Task 2.1 - Collezioni di documenti e sequenze di
grandi dimensioni
Tecniche di analisi spettrale RM1 + RM2
Sequenze biologiche PI
Task 2.2 - Grafi e reti di grandi dimensioni
Reti ad-hoc e dinamiche TUTTI
Analisi visuale di reti RM3
Task 3.3 - Problemi computazionali di grandi
dimensioni
Applicazioni agli elementi finiti PD
Simulazione di alluvioni RM1
Statistiche Finali: WP2
Pubblicazioni (Y1,Y2): (26,50) Tot =76
Conferences:
Y1:12
Y2:24
Journals:
Y1:12
Y2:13
Altro:
Y1:2
Y2:13
Grande incremento di pubblicazioni anno 2
Costo finale MIUR per articolo di WP2: 1470 Euro
Visto il numero di contributi, la presentazione dei
risultati non è totalmente esaustiva
Statistiche Finali: WP1 vs. WP2
Pubblicazioni WP1 (Y1,Y2): (36,72) Tot =108
Conferences:
Journals:
Y1:26
Altro:
Y1:2 Y2:4
Y1:8
Y2:23
Y2:45
Pubblicazioni WP2 (Y1,Y2): (26,50) Tot =76
Conferences:
Journals:
Y1:12
Y2:24
Y1:12
Y2:13
Altro:
Y1:2
Y2:13
Costo finale MIUR per 184 articoli: 607 Euro
Partecipazione unità al WP2
RM1 RM2 RM3 PD
PI
Task 2.1 (Y1,Y2): (12,5)
Collezioni di documenti e
sequenze di grandi dimensioni
-1-
-1-
012
Task 2.2 (Y1,Y2): (12,45)
Grafi e reti di grandi dimensioni
012
012 012 -12 01-
Task 2.3 (Y1,Y2): (2,1)
Problemi computazionali di
grandi dimensioni
-12
0 = Al tempo della proposal
1 = Anno 1
012
2 = Anno 2
Task 2.1
Collezioni di documenti e sequenze di
grandi dimensioni
Task 2.1 – Collezioni di documenti e sequenze
di grandi dimensioni
Unità di Pisa (1/3)
Risultati: memorizzazione di un insieme di stringhe
occupando uno spazio vicino al minimo information
theoretical
P. Ferragina, R. Grossi, A. Gupta, R. Shah, J.S. Vitter, On Searching
Compressed String Collections Cache-Obliviously, Principles of Database
Systems (PODS'08), ACM press, 181-190, 2008.
Task 2.1 – Collezioni di documenti e sequenze
di grandi dimensioni
Unità di Pisa (2/3)
Risultati: classico problema della selezione ottima
esteso però ai suffissi di una stringa. Ottimalità nel
modello cache-oblivious.
G. Franceschini, R. Grossi, S. Muthukrishnan, Optimal cache-aware suffix
selection, Symposium on Theoretical Aspects of Computer Science
(STACS'09), 457-468, 2009.
Task 2.1 – Collezioni di documenti e sequenze
di grandi dimensioni
Unità di Pisa (3/3)
Risultati: dizionario statico in spazio vicino al minimo
information theoretical. Riduzione della ridondanza
rispetto allo spazio minimo.
R. Grossi, A. Orlandi, R. Raman, S.S. Rao, More haste, less waste: Lowering
the redundancy in fully indexable dictionaries, Symposium on Theoretical
Aspects of Computer Science (STACS'09), 517-528, 2009.
Task 2.1 – Collezioni di documenti e sequenze
di grandi dimensioni
Risultati parziali attesi della fase 2 (da proposal)
Documenti XML:
Prototipo software con funzionalità di ricerca ed indicizzazione in collezioni di
documenti (Pisa)
Sequenze biologiche:
Strumento software per l'identificazione di grandi frammenti comuni nei
cromosomi dei mammiferi (Pisa)
Task 2.2
Grafi e reti di grandi dimensioni
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Padova (1/4)
Risultato: Complessità VLSI delle macchine universali
Primi circuiti univers. con slowdown O(1) e area blowup O(A^eps)
Tradeoff area-tempo per circuiti VLSI universali
S.N. Bhatt, G. Bilardi, and G. Pucci. Area-Time Tradeoffs for Universal VLSI
Circuits. Theoretical Computer Science, 408(2-3):143-150, 2008.
(Padova non era coinvolta originariamente in questo task ma i risultati riportati
sono pertinenti)
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Padova (2/4)
Risultato: Ad hoc networks di grandi dimensioni
Completa connettività (w.h.p.) per reti ad hoc Bluetooth
con dispositivi con range di visibilita' limitato
Tecniche per grafi random
P. Crescenzi, C. Nocentini, A. Pietracaprina, and G. Pucci. On the Connectivity of
Bluetooth-Based Ad Hoc Networks. In Concurrency and Computation: Practice and
Experience. Special Issue on EUROPAR 2007. In press, 2008.
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Padova (3/4)
Risultato: Routing su reti di grandi dimensioni
Routing in tempo ottimo Omega(sqrt(cn)) per 1-c relazioni
Algoritmi randomizzati con spazio O(1) per nodo
Algoritmi deterministici con spazio O(c) per nodo
K.T. Herley, A. Pietracaprina and G. Pucci. Store-and-Forward Multicast Routing
on the Mesh. Theory of Computing Systems, 42(4), 2008.
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Padova (4/4)
Risultato: Analisi prestazioni di Overlay Computers
Benchmarks per stimare banda, latenza e potenza di calcolo in reti
peer-to-peer
Tools per l'utilizzazione efficiente di un "Overlay Computer"
P. Bertasi, M. Bianco, A. Pietracaprina, G. Pucci. Obtaining Performance
Measures through Microbenchmarking in a Peer-to-Peer Overlay Computer.
International Journal of Computational Intelligence Research, 4, 2008.
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 1
Risultato: Struttura dati compatta che consente di
rappresentare implicitamente le distanze tra ogni
coppia di nodi in una rete nel caso di guasto di un
qualunque link o nodo.
C. Demetrescu, M. Thorup, V. Ramachandran, R. A. Chowdhury, Oracles
for distances avoiding a failed node or link . SIAM Journal on Computing,
2008.
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 1 + Roma 2
Risultato: Approccio al mantenimento dinamico della
raggiungibilità in una rete basato su rivalutazione di
polinomi su matrici.
C. Demetrescu, G. F. Italiano. Mantaining Dynamic Matrices for Fully
Dynamic Transitive Closure. Algorithmica, 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 2 (1/5)
Risultato: Routing in reti ad anello e algoritmi
distribuiti
A short proof of
the VPN Tree Routing Conjecture on ring
networks. Oper. Res. Lett., 2008
F. Grandoni, V. Kaibel, G. Oriolo, M. Skutella.
Distributed weighted
vertex cover via maximal matchings. ACM Transactions
F. Grandoni, J. Könemann, A. Panconesi.
on Algorithms, 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 2 (2/5)
Risultato: Algorimi esatti (cover, dominating set, ecc.)
F. Grandoni, J. Könemann, A. Panconesi, M. Sozio. A Primal-Dual
Bicriteria Distributed Algorithm for Capacitated Vertex Cover. SIAM
J. Comput, 2008
F.V. Fomin, F. Grandoni, A.V. Pyatkin, A.A. Stepanov. Combinatorial
bounds via measure and conquer: Bounding minimal dominating sets
and applications. ACM Transactions on Algorithms, 2008
F. V. Fomin, F. Grandoni, D. Kratsch. Solving Connected Dominating
Set Faster than 2n. Algorithmica, 2008
F. V. Fomin, F. Grandoni, D. Kratsch. Faster Steiner Tree Computation
in Polynomial-Space. Proc. ESA 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 2 (3/5)
Risultato: Algorimi approssimati
F. Eisenbrand, F. Grandoni, T. Rothvoß, G. Schäfer.
Approximating connected facility location problems via random
facility sampling and core detouring. Proc. SODA 2008 [Talk
domani 12:00]
A. Berger, V. Bonifaci, F. Grandoni, G. Schäfer. Budgeted
Matching and Budgeted Matroid Intersection Via the Gasoline
Puzzle. Proc. IPCO 2008
F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski,
M. Singh. Set Covering with our Eyes Closed. Proc. FOCS 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 2 (4/5)
Risultato: Modellazione spaziale del traffico in presenza di
memoria lunga, per validazione algoritmi di instradamento
L. De Giovanni, M. Naldi. Tests of correlation among wavelet-based estimates
for long memory processes. Communications in Statistics: Simulation and
Computation, 2008
P. L. Conti, L. De Giovanni, M. Naldi. Blind maximum-likelihood estimation of
traffic matrices in long range dependent traffic. International Workshop on
Traffic Management and Traffic Engineering for the Future Internet (FITraMEn
08)
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 2 (5/5)
Risultato: Individuazione di cluster di traffico mediante
tecniche spettrali
M. Naldi, A. Miani. Traffic matrix-based spectral decomposition of networks.
International Workshop on Traffic Management and Traffic Engineering for the
Future Internet (FITraMEn 08)
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 3 (1/4)
Risultato: Tool di visualizzazione MOM (Matched Oneto-Many graphs) [talk di Pietro Palladino oggi 17:30 ]
uses multiplanes views
works with graphs with thousands of vertices
was extensively tested
E. Di Giacomo, W. Didimo, G. Liotta, P. Palladino. Visual Analysis of
One-To-Many Matched Graphs. GD 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 3 (2/4)
Risultato: paradigmi di visualizzazione per l’analisi di
reti sociali (matched drawings, multiplane views,
circular views etc)
Di Giacomo, Didimo, van Kreveld, Liotta, Speckmann, Matched Drawings of
Planar Graphs. GD 2007 and JGAA to appear
Grilli, Hong, Liotta, Meijer, Wismath. Matched Drawability of Graph Pairs
and of Graph Triples. WALCOM '09
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 3 (3/4)
Risultato: paradigmi di visualizzazione per l’analisi di
reti sociali (matched drawings, multiplane views,
circular views etc)
Giordano, Liotta, Whitesides. Embeddability
Problems for Upward Planar Digraphs. GD 2008
Dujmovic, Fellows, Kitching, Liotta, McCartin, Nishimura, Ragde,
Rosamond, Whitesides, Wood. On the Parameterized Complexity of Layered
Graph Drawing. Algorithmica, 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Unità di Roma 3 (4/4)
Risultato: Sviluppo di un Web meta-search clustering
engine basato su una interfaccia basata su grafi.
Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, Pietro
Palladino, WhatsOnWeb+, An Enhanced Visual Search Clustering
Engine , IEEE Pacific Visualization Symposium 2008
Task 2.2 – Grafi e reti di grandi dimensioni
Risultati parziali attesi della fase 2 (da proposal)
Instradamento e broadcasting nelle reti (RM1, RM2, Pisa):
Analisi sperimentale algoritmi cammini minimi dinamici in
memoria esterna (RM1, RM2)
Simulazione del protocollo distribuito per il calcolo dell'albero di
copertura di rimpiazzo (Pisa)
Analisi visuale di reti (RM3):
Sviluppo di un sistema di analisi visuale di reti sociali
Studio di paradigmi di visualizzazione per l’analisi di reti sociali
Analisi sperimentale dei sistemi sviluppati con utenti finali
Task 2.3
Problemi computazionali di grandi dimensioni
Task 2.3 – Problemi computazionali di grandi
dimensioni
Unità di Roma 1
Risultato: Algoritmo combinatorio efficiente per la
simulazione di alluvioni in terreni digitali
sperimentazione su sistemi GIS e confronto con tecniche numeriche
Camil Demetrescu, Irene Finocchi, Torben Hagerup. Efficient Terrain Flooding,
Technical Report, 2008.
(Roma 1 non era coinvolta originariamente in questo task, ma i risultati riportati
sembrano pertinenti)
Task 2.3 – Problemi computazionali di grandi
dimensioni
Unità di Padova
Risultato: Introduzione adattività alla piattaforma in
solutore parallelo FEMS per grandi sistemi lineari.
Microbenchmarking in fase di istallazione per il tuning della
strategia di load-balancing model-driven
Alberto Bertoldo, Mauro Bianco, Geppino Pucci. FEMS: a Static Parallel Solver
for Finite Element Applications. Submitted to IEEE Transactions on Parallel and
Distributed Computing.
FEMS library (GNU LGPL): http://verona.dei.unipd.it/fems/
Task 2.3 – Problemi computazionali di grandi
dimensioni
Risultati parziali attesi della fase 2 (da proposal)
Solutore parallelo adattivo per mesh strutturate agli
elementi finiti (Padova)
Ci hanno dedicato un film…
The Wave
“The terrifying experiment
that went out of control”
(da Settembre nei cinema)
The terrifying experiment that went out of control