Ebook: Databases, Information Systems, and Peer-to-Peer Computing: Second International Workshop, DBISP2P 2004, Toronto, Canada, August 29-30, 2004, Revised Selected Papers

Peer-to-peer (P2P) computing promises to o?er exciting new possibilities in d- tributed information processing and database technologies. The realization of this promise lies fundamentally in the availability of enhanced services such as structured ways for classifying and registering shared information, veri?cation and certi?cation of information, content-distributed schemes and quality of c- tent, security features, information discovery and accessibility, interoperation and composition of active information services, and ?nally market-based me- anisms to allow cooperative and non-cooperative information exchanges. The P2P paradigm lends itself to constructing large-scale complex, adaptive, - tonomous and heterogeneous database and information systems, endowed with clearly speci?ed and di?erential capabilities to negotiate, bargain, coordinate, and self-organize the information exchanges in large-scale networks. This vision will have a radical impact on the structure of complex organizations (business, scienti?c, or otherwise) and on the emergence and the formation of social c- munities, and on how the information is organized and processed. The P2P information paradigm naturally encompasses static and wireless connectivity, and static and mobile architectures. Wireless connectivity c- bined with the increasingly small and powerful mobile devices and sensors pose new challenges to as well as opportunities for the database community. Inf- mation becomes ubiquitous, highly distributed and accessible anywhere and at any time over highly dynamic, unstable networks with very severe constraints on the information management and processing capabilities.

---

