Vai al contenuto| Home page|

   Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricerca
INIZIO_TESTO_DA_INDICIZZARE

RESEARCH PROGRAM

italiano - inglese
Research Units
Similar research programs:
Scientific and education field classification
International Patent Classification
Geographical classification
Bibliografia
[ACS87] A. Aggarwal, A. Chandra, M. Snir. Hierarchical Memory with Block transfer. Proc. FOCS, 1987

[ADRR04] G. Aggarwal, M. Datar, S. Rajagopalan, M. Ruhl. On the streaming model augmented with a sorting primitive. Proc. FOCS, 540-549, 2004

[AV88] A. Aggarwal, J.S. Vitter. The input/output complexity of sorting and related problems. Comm. ACM, 31(9):1116-1127, 1988

[ADM06] D.Ajwani, R. Dementiev, U. Meyer. A computational study of external-memory BFS algorithms. Proc. SODA, 601-610, 2006

[ADE01] P.R. Amestoy, I.S. Duff, J.Y. L'Excellent, X.S. Li. Analysis and comparison of two general sparse solvers for distributed memory computers, ACM Trans. Math. Softw., 27(4):388-421, 2001

[ABF05] L. Arge, G.S. Brodal, R. Fagerberg. Cache-oblivious data structures. Handb. Data Str. and Appl., 34, 2005

[AFI05] G. Ausiello, P.G. Franciosa and G.F. Italiano. Small Stretch Spanners on Dynamic Graphs. Proc. ESA, 2005

[B05] D.P. Bertsekas, Dynamic Programming and Optimal Control, Vol. 1, 3rd Ed., 2005

[B+03] M. Bianco, G. Bilardi, F. Pesavento, G. Pucci, B.A. Schrefler. A frontal solver tuned for fully-coupled non-linear hygro-thermo-mechanical problems. Int. J. Numer. Meth. in Eng., 57(13):1801-1818, 2003

[BEP02] G. Bilardi, K. Ekanadham, P. Pattnaik, Optimal organizations for pipelined hierarchical memories, Proc. SPAA, 109-116, 2002

[BP01] G. Bilardi, E. Peserico, A Characterization of Temporal Locality and Its Portability across Memory Hierarchies, Proc. ICALP, 128-139, 2001

[BF03] G.S. Brodal, R. Fagerberg. On the limits of cache-obliviousness. Proc. STOC, 307-315, 2003

[BW94] M. Burrows, D.J. Wheeler, A block-sorting lossless data compression algorithm, Res. Report 124, DSRC, 1994

[CMV05] B. Catania, A. Maddalena, A. Vakali. XML document indexes: a classification. IEEE Internet Comp., 2005

[CLGKP94] P. M. Chen, E. L. Lee, G. A. Gibson, R. H. Katz, D. A. Patterson. RAID: High-performance, reliable secondary storage. ACM Comp. Surv., 26(2):145-185, 1994

[CDPP05] P.F. Cortese, G. Di Battista, M. Patrignani, M. Pizzonia. Clustering Cycles into Cycles of Clusters, JGAA, 9:391-413, 2005

[DDFLPP99] C. Demetrescu, G. Di Battista, I. Finocchi, G. Liotta, M. Patrignani, M. Pizzonia: Infinite Trees and the Future. Proc. GD, 379-391, 1999

[DFIN02] C. Demetrescu, I. Finocchi, G.F. Italiano, and S. Naeher. Visualization in Algorithm Engineering: Tools and Techniques. In "Experim. Algorithmics, From Algorithm Design to Robust and Efficient Softw.", LNCS 2547, 2002

[DFR06] C. Demetrescu, I. Finocchi, and A. Ribichini. Trading off space for passes in graph streaming problems. Proc. SODA, 714-723, 2006

[DI04] C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. JACM, 51(6), 968-992, 2004

[DEG99] J.W. Demmel, S.C. Eisenstat, J.R. Gilbert, X.S. Li, J.W.H. Liu. A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. and App., 20(3):720-755, 1999

[DDGL05a] E. Di Giacomo, W. Didimo, L. Grilli, G. Liotta: WhatsOnWeb: Using Graph Drawing to Search the Web. Proc. GD, 480-491, 2005

[DDLM04] E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer: Computing Radial Drawings on the Minimum Number of Circles. Proc. GD, 251-261, 2004

[D59] E.W. Dijkstra. A note on two problems in connexion with graphs. Num. Mathematik, 1959

[FPP05] C. Fantozzi, A. Pietracaprina, G. Pucci. Translating Submachine Locality into Locality of Reference. JPDC S.I. IPDPS'04 Best Papers, 2005

