Average-Distortion Sketching
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912319689195520 |
|---|---|
| author | Bao, Yiqiao Baweja, Anubhav Menand, Nicolas Waingarten, Erik White, Nathan Zhang, Tian |
| author_facet | Bao, Yiqiao Baweja, Anubhav Menand, Nicolas Waingarten, Erik White, Nathan Zhang, Tian |
| contents | We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $μ$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $μ$. The notion generalizes average-distortion embeddings into $\ell_1$ [Rabinovich '03, Kush-Nikolov-Tang '21] as well as data-dependent locality-sensitive hashing [Andoni-Razenshteyn '15, Andoni-Naor-Nikolov-et-al. '18], which have been recently studied in the context of nearest neighbor search.
$\bullet$ For all $p \in (2, \infty)$ and any $c$ larger than a fixed constant, we give an average-distortion sketch for $([Δ]^d, \ell_p)$ with approximation $c$ and bit-complexity $\text{poly}(2^{p/c} \cdot \log(dΔ))$, which is provably impossible in (worst-case) sketching.
$\bullet$ As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_p$ (for large $p > 2$). The prior best approximation was $O(p)$ [Andoni-Naor-Nikolov-et-al. '18, Kush-Nikolov-Tang '21], and we show it can be any $c$ larger than a fixed constant (irrespective of $p$) by using $n^{O(p/c)}$ space.
We give some evidence that $2^{Ω(p/c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05156 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Average-Distortion Sketching Bao, Yiqiao Baweja, Anubhav Menand, Nicolas Waingarten, Erik White, Nathan Zhang, Tian Data Structures and Algorithms We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $μ$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $μ$. The notion generalizes average-distortion embeddings into $\ell_1$ [Rabinovich '03, Kush-Nikolov-Tang '21] as well as data-dependent locality-sensitive hashing [Andoni-Razenshteyn '15, Andoni-Naor-Nikolov-et-al. '18], which have been recently studied in the context of nearest neighbor search. $\bullet$ For all $p \in (2, \infty)$ and any $c$ larger than a fixed constant, we give an average-distortion sketch for $([Δ]^d, \ell_p)$ with approximation $c$ and bit-complexity $\text{poly}(2^{p/c} \cdot \log(dΔ))$, which is provably impossible in (worst-case) sketching. $\bullet$ As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_p$ (for large $p > 2$). The prior best approximation was $O(p)$ [Andoni-Naor-Nikolov-et-al. '18, Kush-Nikolov-Tang '21], and we show it can be any $c$ larger than a fixed constant (irrespective of $p$) by using $n^{O(p/c)}$ space. We give some evidence that $2^{Ω(p/c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on). |
| title | Average-Distortion Sketching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.05156 |