Refine
Year of publication
Document Type
- In Proceedings (22)
- Article (16)
- ZIB-Report (5)
- Other (4)
- Book chapter (2)
- Poster (2)
Language
- English (51)
Is part of the Bibliography
- no (51)
Keywords
- DHT (2)
- Grid computing (1)
- P2P (1)
- Paxos (1)
- Range Queries (1)
- Transaktionen (1)
- XML (1)
- availability (1)
- customized user interfaces (1)
- data grid (1)
- distributed catalog (1)
- grid user communities (1)
- multidimensional data sets (1)
- range queries (1)
- reliability (1)
- replication (1)
- routing (1)
- strenge Konsistenz (1)
- strong consistency (1)
- structured overlays (1)
- transactions (1)
- web portals (1)
Geomultisens – a common automatic processing and analysis system for multi-sensor satellite data
(2016)
We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.
\newcommand{\chordsharp}{Chord$^\##$} Data lookup is a fundamental problem in peer-to-peer systems: Given a key, find the node that stores the associated object. Chord and other P2P algorithms use distributed hash tables (DHTs) to distribute the keys and nodes evenly across a logical ring. Using an efficient routing strategy, DHTs provide a routing performance of $O (\log N)$ in networks of $N$ nodes. While the routing performance has been shown to be optimal, the uniform key distribution makes it impossible for DHTs to support range queries. For range queries, consecutive keys must be stored on lo gically neighboring nodes. In this paper, we present an enhancement of Chord that eliminates the hash function while keeping the same routing performance. The resulting algorithm, named \chordsharp{}, provides a richer function ality while maintaining the same complexity. In addition to Chord, \chordsharp{} adapts to load imbalance.