论文标题
通过局部敏感订单标记了最近的邻居搜索和公制跨度
Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
论文作者
论文摘要
Chan，Har-Peled和Jones [Sicomp 2020]为欧几里得空间开发了对区域敏感的订单（LSO）。 a $（τ，ρ）$ - lso是一个订购的$σ$，因此每$ x，y \ in \ mathbb {r}^d $都有一个订购$σ\inς$，其中$ x $和$ y $ w.r.t. $σ$在$ x $ $ x $或$ y $的$ρ$ nighborhood中。从本质上讲，LSO允许人们将问题减少到$ 1 $维的线路。后来，Filtser和Le [STOC 2022]开发了LSO的LSO，用于翻倍指标，通用度量空间和次要的免费图。对于欧几里得和加倍的空间，LSO中的有序数在维度中是指数的，这使它们主要对低维度有用。在本文中，我们为Euclidean，$ \ ell_p $开发了新LSO，并加倍空间，使我们可以将更大的延伸量以少量的订单交易。然后，我们使用新的LSO（以及以前的LSO）来构建报告较低的跳班跨度，可靠的跨度，可靠的跨度和轻度跨度的路径。虽然许多最近的邻居搜索（NNS）数据结构是为具有隐式距离表示的度量空间（其中两个度量点之间的距离，例如使用其名称，例如欧几里得空间），但对于其他空间，几乎什么都不知道。在本文中，我们启动了标记为NNS问题的研究，其中允许人们人为地将标签（短名称）分配给度量点。我们使用LSO在此模型中构建有效标记的NNS数据结构。
Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive orderings (LSO) for Euclidean space. A $(τ,ρ)$-LSO is a collection $Σ$ of orderings such that for every $x,y\in\mathbb{R}^d$ there is an ordering $σ\inΣ$, where all the points between $x$ and $y$ w.r.t. $σ$ are in the $ρ$-neighborhood of either $x$ or $y$. In essence, LSO allow one to reduce problems to the $1$-dimensional line. Later, Filtser and Le [STOC 2022] developed LSO's for doubling metrics, general metric spaces, and minor free graphs. For Euclidean and doubling spaces, the number of orderings in the LSO is exponential in the dimension, which made them mainly useful for the low dimensional regime. In this paper, we develop new LSO's for Euclidean, $\ell_p$, and doubling spaces that allow us to trade larger stretch for a much smaller number of orderings. We then use our new LSO's (as well as the previous ones) to construct path reporting low hop spanners, fault tolerant spanners, reliable spanners, and light spanners for different metric spaces. While many nearest neighbor search (NNS) data structures were constructed for metric spaces with implicit distance representations (where the distance between two metric points can be computed using their names, e.g. Euclidean space), for other spaces almost nothing is known. In this paper we initiate the study of the labeled NNS problem, where one is allowed to artificially assign labels (short names) to metric points. We use LSO's to construct efficient labeled NNS data structures in this model.
