Optimal (Euclidean) Metric Compression

DOI10.1137/20M1371324MaRDI QIDQ5080486zbMATH OpenOpenAlexWikidataFDO

Authors Tal Wagner, Piotr Indyk

Publication date 31 May 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.03152

zbMATH Keywords

dimension reductionquantizationdistance oracledistance sketchmetric sketch

Mathematics Subject Classification ID

Data structures (68P05) Discrete geometry (52C99) Metric embeddings as related to computational problems and algorithms (68R12)

Recommendations

• Near-optimal (Euclidean) metric compression
• Advances in metric embedding theory
• Volume distortion for subsets of Euclidean spaces
• Dimension reduction for ultrametrics
• Near-optimal compression for the planar graph metric

Cites work

• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximate distance oracles
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved preprocessing time
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Euclidean quotients of finite metric spaces
• Extensions of Lipschitz mappings into a Hilbert space
• Fast binary embeddings and quantized compressed sensing with structured matrices
• Graph spanners
• Near-optimal (Euclidean) metric compression
• Nonlinear dimension reduction via outer bi-Lipschitz extensions
• On sparse spanners of weighted graphs
• On the distortion required for embedding finite metric spaces into normed spaces
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Optimal terminal dimensionality reduction in Euclidean space
• Probabilistic clustering of high dimensional norms
• Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The space complexity of approximating the frequency moments

Cited in

(2)

• Fast Metric Embedding into the Hamming Cube
• Optimal coding of elements of a metric space

This page was built for publication: Optimal (Euclidean) Metric Compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080486)