Multi-Dimensional Radius Query Benchmarksets

The following data overview is an excerpt from the "Benchmarking and Engineering Data Structures forSpherical Range Queries" paper [0]All datasets were generated or processed using rembed [1]We introduce a new benchmark-set based on graph embeddings, using geometric inhomogeneous random graphs (GIRGs) [2]generated using the method in [3]. For generation, we set the average degree to 15, the power-law exponent to 2.5, the dimension to 4, and the temperature to 0 (corresponding to α = ∞). We vary the number of vertices n in a and use 3 different seeds for each parameter configuration.To obtain a data set from these graphs, we compute embeddings using the WEmbed algorithm [4] implemented in rembed [0].

We set the embedding dimension d from 2 to 16.

We choose 10 k queries per embedding, sorting the vertices by degree and then choosing every k-th vertex for k = n/10^4.The distributions data consists of uniformly random distributed points within a unit hypercube.

The number of points varies from 10 k to 10 M in half-log-steps in dimensions 2,8,32. For each point set, a 10 k query-set is provided with the query radius set for each point such that the expected number of returned points is 15. The point of interest (POI) data represents geographic data and is queried with fixed-radius POI queries, e.g., finding all bus stops within 500 meters of a given location.
... mehr

The data stems from the OpenStreetMap project for Germany [5], with 20 categories including: ATMs (≈ 12 k), bakeries (≈ 33 k), parking facilities (≈ 769 k), bus stops (≈ 761 k), and restaurants (≈ 103 k).

Query sets are constructed by using POIs of one category as dataset and POIs of a different category as query points.

Queries in our benchmark where run at radii of 500 m, 1000 m, 2000 m, and 5000 m.[0] https://arxiv.org/pdf/2607.07367[1] https://github.com/wembed-pdf/rembed[2] Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theor. Comput. Sci., 760:35–54, 2019. doi:10.1016/J.TCS.2018.08.014.537[3] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic525random graphs. Network Science, 10(4):361–380, 2022. doi:10.1017/nws.2022.32.[4] Thomas Bläsius, Jean-Pierre von der Heydt, Maximilian Katzmann, and Nikolai Maas. Weighted embeddings for low-dimensional graph representation. In AAAI Conference on Artificial Intelligence (AAAI), pages 15587–15595, 2025. doi:10.1609/aaai.v39i15.33711.[5] OSM Data downloaded from Geofabrik Gmbh. OSM Data Germany https://download.geofabrik.de/