Research map / Learning theory and algorithms / Clustering

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

AAAI 2024 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Presents near-linear-size approximate distance and shortest-path oracles for vertex-fault-tolerant Euclidean spanners, answering queries under a small set of failed vertices.

Problem

Approximate distance and shortest-path queries in road-network-like graphs under vertex failures, where prior general-graph oracles need quadratic space.

Approach

Builds kernel oracles on fault-tolerant Euclidean spanners using FT-structures (adapted from edge-fault structures of Chechik et al.) built only for net-vertex pairs and restricted subgraphs, giving near-linear space; path-preserving kernels plus a fault-tolerant connectivity oracle recover actual paths.

Key results

• Distance oracle answers (1+ε)-approximate distance queries in O(t^8 f^4) time for moderately far vertices with space near-linear (h(t,f,ε)·n log n), where h = exp(O(f log(tf/ε))).
• Shortest-path oracle returns an approximate path in O(f^4 log^2 n log log n + sol) time, where sol is the number of vertices in the returned path.
• Prior best vertex-fault approximate distance oracle by Duan, Gu, and Ren 2021 uses O(n^2) space, which this work improves to near-linear.

Limitations

• Hidden constants and exponential dependence on t and f (exp(O(f log(tf/ε)))) make the oracle likely impractical as stated
• Only analyzed for two-dimensional Euclidean spanners; higher dimensions only sketched in appendices
• Queries restricted to moderately far vertex pairs; close pairs are handled via generalization lemmas

Experimental setup

Metrics: space complexity construction time query time

Baselines: Duan, Gu, and Ren 2021 vertex-fault distance oracle

Builds on: Chechik et al. 2017 FT structure Duan and Pettie fault-tolerant connectivity oracle Gudmundsson et al. 2008 spanner distance oracle Duan, Gu, and Ren 2021 vertex-fault distance oracle

Closest papers by meaning

• Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (AAAI 2025 · similarity 0.86)
• Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.82)
• Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.82)
• Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.81)
• Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · similarity 0.81)
• Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs (NeurIPS 2026 · similarity 0.80)