A survey on self‐organized semantic storage <s> GridVine <s> GridVine is a semantic overlay infrastructure based on a peer-to-peer (P2P) access structure. Built following the principle of data independence, it separates a logical layer - in which data, schemas, and schema mappings are managed - from a physical layer consisting of a structured P2P network supporting decentralized indexing, key load-balancing, and efficient routing. The system is decentralized, yet fosters semantic interoperability through pair-wise schema mappings and query reformulation. GridVine's heterogeneous but semantically related information sources can be queried transparently using iterative query reformulation. The authors discuss a reference implementation of the system and several mechanisms for resolving queries collaboratively. <s> BIB001 </s> A survey on self‐organized semantic storage <s> GridVine <s> Scalable distributed semantic storage infrastructures are hard to realize. We propose the usage of principles of selforganization for the storage and retrieval of RDF triples. We use a biology-inspired algorithm for clustering of triples based on a purely syntactical similarity measure. <s> BIB002 </s> A survey on self‐organized semantic storage <s> GridVine <s> Traditional approaches for data storage and analysis are facing their limits when handling the enormous data amounts of today's applications. We believe that a radical departure from contemporary architectures of stores is necessary to satisfy that central scalability requirement. One of the most promising new schools of thought in system design are swarm intelligent and swarm-based approaches for data distribution and organization. In this paper, we describe our current work on a swarm-based storage service for Semantic Web data. This storage service utilizes algorithms discovered in the behavior of ant colonies. We describe these algorithms and our enhancements to them as well as our evaluation of the implementation. <s> BIB003 </s> A survey on self‐organized semantic storage <s> GridVine <s> In many systems providing storage and retrieval operations on data, indices are used to make these operations more efficient. Distributed storage systems provide means to distribute the burden of storing and retrieving data onto multiple different computers. Routing indices can answer the central question in these systems: Where should one look for a specified data item? To be able to query for different columns in a relation or different entries in tuples, indexing for multiple dimensions is necessary. Our group applies a swarm-based approach to distributed storage leading to a new class of distributed systems, which are fully self-organized in their behavior and lack any shared global data structures. In this paper, we research whether multiple levels of routing indices can be maintained and used in such a distributed and self-organized storage service. To achieve this, we look into different types of indices and evaluate them in an experiment. <s> BIB004
GridVine is a distributed semantic storage system built as an overlay over an arbitrary structured P2P network BIB001 . Every node that is part of this P2P network participates in the storage of new data, thus increasing the capacity of the storage system becomes a trivial task. GridVine is built on top the P-Grid P2P system, which also uses a prefix tree similar to tapestry, but also includes several enhancements aimed towards self-organization: Within P-Grid, the prefix a node is responsible for is determined by a decentralized process determining if a change of responsibilities would be justified . This enables the P2P network to adapt to the actual distribution of the data object within the employed hash function's result space. The used overlay network structure is already shown in Figure 2 . Insertion of new triples into the distributed storage system can be performed on any node that is part of the P2P network. In order to enable other nodes to find triples by any of its entries, the object is added to the distributed index structure three times, once for each triple entry. Query operations can now translate triple patterns to P2P lookup operations, which statistically complete within logarithmic time. To achieve independence from node failures, a dynamic replication scheme samples the storage network to detect deviations from the desired replication level and then acts accordingly. Of course, if stored triples are changed, the replicated copies have to be located and updated as well, however, P-Grid supports a de-centralized mechanism based on rumor spreading for this task . GridVine also handles schemata, which describe the classes and properties used in the stored RDF graphs, these schemata can also be inserted into the storage layer, making them easily accessible to all nodes. Graphs using different schemata can be queried together, if a schema mapping has been defined. GridVine also supports the storage of these mappings, which can then be used on every node. Through the usage of the advanced and self-organizing P-Grid infrastructure, GridVine avoids the issue of the uneven distribution of storage load, and thus scales very well with additional data to be stored as well as allows the system to adapt to changing properties of the stored data. The three-fold indexing requires no message flooding for query purposes. However, the issue of uneven popularity of data items still poses an issue: for example, nodes unfortunate enough to be responsible for heavily used properties still can become hot points and thus hinder scalability. 4.6 The self-organized semantic storage service The self-organized semantic storage service (S4) uses an entirely different approach for the organization of its distributed storage network: Here, the foraging and brood sorting methods used by several ant species is used to implement a distributed storage system BIB003 BIB004 BIB002 . Ant colonies are able to coordinate to millions of individuals without any central control, are able to adapt to changing environments, and can handle issues -e.g. ants being eaten -without affecting the rest of the colony. Foraging ants on the search for food start-off on a random walk from their nest, as soon as they encounter food, they return to the nest, leaving a pheromone path on the ground. Other ants on the search for food are now inclinedalbeit not forced -to follow this path. Operations further increase pheromone values if they are successful as well. At any points, ants may also leave this path, enabling the discovery of new food sources. This algorithm has been shown to be able to create near-optimal solutions for hard combinatorial problems in affordable time. The adaption of these algorithms to distributed storage aims at also carrying these properties over, data items are modeled as the ant's food carrying a distinctive scent, and the storage network of interconnected nodes is their landscape. While S4 was designed to store tuples of arbitrary length, the storage of RDF triples is possible and was one of its use cases. The overlay network structure of nodes connected to other nodes provides a virtual landscape, on which single storage and retrieval operations can move around. Operations are routed over multiple nodes according to distinct pheromone values present on the network connections, and successful operations trace back the path taken through the network, increasing the corresponding pheromone value. This represents a positive enforcement mechanism, converging on the shortest possible path from the node where a request was issued to the node storing the relevant data items over multiple consecutive requests. While it was shown that the described concept has a very high-success rate, a small percentage of requests will not reach their destinations, effectively accepting a trade-off between efficiency and correctness. This concept is shown in Figure 4 : if a request to locate a data item #B stored on the node S3 is sent to node S2, this node can make a stochastic routing decision based on the pheromones present. In the example, the probability to route the request to S1 rather than to S5 is higher, since only one further hop will be required. On S1, the process is repeated, this time yielding an even higher probability. These values can be calculated at any node in the network, enabling routing all requests to their destination. The second swarm concept used in S4 is the so-called "brood sorting", which is used by ants to organize their brood within their nest. Again, without any central organization, larvae in similar stages of development are placed near to each other, making caring for them a simpler task. The same concept is applied to the stored tuples in S4, according to an arbitrary similarity measure, tuples are clustered together into a limited number of clusters, making storage operations far more efficient. Contrary to DHTs, the strictness of the global law governing the possible locations of data items is reduced, allowing the system for example to move data items in order to reach a even storage load distribution. The same property also allows the movement Self-organized semantic storage of over-popular data items to nodes with lesser load, making effective query load leveling possible. Should nodes fail or join the network, no re-organization of the stored data is necessary, since the swarm of queries will quickly form new paths around the failing nodes or include new nodes into the tasks of storing data and query answering.