Spherical range queries are a fundamental primitive for working with spatial data. Many spatial data structures have been developed to answer these queries, but choosing the optimal one for a specific application is a difficult task. This is because theoretical worst-case bounds are often overly pessimistic, and existing average-case analyses are rather restricted and hard to compare. We address this problem with two main contributions. First, we present a comprehensive evaluation of state-of-the-art spatial indices across a diverse set of benchmarks. This includes a new benchmark based on graph embeddings alongside multiple real-world datasets from the literature. Our benchmark covers instances scaling up to 10M points and ranging between 2 and 960 dimensions. Second, we introduce the Sorted-Projection Radius KD-tree (SPRK-tree), a high-performance KD-tree variant. The SPRK-tree combines aggressive subtree pruning via radius reduction, sorted projection-based leaf nodes, and careful implementation optimizations. It consistently achieves the fastest query times in almost all benchmarks, and ranks second in the few remaining cases.

Learning low-dimensional numerical representations from symbolic data, e.g., embedding the nodes of a graph into a geometric space, is an important concept in machine learning. While embedding into Euclidean space is common, recent observations indicate that hyperbolic geometry is better suited to represent hierarchical information and heterogeneous data (e.g., graphs with a scale-free degree distribution). Despite their potential for more accurate representations, hyperbolic embeddings also have downsides like being more difficult to compute and harder to use in downstream tasks. We propose embedding into a weighted space, which is closely related to hyperbolic geometry but mathematically simpler. We provide the embedding algorithm WEmbed and demonstrate, based on generated as well as over 2000 real-world graphs, that our weighted embeddings heavily outperform state-of-the-art Euclidean embeddings for heterogeneous graphs while using fewer dimensions. The running time of WEmbed and embedding quality for the remaining instances is on par with state-of-the-art Euclidean embedders.

We consider intersection graphs of disks of radius r in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of r, where very small r corresponds to an almost-Euclidean setting and r ∈ Ω(log n) corresponds to a firmly hyperbolic setting. We observe that larger values of r create simpler graph classes, at least in terms of separators and the computational complexity of the Independent Set problem. First, we show that intersection graphs of disks of radius r in the hyperbolic plane can be separated with 𝒪((1+1/r)log n) cliques in a balanced manner. Our second structural insight concerns Delaunay complexes in the hyperbolic plane and may be of independent interest. We show that for any set S of n points with pairwise distance at least 2r in the hyperbolic plane, the corresponding Delaunay complex has outerplanarity 1+𝒪((log n)/r), which implies a similar bound on the balanced separators and treewidth of such Delaunay complexes. Using this outerplanarity (and treewidth) bound we prove that Independent Set can be solved in n^𝒪(1+(log n)/r) time. The algorithm is based on dynamic programming on some unknown sphere cut decomposition that is based on the solution. The resulting algorithm is a far-reaching generalization of a result of Kisfaludi-Bak (SODA 2020), and it is tight under the Exponential Time Hypothesis. In particular, Independent Set is polynomial-time solvable in the firmly hyperbolic setting of r ∈ Ω(log n). Finally, in the case when the disks have ply (depth) at most 𝓁, we give a PTAS for Maximum Independent Set that has only quasi-polynomial dependence on 1/ε and 𝓁. Our PTAS is a further generalization of our exact algorithm.