[FPRU94] U. Feige, P. Raghavan, D. Peleg, E. Upfal. Computing with noisy information. SIAM J. Comp., 23:1001-1018, 1994

[FKMSZ04] J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang. On graph problems in a semi-streaming model. Proc. ICALP, 531-543, 2004

[FCE95] Q.W. Feng, R.F. Cohen, P. Eades. Planarity for Clustered Graphs. Proc. ESA, 213-226, 1995

[FLMM05] P. Ferragina, F. Luccio, G. Manzini, and S. Muthukrishnan. Structuring labeled trees for optimal succinctness, and beyond. FOCS, 2005

[FM05] P. Ferragina, G. Manzini. Indexing Compressed Text. JACM, 52:552-581, 2005

[FI04] I. Finocchi, G. F. Italiano. Sorting and searching in the presence of memory faults (without redundancy). Proc. STOC, 101-110, 2004

[FGMP02] G. Franceschini, R. Grossi, J. I. Munro, L. Pagli, Implicit B-trees: New results for the dictionary problem. Proc. FOCS and JCSS S.I., 145-154, 2003

[FJ98] M. Frigo, S. Johnson, FFTW: An adaptive software architecture for the FFT, Proc. ICASSP, 3:1381-1384, 1998

[FLPR99] M. Frigo, C.E. Leiserson, H. Prokop, S. Ramachandran. Cache-Oblivious Algorithms. Proc. FOCS, 285-297, 1999

[GLS05] M.T. Goodrich, G.S. Lueker, J.Z. Sun. C-planarity of extrovert clustered graphs. Proc. GD, 211-222, 2005

[GV05] R. Grossi, J.S. Vitter. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. SIAM J. Comp., 35(2):378-407, 2005.

[HEW98] M. L. Huang, P. Eades, J. Wang: On-line Animated Visualization of Huge Graphs using a Modified Spring Algorithm. J. Vis. Lang. and Comp., 9(6): 623-645, 1998.

[ISO89] International Standards Organization: "Intra-Domain IS-IS Routing Protocol", ISO-IEC JTC1/SC6 WG2N323, 1989

[K05] M. Kaki. Findex: search result categories help users when document ranking fails. Proc. CHI, 131-140, 2005

[K99] V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. Proc. FOCS, 1999

[LRP95] J. Lamping, R. Rao, P. Pirolli. A focus-context technique based on hyperbolic geometry for visualization large hierarchies. Proc. InterCHI, 401-408, 1995.

[MS00] L. Marsan and M.-F. Sagot, Algorithms for extracting structured motifs using a suffix tree with application to promoter and regulatory site consensus identification. J. Comp. Bio., 7:345-360, 2000.

[MZ03] U. Meyer, N. Zeh. I/O-efficient undirected shortest paths. Proc. ESA, 434-445, 2003

[M+02] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, U. Alon. Network motifs: simple building blocks of complex networks. Science 298(5594): 824-827, 2002

[M99] J. Moy, "OSPF: Anatomy of an Internet Routing Protocol", Addison-Wesley, 1999

[M05] S. Muthukrishnan. Data streams: algorithms and applications. http://athos.rutgers.edu/~muthu.

[NPW04] E. Nardelli, G. Proietti, and P. Widmayer. Nearly linear time minimum spanning tree maintenance for transient node failures. Algoritmica, 40:119-132, 2004

[PS05] N. Pisanti, M.F. Sagot: Inference of Network Expressions. In Applied Combinatorics on Words, 5:241-267, 2005

[PSWZ04] G. Prencipe, N. Santoro, P. Widmayer, T. Zuva. Computing all the Best Swap Edges Distributively. Proc. OPODIS, 2004, 154-168

[PZ03] A. Pietracaprina, D. Zandolin., Mining Frequent Itemsets using Patricia Tries, Proc. FIMI, 2003

[R+05] M. T. Ross et al., The DNA sequence of the human X chromosome Nature 434:325-337, 2005

[RMC91] G. G. Robertson, J.D. Mackinlay, S. K. Card, Cone trees: animated 3D visualizations of hierarchical information. Proc. CHI, 189-193, 1991

[R03] J. Ruhl. Efficient Algorithms for New Computational Models. PhD thesis, MIT, 2003

[SB94] M. Sarkar, M.H. Brown, Graphical fisheye views. Comm. of ACM, 37:73-84, 1994

[SGG05] A. Silberschatz, P.B. Galvin, G. Gagna. Operating Systems Concepts, 7th Edition, Wiley, 2005

