Prioritized Metric Structures and Embedding
From MaRDI portal
Publication:2941541
DOI10.1145/2746539.2746623zbMath1321.68222arXiv1502.05543OpenAlexW2094568665MaRDI QIDQ2941541
Ofer Neiman, Arnold Filtser, Michael Elkin
Publication date: 21 August 2015
Published in: SIAM Journal on Computing, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Abstract: Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms cite{llr}, online algorithms cite{BBMN11}, distributed algorithms cite{KKMPT12} and for computing sparsifiers cite{ST04}. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee. In this paper we alleviate this limitation by devising a suit of {em prioritized} metric data structures and embeddings. We show that given a priority ranking $(x_1,x_2,ldots,x_n)$ of the graph vertices (respectively, metric points) one can devise a metric data structure (respectively, embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex $x_j$ will depend on the rank $j$ of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension, may depend only on $j$. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and label size (resp., dimension) {em simultaneously}. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their non-prioritized counterparts.
Full work available at URL: https://arxiv.org/abs/1502.05543
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramsey partitions and proximity data structures
- Lower bounds for local versions of dimension reductions
- The metrical interpretation of superreflexivity in Banach spaces
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On sparse spanners of weighted graphs
- The dimension of almost spherical sections of convex bodies
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- The geometry of graphs and some of its algorithmic applications
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Approximate Distance Oracles with Improved Bounds
- Prioritized Metric Structures and Embedding
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Extensions of Lipschitz mappings into a Hilbert space
- Triangulation and embedding using small sets of beacons
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- A Separator Theorem for Planar Graphs
- Routing with Polynomial Communication-Space Trade-Off
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
- Distance Labels with Optimal Local Stretch
- Shortest-path queries in static networks
- Object location using path separators
- Approximate distance oracles with constant query time
- Spanners with Slack
- A Polylogarithmic-Competitive Algorithm for the k-Server Problem
- Automata, Languages and Programming
- Approximate Distance Oracles with Improved Query Time
- Advances in metric embedding theory
- A tight bound on approximating arbitrary metrics by tree metrics
- Efficient distributed approximation algorithms via probabilistic tree embeddings
Related Items (8)
Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Prioritized Metric Structures and Embedding ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Near Isometric Terminal Embeddings for Doubling Metrics
Uses Software
This page was built for publication: Prioritized Metric Structures and Embedding
