?
Exact Search with Small World Data Structure for One Dimensional Metric Space
The ability to scale is desirable in computer system as well as business settings. The distributed systems clearly demonstrate this ability and powerfulness to process a very big amount of data. Many system that have distributed architecture like Hadoop file system or distributed torrent tracker are based on the distribute hash table (DHT) which manages the set of distributed network nodes connected not only by the physical channel but connected by the additional overlay network. This overlay network is used for searching nodes and for distributing tasks among them. The main feature of this approach is that there is no central element or node which knows the global topology of the network. Search of nodes in the network performed by passing query messages from on node to other. Despite that every node has knowledge only about the small number of other nodes, the network organized so that the search involves logarithmical number of nodes.
There are several DHT implementations which specify how to construct and support the structure of the network. In this paper we demonstrate how this network can be constructed very easily by applying the sight modification of the recently published Metrized Small World algorithm to case of one dimensional.
Also we suggest how to completely separate the concept of network location of the data from the search functionality. This separation is important, for an instance, for building global storages where data is owned by multiple parties and each party is interested in keeping control over the aspects of physical storage and access to the data it owns. So in contrast from DHT the addition of a new data does not require relocation to the existing node.