[Vi01] J.S. Vitter. External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA, ACM Comp. Surv., 33(2):209-271, 2001

[WSS99] J.T.L.Wang and B.A. Shapiro and D. Shasha, Pattern Discovery in Biomolecular Data, Oxford University Press, 1999

[We05] S. Wernike: A faster algorithm for detecting network motifs. Proc. WABI, 1-12, 2005

[WPD01] R. Whaley, A. Petitet, J. Dongarra, Automated Empirical Optimization of Software and the ATLAS Project. Par. Comp., 27(1-2):3-35, 2001

[ZE99] O. Zamir and O. Etzioni. Grouper: a dynamic clustering interface to web search results. Comp. Networks, 31(11-16):1361-1374, 1999

[ZL77] J. Ziv, A. Lempel. A universal algorithm for sequential data compression, IEEE Tr. Inf. Theory, 23(3):337-343, 1977
Keywords
ALGORITHMS, DATA STRUCTURES, COMPLEX MEMORY SYSTEMS, EXTERNAL MEMORY, DATA COMPRESSION, GRAPHS, DATA VISUALIZATION

MAINSTREAM: Algorithms for massive information structures and data streams

Università degli Studi di Roma "La Sapienza"
Abstract
This research project brings together five leading groups in algorithmic research in Italy in a joint effort that aims at:

(1) Discovering new algorithmic techniques and methodologies for processing very large information structures;

(2) Identifying and solving key algorithmic problems in important applications that deal with massive data sets; and

(3) Contributing to the accelerated transfer of advanced algorithmic technologies through experiments and the engineering of efficient algorithmic code.

As a natural consequence of our methodological and application-oriented approach, the research plan is organized into two mutually related Work Parts (WP):

WP1 - COMPUTATIONAL MODELS AND ALGORITHMIC METHODOLOGIES

In this Work Part we will address a variety of computation models used for managing massive information structures, such as external memory models, hierarchical memory models, pipelined memories, faulty memories and data streaming. In particular we will study how algorithm design techniques and technological aspects of complex memory systems interact and adapt to each other. We also plan to study general algorithmic techniques such as compression and space-efficient data representation, general methods for storing and visualizing very large graphs, and pattern discovery techniques. Another goal will be to develop tools and >>>

Principal Investigator
Giorgio Ausiello Università degli Studi di ROMA "La Sapienza"
Research Objectives
During the last ten years the developments in computer applications have put more and more emphasis on the management of massive data sets, such as very long strings, huge collections of texts and documents, very large graphs and matrices, etc. The need for handling such data sets arises, for example, in bioinformatics, in meteorology, in the solution of challenging computational problems, in the exploration and visualization of very large computer networks (such as Internet) or social networks. For various reasons, designing efficient algorithms for dealing with huge information structures represents a major challenge. In most cases data are stored in external memory and we have to devise new algorithmic techniques for handling them minimizing disk accesses. Besides, in such circumstances, new techniques for compression and visualization are required. Note that in some cases data are so large that they cannot even fit in external memory but have to be analyzed 'on the fly'. Finally, when massive data are considered, new algorithms for dealing with faulty data are needed because error probability is not anymore negligible.

This research project brings together five leading groups in algorithmic research in Italy in a joint effort that aims at:

(1) Discovering new algorithmic techniques and methodologies for processing very large information structures;

(2) Identifying and solving key algorithmic problems >>>

Timescale
24 months
National and international background
In the following we will illustrate, for each task, the scientific background on which the project is based.

WP1 - COMPUTATIONAL MODELS AND ALGORITHMIC METHODOLOGIES

Task 1.1 - Complex memory systems

Contemporary computing platforms exhibit rather complex memory systems typically organized as a hierarchy of increasingly larger and slower memory levels. Adapting the structure of the computation to the structure of the memory system is crucial to performance, especially when massive data sets or streams are involved. Moreover, faults are likely to occur in large and complex memories, and suitable strategies must be adopted to guarantee the correctness of the computation. We summarize below recent results, relevant to the project goals, regarding adaptivity (at both algorithmic and virtual memory management levels) and fault-tolerant algorithms.

Algorithmic adaptivity

Two well known approaches for the design of adaptive algorithms in memory hierarchies are based on the External Memory (EM) (see [AV88]) and the Cache-Oblivious (CO) (see [FLPR99]) frameworks. Both frameworks are based on a two-level hierarchy model formed by a fast but small level and a large but slow level. Data blocks in the slow memory can only be accessed by first copying them into the fast memory, and the goal is to minimize copy operations. In the EM framework, parameters such >>>