Refine
Year of publication
Document Type
- In Proceedings (31)
- Article (12)
- ZIB-Report (5)
- Other (4)
- Book chapter (3)
- Doctoral Thesis (1)
- Master's Thesis (1)
- Poster (1)
Is part of the Bibliography
- no (58)
Keywords
- DHT (3)
- Paxos (2)
- Algorithms (1)
- Distributed System (1)
- P2P (1)
- Range Queries (1)
- Storage (1)
- Transaktionen (1)
- heuristic search (1)
- multidimensional data sets (1)
- pattern databases (1)
- range queries (1)
- routing (1)
- strenge Konsistenz (1)
- strong consistency (1)
- structured overlays (1)
- transactions (1)
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.