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.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Author:Alexander Reinefeld, Florian Schintke, Thorsten Schütt
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)

$Rev: 13581 $