Carleton Scientific 2006-05-22

Distributed Data and Structures Records of the 5th International Meeting Introduction Distributed data structures have attracted systematic research from both practical and theoretical points of view: in the database field, dynamic structures for distributed data accommodation have been developed, while in the algorithms literature, the time and space complexity of distributing structuring schemes, or dictionaries as they are widely known, has been studied. However, in the last years, due to rapid evolution of network technology, the technological framework known as network computing emerged; this novel environment imposes new constraints to the design and implementation of distributed algorithms and manipulation of distributed data. Of course, advances in the domain are fundamental to performance, integrity and scalability of various types of storage and database systems, as well as to emergence of P2P and of Grid Computing Systems. The Workshop on Distributed Data and Structures (WDAS) series was initiated by the need to bring together computer scientists interested in distributed data and structures in the constantly expanding net-centric “surroundings.” The workshops examine the state of the art in the areas of: fundamental theoretical advances, i.e., complexity analysis; access methods and algorithms; programming languages; architecture; and prototypes and applications The fifth WDAS was held in Thessaloniki, Greece, on 13-14 June 2003. Previous workshops took place in Orlando (1998), Princeton (1999), L’Aquilla (2000) and Paris (2002). The workshop was successful in providing presentations of ongoing work, while offering the opportunity and time to discuss, analyze, and characterize facets of the field. Prof. Manolis Koumbarakis opened the workshop with a keynote address on “Information Dissemination in P2P Networks: Data Models, Algorithms and Implementation Techniques.” This volume is based entirely on the talks, discussions, and results of the meeting. The WDAS’03 program included 13 presentations. The topics concern: (a) Signature and Bloom Files; (b) Distributed Hashing Schemes; (c) Distributed Multidimesional Indexes; (d) P2P and Grid Computing Systems; and (e) Load Balancing and Service Oriented Distributed Architectures. WDAS’03 was organized with the kind and generous support of (a) the Research Committee of the Aristotle University of Thessaloniki, and (b) the CITY College of Liberal Studies. The members of the Data Engineering Laboratory of the Department of Informatics of Aristotle University — in particular, Dimitrios Katsaros and Antonios Sidiropoulos — are greatly acknowledged for their help and efforts in organizing this meeting. Yannis Manolopoulos, Aristotle University of Thessaloniki Program Committee Yannis Manolopoulos, Aristotle University, Chair Karl Aberer, EPFL Lausanne Michael Adiba, University Joseph Fourier – IMAG Paris Yuri Breitbart, Bell Labs Witold Litwin, University Paris 9, Dauphine Fabrizio Luccio, University of Pisa Enrico Nardelli, University of L’Aquila Panayiotis Bozanis, University of Thessaly Gerard Levy, University Paris 9, Dauphine Tore Risch, University of Uppsala Maya Satratzemi, University of Macedonia Thomas Schwartz, University of Santa Clara Paul Spyrakis, University of Patras Witold Staniszkis, Rodan Warsaw Ugo Vaccaro, University of Salerno Patrick Valduriez, INRIA, Paris Peter Widmayer, ETHZ Zurich Organizing Committee Petros Kefalas, CITY College, Chair George Evangelidis, University of Macedonia Yorgos Grigoriadis, Aristotle University Yannis Karydis, Aristotle University Dimitris Katsaros, Aristotle University Apostolos Papadopoulos, Aristotle University Katerina Raptopoulou, Aristotle University Antonis Sidiropoulos, Aristotle University Michael Vassilakopoulos, Technology Educational Institute of Thessaloniki Table of Contents Yannis Manolopoulos Introduction Adriano Di Pasquale, Enrico Nardelli, &38; Guido Proietti An RP* Extension with Almost Constant Amortized Costs Mianakindila Tsangou, Samba Ndiaye, Mouhamed T. Seck, &38; Witold Litwin Range Queries to Scalable Distributed Data Structure RP* C. Raibulet &38; C. Demartini Toward Service Oriented Distributed Architectures Cécile Le Pape, Stéphane Gançarski, &38; Patrick Valduriez Trading Freshness for Performance in a Cluster of Replicated Databases G. Cordasco, A. Negro, V. Scarano, &38; A.L. Rosenberg $c$-Perfect Hashing Schemes for Arrays, with Applications to Parallel Memories K. Aberer, M. Hauswirth, &38; M. Punceva Self-organized Construction of Distributed Access Structures: A Comparative Evaluation of P-Grid and Freenet Djamel-Eddine Zegour Adaptation of Trie Hashing for Distributed Environments Panayiotis Bozanis Accommodating $k$-d Trees in the SDDS Model M. Batko, C. Gennaro, &38; P. Zezula Scalable and Distributed Similarity Search in Metric Spaces W. Litwin &38; T. Schwarz Algebraic Signatures for Scalable Distributed Data Structures R. Mokadem, W. Litwin, &38; T. Schwarz Disk Backup through Algebraic Signatures in Scalable and Distributed Data Structures G. Koloniari &38; E. Pitoura Bloom-Based Filters for Hierarchical Data F. Baklouti &38; G. Lévy Parallel Algorithms for General Galois Lattices Building