P2P Routing of Range Queries in Skewed Multidimensional Data Sets
Please always quote using this URN: urn:nbn:de:0297-zib-9671
- 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.
Author: | Alexander Reinefeld, Florian SchintkeORCiD, Thorsten SchüttORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | multidimensional data sets; range queries; routing; structured overlays |
CCS-Classification: | E. Data / E.1 DATA STRUCTURES |
C. Computer Systems Organization / C.2 COMPUTER-COMMUNICATION NETWORKS / C.2.4 Distributed Systems | |
H. Information Systems / H.3 INFORMATION STORAGE AND RETRIEVAL / H.3.3 Information Search and Retrieval | |
H. Information Systems / H.3 INFORMATION STORAGE AND RETRIEVAL / H.3.4 Systems and Software | |
H. Information Systems / H.3 INFORMATION STORAGE AND RETRIEVAL / H.3.5 Online Information Services | |
Date of first Publication: | 2007/09/03 |
Series (Serial Number): | ZIB-Report (07-23) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 07-23 |