Ebook: Databases, Information Systems, and Peer-to-Peer Computing: International Workshops, DBISP2P 2005/2006, Trondheim, Norway, August 28-29, 2005, Seoul, Korea, September 11, 2006, Revised Selected Papers

The aim of the International Workshop on Databases, Information Systems and P2P Computing was to explore the promise of P2P to o?er exciting new p- sibilities in distributed 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 infor- tion, veri?cation and certi?cation of information, content distributed schemes and quality of content, security features, information discovery and accessib- ity, interoperation and composition of active information services, and ?nally market-based mechanisms to allow cooperative and noncooperative information exchanges. The P2P paradigm lends itself to constructing large-scale, complex, adaptive, autonomous 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, sci- ti?c or otherwise) and on the emergence and the formation of social communities, 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 combined with the increasingly small and powerful mobile devices and sensors poses new challenges as well as opp- tunities to the database community. Information becomes ubiquitous, highly distributed and accessible anywhere and at any time over highly dynamic, - stable networks with very severe constraints on the information management and processing capabilities.

---

This book constitutes the thoroughly refereed postproceedings of the 3rd and 4th International Workshop on Databases, Information Systems and Peer-to-Peer Computing, DBISP2P 2005 and DBISP2P 2006, held in Trondheim, Norway, in August 2005 and in Seoul, Korea, in September 2006, as satellite events of VLDB, the International Conference on Very Large Data Bases. Table of Contents Cover Databases, Information Systems, and Peer-to-Peer Computing, International Workshops, DBISP2P 2005/2006 Trondheim, Norway, August 28-29, 2005, Seoul, Korea, September 11, 2006, Revised Selected Papers ISBN-10 3540716602 ISBN-13 9783540716600 Preface Executive Committees Organizers of the Third Edition Organizers of the Fourth Edition Steering Committee Program Committee Additional Reviewers and Helpers Preceding Editions of DBISP2P Table of Contents Third Edition Knowledge Discovery and Emergent Semantics Query Answering and Overlay Communities Indexing, Caching and Replication Techniques Complex Query Processing and Routing Semantic Overlay Networks Services, Agents and Communities of Interest Fourth Edition Invited Talk Data Placement and Searching Semantic Search Query Processing and Workload Balancing Continuous Queries and P2P Computing Galois Connections, T-CUBES, and P2P Data Mining 1 Introduction 2 Galois Connections 3 Multi-valued Galois Connections 4 T-CUBES 5 T-CUBE Evaluation 5.1 Database Heritage 5.2 Concept Analysis Heritage 6 Conclusion References Querying a Super-Peer in a Schema-Based Super-Peer Network 1 Introduction 1.1 SEWASIE Architecture 2 The SEWASIE System 3 Query Reformulation in the SEWASIE System 3.1 Query Unfolding 3.2 An Agent-Based Prototype for Query Processing 4 Conclusion and Future Work References Database Selection and Result Merging in P2P Web Search 1 Introduction 2 Related Work 2.1 P2P Search Platforms 2.2 Database Selection 2.3 Result Merging 3 Pseudo-relevance Feedback for Distributed IR 3.1 Database Selection 3.2 Result Merging 4 Experiments 4.1 Experimental Setup 4.2 Database Selection Experiments 4.3 Result Merging Experiments 5 Conclusion and Future Work Acknowledgment References Multiple Dynamic Overlay Communities and Inter-space Routing 1 Introduction 2 Related Work 3 Multiple DHT-P2P Spaces 3.1 Creating Multiple Spaces 3.2 Linking Multiple Spaces 4 Inter-space Routing Policies 4.1 Chord Routing and Broadcasting 4.2 Strategies with No State Overhead 4.3 Strategies with Extensive State Overhead 4.4 Gateway-Based Strategies 4.5 Caching-Based Strategies 5 ComparativeAnalysis 6 Conclusions and Future Work References Benefit and Cost of Query Answering in PDMS 1 PDMS and Data Quality 2 PDMS and Completeness 2.1 Data Sources and Mappings in PDMS 2.2 Completeness of Data Sets 3 Query Planning and Completeness 3.1 PDMS Query Planning 3.2 Completeness of Query Plans 4 Pruning Subplans 5 Experiments 6 Related Work 7 Conclusions References Cooperative Prefetching Strategies for Mobile Peers in a Broadcast Environment 1 Introduction 2 System Model and Assumptions 2.1 System Model 2.2 PT heuristic and Assumptions 3 Announcement-Based Cooperative Prefetching (ACP) 3.1 Deciding Whether to Send Out Announcement 3.2 Making Final Decision 3.3 Answering Queries Cooperatively 4 Simulation Model 5 Experiments and Results 5.1 Effect of Cache Size 5.2 Effect of Overlap 5.3 Effect of Skewness . 5.4 Effect of Transmission Range 5.5 Effect of Move Speed 5.6 Effect of Data Size 6 Conclusion References Symmetric Replication for Structured Peer-to-Peer Systems 1 Introduction 2 Preliminaries 3 Major Existing Replication Schemes 4 The Symmetric Replication Scheme 5 Exploiting Symmetric Replication 6 Evaluation 7 Related Work 8 Conclusions References A Gradient Topology for Master-Slave Replication in Peer-to-Peer Environments 1 Introduction 2 Peer Utility Metrics 3 Gradient Topology 4 Neighbour Selection Algorithm 5 Replication Strategy 5.1 Replica Placement 5.2 Replica Synchronisation 5.3 Master Election 5.4 Replica Discovery 6 Evaluation 7 Related Work 8 Conclusions and Future Work References A Content-Addressable Network for Similarity Search in Metric Spaces 1 Introduction 2 Background 2.1 Content-Addressable Network (CAN) 2.2 Metric Spaces 2.3 Pivot-Based Filtering 3 MCAN 3.1 Notation 3.3 Insertion 4 Performance Evaluation 4.1 Range Query 5 Related Work and Conclusions References Range Query Optimization Leveraging Peer Heterogeneity in DHT Data Networks 1 Introduction 2 Range Queries over DHTs 3 The RangeGuard 3.1 Node Performance Counters and the Node Performance Relation (NPR) 3.2 Joining the RangeGuard 3.3 Leaving the RangeGuard 3.4 Range Query Processing Using RGs 3.5 Modifcations to the LP-DHT Overlay 4 Load Distribution on the RG Ring 5 Performance Evaluation 5.1 Hop Count 5.2 Load Distribution 6 Related Work 7 Conclusions Acknowledgments References Guaranteeing Correctness of Lock-Free Range Queries over P2P Data 1 Introduction 2 Background 2.1 System Model 2.2 P-Ring 3 Query Correctness 3.1 Correct Query Results 3.2 Incorrect Query Results: Examples 4 A Simple Protocol 4.1 Range Ownership 4.2 Correct Range Queries 4.3 Incorrect Query Results Revisited 5 Extension to Simple Protocol 6 Conclusion References Publish/Subscribe with RDF Data over Large Structured Overlay Networks 1 Introduction 2 System Model and Data Model 3 A High-Level View of Our Algorithms 4 The Single Query Chain Algorithm 5 The Multiple Query Chains Algorithm 6 Experiments 7 Conclusions References A Semantic Information Retrieval Advertisement and Policy Based System for a P2P Network 1 Introduction 2 Basic Concepts 3 Architecture and Functionalities 4 Concluding Remarks References Cumulative Algebraic Signatures for Fast String Search, Protection Against Incidental Viewing andCorruptionofDatainanSDDS 1 Introduction 2 RecordEncoding 3 Searches 4 Performance 5 Protection Against Incidental Corruption 6 Protection Against Accidental Viewing 7 Related Work 8 Conclusions Acknowledgements References PARIS: A Peer-to-Peer Architecture for Large-Scale Semantic Data Integration 1 Introduction 2 SystemModel 3 Topology 4 Functional Architecture 4.1 Network Management 4.2 Query Processing 4.3 Mapping Management 5 Conclusion and Future Work References Processing Rank-Aware Queries in P2P Systems 1 Introduction 2 Multidimensional Routing Indexes Based on the QTree 2.1 Routing Indexes 2.2 QTree-Based Routing Indexes 3 Processing Multidimensional Top-N Queries 4 Skyline Queries 5 Conclusion References Semantic Caching in Schema-Based P2P-Networks 1 Introduction 2 Related Work 3 Semantic Caching in Super-Peer Networks 3.1 Answering Queries Using Semantic Caches 3.2 Cache Management Strategies in Edutella 3.3 Answering Queries in Edutella Using MiniCon 4 Simulation 4.1 Experimental Setup 4.2 Results 5 Summary and Future Work References Aggregation of a Term Vocabulary for P2P-IR: A DHT Stress Test 1 Introduction 2 Overview of Structured P2P Systems 3 Aggregation of Term Vocabulary 3.1 Usage Scenario 3.2 Blunt Message Handling 3.3 Splitting the Vocabulary into Blocks 3.4 Message Queuing 3.5 Avoiding Flooding 4 Experimental Results 5 Discussion 5.1 Redistribution of Aggregates 5.2 Fighting Malicious Peers 5.3 Updating Term Frequencies 5.4 Scaling It Up 6 Conclusions References Peer Group-Based Dependency Management in Service-Oriented Peer-to-Peer Architectures 1 Introduction 2 Related Work 3 TheDeEvolvePlatform 4 Dependency Analysis in DeEvolve 4.1 Registration of Consumer Dependencies 4.2 Adaptation Policy 4.3 Prototypical Implementation 5 Conclusion References LEAP-DB: A Mobile-Agent-Based Distributed DBMS Not Only for PDAs 1 Introduction 2 Databases on Mobile Devices and JADE-LEAP 3 LEAP-DB Design 4 Aspects of the Implementation 5 Conclusion References Models and Languages for Overlay Networks 1 Introduction 2 Node Views, the System Model 3 OverML, the XML Overlay Modelling Language 3.1 SLOSL, the View Specification Language 3.2 NALA, the Node Attribute Language 3.3 HIMDEL, the Hierarchical Message Description Language 4 Conclusion, Current and Future Work References A Peer-to-Peer Membership Notification Service 1 Introduction 2 SystemModel 3 MNSSpecification 3.1 Specification 3.2 Impossibility Results 4 A p2p MNS Implementation References Querying Communities of Interest in Peer Database Networks 1 Introduction 2 Querying Communities of Interest 2.1 Motivating Example and Preliminary Concepts 2.2 Community-Based Querying Algorithm 3 Implementation 3.1 System Architecture 3.2 Implementation and Experiments 4 Related Work 5 Conclusion and Future Work Acknowledgment References Middleware for Reliable Real-Time Sensor Data Management 1 Introduction 2 Data Management on Sensor Networks 2.1 Attribute-Based Queries 2.2 Spatial Queries 2.3 Top-K Queries 3 Middleware Components 3.1 In-Network Data Storage 3.2 Real-Time Data Dissemination 4 Related Work 5 Conclusions Acknowledgments References Oscar: Small-World Overlay for Realistic Key Distributions 1 Introduction 2 Background 3 Problems with Existing Solutions 4 Network Construction Using Scalable Sampling 4.1 The Insight and the Proposed Method 4.2 The Algorithms for Long-Range Link Construction 5 Simulations 6 Conclusions References Keyword Searching in Structured Overlays Via Content Distance Addressing 1 Introduction 2 A High Level Presentation 2.1 Hashing 2.2 Routing in Hypercube Graphs 2.3 Query Processing 2.4 Dataset Characterisation 3 Our Approach 3.1 Query Model 3.2 Summary Hash 3.3 Keyword Query Reduction 3.4 Keyword Edges and Emulation 3.5 Probing the Ball 4 Evaluation 4.1 Experimental Setup 4.2 Retrieval Performance and Data Placement 4.3 Performance 5 Related Work 6 Conclusion and Future Works References XML Query Routing in Structured P2P Systems 1 Introduction 2 System Functionality 3 Document Indexing 4 Data Placement and Query Processing 5 Handling Network Updates 6 Related Work 7 Performance Evaluation 8 Conclusion References Reusing Classical Query Rewriting in P2P Databases 1 Introduction 2 Query Similarity 2.1 Aspects of Query Similarity 2.2 Query Similarity Criteria 3 Query Reformulation 4 Conclusions and Future Work References Efficient Searching and Retrieval of Documents in PROSA 1 Introduction 2 PROSA: A Brief Description 2.1 Peer Joining PROSA 2.2 PROSA Dynamics 3 Information Retrieval in PROSA 3.1 Two Words About Simulations 3.2 Number of Retrieved Documents 3.3 Query Recall 4 Energetical Considerations 5 Conclusions and Future Work References P2P Query Reformulation over Both-As-View Data Transformation Rules 1 Introduction 2 Overview of BAV Data Integration 2.1 AutoMed's IQL Query Language 2.2 An Example 3 Query Reformulation over BAV Pathways 3.1 BAV Query Reformulation 4 Data Source Schema Query Processing 5 Concluding Remarks References RDFCube: A P2P-Based Three-Dimensional Index for Structural Joins on Distributed Triple Stores 1 Introduction 2 Our Proposed Approach 2.1 RDFCube: A Three-Dimensional Hash Space 2.2 RDFCube Construction 2.3 Query Processing with Join Operations 3 Performance Evaluation 3.1 Experiment Setup 3.2 Experiment Results 4 Conclusions References Optimal Caching for First-Order Query Load-Balancing in Decentralized Index Structures 1 Introduction 2 A Taxonomy of Replication 3 Replication and Search Cost 4 Optimal Query-Adaptivity 5 Optimal Replica Placement 6 Query Adaptive Replication 6.1 Numerical Evaluation 6.2 Simulations 7 Conclusion and Future Work References On Triple Dissemination, Forward-Chaining, and Load Balancing in DHT Based RDF Stores 1 Introduction 2 Related Work 3 RDFStorage 3.1 Life-Cycle of Triples 3.2 Node Departure 3.3 Node Arrival 3.4 RDFS Rules 4 Load Balancing 4.1 Overlay Tree 4.2 Compensation of Node Failure 4.3 Soft-State Updates 4.4 RDFS Rules 5 Conclusion References Priority Based Load Balancing in a Self-interested P2P Network 1 Introduction 2 Problem Definition 2.1 The Model 2.2 Possible Solutions 3 Priority Based Load Balancing 3.1 The Scheme 3.2 Finding Optimal Solution 3.3 Tuning Method 3.4 Implementation Issues 4 Experimental Evaluation 4.1 Initial Load Assignment 4.2 Load Assignment Tuning 5 Conclusion References A Self-organized P2P Network for an Efficient and Secure Content Location and Download 1 Introduction 2 System Description 2.1 Initializing and Joining the Network 2.2 Joining a Sub-group 2.3 SuperPeer Assignment 2.4 SuperPeers Maintenance 2.5 Registering the Shared Files 2.6 Searching for a Content 2.7 Additional Reliability 3 Performance Analysis 4 Related Works 5 Conclusions Acknowledgements References Query Coordination for Distributed Data Sharing in P2P Networks 1 Introduction 2 Problem Definiion 3 Coordination Engine Architecture 4 Application Example 5 Experimental Results 6 Conclusion References A Comparative Study of Pub/Sub Methods in Structured P2P Networks 1 Introduction 2 Related Work 3 SystemModel 3.1 Discussion 4 Design Patterns 4.1 Store-Sub 4.2 Store-Pub 5 Complexity Analysis 5.1 Store-Sub 5.2 Store-Pub 5.3 Discussion 6 Experiments 6.1 Analytical Results 6.2 Simulations 7 Conclusion and Future Work References Answering Constrained k-NN Queries in Unstructured P2P Systems 1 Introduction 2 Problem Definition 3 Pruning Candidate Peers 3.1 The Radius-Convergence Approach 3.2 The Radius-Expanding Approach 4 Experimental Study 5 Related Work 6 Conclusion References Scalable IPv4/IPv6 Transition: A Peer-to-Peer Based Approach 1 Introduction 2 Mechanism 3 ProtocolDesign 4 Analysis of P2P Network Connectivity 4.1 Single Node Destruction (SND) 4.2 Single Virtual Link Destruction (SVLD) 4.3 SND+SVLD 4.4 Influence of Node Number N 4.5 Summary 5 Prototype and Experiments 5.1 The Prototype 5.2 The Experiments 6 Conclusions References Author Index