Distributed Data and Structures Records of the 1st International Meeting Introduction This volume contains the records of the 3rd research workshop on Distributed Data and Structures. Currently, the research on distributed data structures is carried out in many fields, from parallel systems to distributed computing, from AI to GIS. Their systematic design and analysis has just started: in the database literature, dynamic file structures for distributed object management have attracted some attention, and in the algorithms literature, data structures have been studied from a complexity oriented point of view. However, this research is mostly "hidden", relegated to the side of each field, obscured by the weight of the application domain, especially in databases but also in the algorithms community. In fact, there is not even a definitive acceptance of its existence as a research field. This is surprising, especially in the light of the following two important developments. As databases are growing steadily, applications become more and more demanding, and distributed computer systems are becoming rather easily available, the problem of how to efficiently maintain large datasets gains importance. An important aspect of this problem is the design, implementation, and operation of a data structure in a distributed system. At the same time, in the constantly expanding net-centric universe, an increasing amount of data is available, distributed among sites. The structuring of the data for accessing, manipulation and processing is a crucial task which can ultimately affect the performance, integrity and usefulness of the entire system. These two developments bring the research on distributed data and structures at the forefront. The absence of a specific focus on this subject is an anomaly in the status of the current research efforts; at the same time, this situation opens an exceptional opportunity for researchers. This 3rd edition of the workshop was held in L'Aquila, Italy, in conjunction with SIROCCO 2000, the 7th International Colloquium on Structural Information and Communication Complexity. The purpose of this workshop has been to bring together application-oriented developers and theoretical researchers concerned with the maintenance of distributed data and the organization of the interaction between the computing nodes. The workshop has been successful in both respects. It comprised both formal presentations, whose goal was to give a picture of some aspects of the field, and open time and space to discuss, analyze, and characterize the many facets of the field. The topics covered include: design, implementation and operation of distributed data structures in general; measures of efficiency for distributed data structures; complexity analysis (lower and upper bounds) for distributed data structures; connection between distributed data maintenance and mobile data maintenance; connection between the interaction structure of the nodes and the data maintenance; This volume is based entirely on the talks, discussions, and results of the meeting. Its small size is due to the fact that most of the contributions came as discussion and have not yet found their form as a written text. Still, we hope this volume will convey to the reader at least part of interest, excitement and visions experienced by the participants. We are confident it will provide useful tools for a unified view of this emerging research area, so important from both an applicative and a theoretical viewpoint. We would like to thank: all the participants to the meeting for their enthusiasm and contributions; all the researchers who, although unable to attend, have expressed their strong support for the workshop goals and future; Luca Forlizzi, Michele Flammini and Guido Proietti for the excellent organizational work; and Steve Izma of Carleton Scientific for the unusual editorial effort. We also gratefully acknowledge the organizational and financial support of: University of L'Aquila, CHOROCHRONOS: A Research Network on Spatio-Temporal Database Systems (EU-TMR Grant ERB-FMR-XCT-960056), the Italian National Research Council, the I-CUBO association for the advancement of Computer Science in the society. Adriano Di Pasquale, Fabrizio Luccio, and Enrico Nardelli Table of Contents Adriano Di Pasquale, Fabrizio Luccio, & Enrico Nardelli Introduction Panayiotis Bozanis & Yannis Manolopoulos DSL: Accommodating Skip Lists in the SDDS Model L. Flores Pacheco, G. Franceschini, F. Luccio, & L. Pagli Decomposition of k-Dense Trees W. Litwin, J. Menon Scalable Distributed Log Structured Arrays Y. Ndiaye, A. W. Diene, W. Litwin, & T. Risch Scalable Distributed Data Structures for High-Performance Databases Adriano Di Pasquale & Enrico Nardelli An Amortized Lower Bound for Distributed Searching of k-dimensional Data Adriano Di Pasquale & Enrico Nardelli Scalable Distributed Data Structures: A Survey