论文标题
高维度的最远的点查询和相关问题
In-Range Farthest Point Queries and Related Problem in High Dimensions
论文作者
论文摘要
范围聚集查询是具有许多应用程序的重要类型。它旨在在给定查询范围$ b $中获得一些点（从点集$ p $）的点（从点集$ p $）的一些结构信息（定义的）。在本文中，我们研究了两个汇总功能的高维空间中的范围 - 聚集问题问题：（1）$ f（p \ cap b）$是$ p \ cap b $到查询点$ q $ in $ \ mathbb {r}^d $和（2）$ f（p \ cap b）$ encl（$ enc）的最高点$ q $ $ $ $。对于问题（1），称为最远的点（IFP）查询，我们开发了双标准近似方案：对于任何$ε> 0 $，指定最距离的近似值和任何$γ> 0 $，该近似值和任何$γ> 0 $衡量查询范围的“模糊”范围，我们表明，我们可能会显示出$ P $ P $ P $ P $ p Data Data Data Data Data Data Data Data Data Data Data Data Size size size的大小$ \ tilde {o} _ {ε，γ}（dn^{1+ρ}）$ in $ \ tilde {o} _ {o} _ {ε，γ}（dn^{1+ρ}）$ time，给定任何$ \ m} $ \ tilde {o} _ {ε，γ}（dn^ρ）$ time a point $ p $，是$（1-ε）$ - 在所有点$ q $的近似值（1+γ）$ - 扩展$ b（1+γ）$ b $ $ 0 $ $ 0 <1 $ a $ a $ a $ a $ a $ quent $ q $ a $ q $ a $ 0 <1 <ρ<ρ<ρ<ρ<ρ<1 $ q $的近似值Big-O符号中的常数仅取决于$ε$，$γ$和$ \ text {polylog}（nd）$。对于问题（2），我们表明可以将IFP结果应用于具有相似时间和空间复杂性的查询方案，以实现MEB的$（1+ε）$ - 近似值。
Range-aggregate query is an important type of queries with numerous applications. It aims to obtain some structural information (defined by an aggregate function $F(\cdot)$) of the points (from a point set $P$) inside a given query range $B$. In this paper, we study the range-aggregate query problem in high dimensional space for two aggregate functions: (1) $F(P \cap B)$ is the farthest point in $P \cap B$ to a query point $q$ in $\mathbb{R}^d$ and (2) $F(P \cap B)$ is the minimum enclosing ball (MEB) of $P \cap B$. For problem (1), called In-Range Farthest Point (IFP) Query, we develop a bi-criteria approximation scheme: For any $ε>0$ that specifies the approximation ratio of the farthest distance and any $γ>0$ that measures the "fuzziness" of the query range, we show that it is possible to pre-process $P$ into a data structure of size $\tilde{O}_{ε,γ}(dn^{1+ρ})$ in $\tilde{O}_{ε,γ}(dn^{1+ρ})$ time such that given any $\mathbb{R}^d$ query ball $B$ and query point $q$, it outputs in $\tilde{O}_{ε,γ}(dn^ρ)$ time a point $p$ that is a $(1-ε)$-approximation of the farthest point to $q$ among all points lying in a $(1+γ)$-expansion $B(1+γ)$ of $B$, where $0<ρ<1$ is a constant depending on $ε$ and $γ$ and the hidden constants in big-O notations depend only on $ε$, $γ$ and $\text{Polylog}(nd)$. For problem (2), we show that the IFP result can be applied to develop query scheme with similar time and space complexities to achieve a $(1+ε)$-approximation for MEB.