This book constitutes the thoroughly refereed postproceedings of the Second International Workshop on Databases, Information Systems, and Peer-to-Peer Computing, DBISP2P 2004, held in Toronto, Canada in August 2004 in conjunction with VLDB 2004. The 14 revised full papers presented together with an invited keynote paper were carefully selected during two rounds of reviewing and improvement. The papers are organized in topical sections on query routing and processing, similarity search in P2P networks, adaptive P2P networks, and information sharing and optimization. Table of Contents Cover Databases, Information Systems, and Peer-to-Peer Computing, Second International Workshop, DBISP2P 2004, Toronto, Canada, August 29-30, 2004 Revised Selected Papers ISBN 3540252339 Preface Organization Program Chair Steering Committee Program Committee Sponsoring Institutions Table of Contents Keynote Address Query Routing and Processing Similarity Search in P2P Networks Adaptive P2P Networks Information Sharing and Optimization Data Management in Mobile Peer-to-Peer Networks1 1 Introduction 2 Data Model 2.1 Resource Model 2.2 Peers and Validity Reports 2.3 Reports Relations 2.4 Report Relevance 3 Data Dissemination 4 The Economic Model 4.1 Virtual Currency and the Security Module 4.2 Producer-Paid Reports 4.3 Consumer-Paid Reports 5 Query and Query Processing 5.1 Query Language 5.2 Query Processing 6 Information Usage Strategies and Transactional Issues 7 Relevant Work 8 Conclusion References On Using Histograms as Routing Indexes in Peer-to-Peer Systems 1 Introduction 2 Histograms in Peer-to-Peer Systems 2.1 Histograms as Routing Indexes 2.2 Using Histograms for Clustering 3 Query Routing and Network Construction 3.1 Query Routing 3.2 Clustering 4 Experimental Results 4.1 Histogram Distance Metrics 4.2 Cluster Quality 4.3 Query Routing 5 Related Work 6 Conclusions and Future Work References Appendix Processing and Optimization of Complex Queries in Schema-Based P2P-Networks 1 Introduction and Motivation 2 Distributed Routing Indices 3 Plan Generation, Distribution and Optimization 3.1 Distributed Plan Generation 3.2 Query Optimization 4 Implementation 5 Conclusion and Further Work References Using Information Retrieval Techniques to Route Queries in an InfoBeacons Network 1 Introduction 2 Routing Queries to Information Sources 3 Routing Queries Between Beacons 4 Experimental Results 4.1 Experimental Setup 4.2 Routing Queries Between Information Sources 4.3 Beacon Network Topologies in the Flat Architecture 4.4 Routing Queries Between Beacons 5 Related Work 6 Conclusions and Future Work References Content-Based Similarity Search over Peer-to-Peer Systems 1 Introduction 2 Background 2.1 Vector Space Model (VSM) 2.2 Latent Semantic Indexing (LSI) i=1 Bi 2.3 Chord 3 Document Distribution Model 3.1 Computing Document Vectors 3.2 Publishing Documents 3.3 Query Lookup 4 Load Balancing in the System 4.1 Multi-level Reference Sets 4.2 Load Aware Peer Joins 5 Experimental Results 5.1 Experimental Setup 5.2 Results Without Load Balancing 5.3 Results with Load Balancing 5.4 Discussion 6 Conclusion References A Scalable Nearest Neighbor Search in P2P Systems 1 Introduction 2 Metric Space and Similarity Queries 3 Principles of GHT* 3.1 Architecture of GHT* 3.2 Address Search Tree 3.3 Insert and Range Search Algorithms 4 Searching for Nearest Neighbors 4.1 kNN Search in GHT* 4.2 kNN Algorithm 4.3 Implementation Issues 5 Performance Evaluation 5.1 Performance Characteristics 5.2 kNN Search Performance 5.3 kNN Search Scalability 6 Conclusions References Efficient Range Queries and Fast Lookup Services for Scalable P2P Networks 1 Introduction 2 Related Work 3 System Architecture 3.1 Join 3.2 Leave 3.3 Insertion 3.4 Deletion 3.5 Search Query 4 Performance Analysis 4.1 Performance Measure 4.2 Experimental Setting 4.3 Joining Mechanism 5 Conclusion and Future Work Acknowledgement References The Design of PIRS, a Peer-to-Peer Information Retrieval System 1 Introduction 2 Limits of Current Work in P2P Information Retrieval 2.1 Characteristics of P2P Systems 2.2 The Limits of Information Retrieval Using Web Search Engines 2.3 Current Peer-to-Peer Information Retrieval Systems and Their Limits 3 Model 4 The Design of PIRS 4.1 Goals 4.2 Overview 4.3 Metadata Collection 4.4 Metadata Distribution 4.5 Metadata Use 4.6 Implementation Issues 5 Experimental Results 5.1 The Simulator 5.2 Results for Various Combinations of Metadata Distribution and Ranking 6 Discussion 6.1 Compatibility with Existing Technologies 6.2 The Outlook for Peer-to-Peer Information Retrieval 7 Conclusion References Adapting the Content Native Space for Load Balanced Indexing 1 Introduction 2 Related Work 3 ZNet 3.1 Space Partitioning and Mapping 3.2 Query Routing and Resolving 3.3 Node Join and Leave 3.4 Load Balancing 4 Experimental Results 4.1 Load Balancing 4.2 Average Lookup Cost 4.3 Range Search Cost 5 Conclusion References On Constructing Internet-Scale P2P Information Retrieval Systems 1 Introduction 2 Search Techniques for Unstructured P2P Networks 3 Overlay Topologies for E.cient Network Utilization 4 Experimental Evaluation Methodology 5 Experiments 6 Conclusions and Future Work References AESOP: Altruism-Endowed Self-organizing Peers 1 Introduction 1.1 Our Perspectives and Position Real-World Perspective. Our starting position is that our world consists of altruists, 2 PLANES: Altruists to the Rescue 2.1 Architecting Layered, Altruism-Based P2P Networks 2.2 PLANES Algorithms Routing. The routing algorithm is called at a node with srcNodeId, requesting docId, 2.3 Performance of Routing in PLANES 2.4 PLANES Architecture Extensions 3 AltSeAl: Altruism Sealed 3.1 The Monitoring/Accounting Layer 3.2 Favors and Complaints 3.3 SeAled PLANES: AltSeAl and AltNets 4 The Performance of AltSeAl 4.1 Experimental Setup 5 Conclusions References Search Tree Patterns for Mobile and Distributed XML Processing 1 Introduction 2 Motivation 2.1 Brief Introduction into the Concept and Terminology 2.2 Overview and Scenario 2.3 Segmentation Caching in Peer-to-Peer Environments 2.4 Expected Behavior in Peer-to-Peer Environments 3 Framework for ST-Patterns 3.1 Formal Framework 3.2 DTD Trees 3.3 XML Data Model 3.4 ST-Patterns 3.5 Pattern Fragments: Answers to ST-Pattern 4 Properties and Operations on ST-Patterns 4.1 Expansion and Compression of ST-Patterns 5 Evaluating ST-Patterns 5.1 Node Matching for ST-Patterns 5.2 Node Matching as Basic ST-Patterns Algorithm 5.3 Processing of ST-Patterns 6 Data Processing Based on ST-Patterns 6.1 Choice of the ST-Pattern Set 6.2 Use of ST-Patterns in the Caching Scenario 6.3 Properties of Pattern Operations 7 Related Work 8 Summary and Conclusions References Dissemination of Spatial-Temporal Information in Mobile Networks with Hotspots1 1 Introduction 2 System Architecture 2.1 Resource Model 2.2 Peers and Validity Reports 2.3 Relevance Model 2.4 Peer-to-Peer Report Exchange 3 Benefit of Report Dissemination 3.1 Resource Discovery Strategies 3.2 Comparison of Resource Discovery Strategies 4 Relevant Work 5 Conclusion References Wayfinder Navigating and Sharing Information in a Decentralized World 1 Introduction 2 Background: PlanetP 3 Files and Directories 4 Consistency 5 Performance 6 Related Work 7 Conclusions and Future Work References CISS: An Efficient Object Clustering Framework for DHT-Based Peer-to-Peer Applications 1 Introduction 2 Related Work 3 System Architecture 4 Technical Issues 4.1 Locality Preserving Function (LPF) 4.2 Efficient Routing Protocols for Data Updates and Multi-dimensional Range Queries 4.3 Cluster-Preserving Load Balancing 5 Experiments 5.1 Data Update Performance 5.2 Multi-dimensional Range Query Performance 6 Conclusion and Future Work References Author Index