In-Range Farthest Point Queries and Related Problem in High Dimensions

Ziyun Huang, Jinhui Xu

Abstract

This paper addresses the computational challenge of performing complex range-aggregate queries in high-dimensional spaces ($R^d$). Specifically, it focuses on the In-Range Farthest Point (IFP) and Minimum Enclosing Ball (MEB) problems, which are notoriously difficult due to the "curse of dimensionality." The authors present the first efficient theoretical bi-criteria approximation schemes for these problems. By integrating a novel "ball-peeling" strategy with a multi-scale data structure based on Locality Sensitive Hashing (LSH), the proposed methods achieve sub-linear query times and sub-quadratic space complexity, providing a significant breakthrough in high-dimensional computational geometry.

Introduction

In traditional range searching, the goal is typically to identify or count points within a specific geometric region, such as a sphere or a box. Range-aggregate queries are more demanding: they require computing a structural property of the subset of points contained within the query range. Examples include finding the point farthest from a query location or determining the smallest ball that encloses all points in the range.

While these problems are well-solved in low-dimensional settings (e.g., 2D or 3D), they become exponentially harder as the dimensionality $d$ increases. Prior to this work, no efficient theoretical results existed for IFP or MEB queries in high-dimensional space that avoided the exponential pitfalls of the curse of dimensionality.

Methodology

To circumvent the inherent complexity of exact solutions, the authors develop a bi-criteria approximation scheme. This approach allows for a $(1-\epsilon)$ approximation of the distance and permits the query range itself to be "fuzzy" by a factor of $(1+\gamma)$. The methodology is built upon three primary technical pillars:

1. Ball Difference (BD) Queries

The authors introduce a fundamental building block designed to identify a point that resides within one ball ($B_{in}$) but outside another ($B_{out}$). This is implemented by adapting Locality Sensitive Hashing (LSH). While LSH is traditionally used to find similar (close) points, the authors modify it to handle the "difference" between two balls by analyzing bit-string commonalities to satisfy specific distance constraints relative to two distinct centers.

2. The Ball-Peeling Strategy

To solve the IFP problem, the algorithm employs a "ball-peeling" technique. Starting from a small radius around the query point, the algorithm iteratively "peels" away layers of the point set. By using BD queries to check for the existence of points in the annulus between the current boundary and the query range, the algorithm effectively isolates the approximate farthest point.

3. Multi-scale Data Structures

Because query ranges can vary significantly in size and location, the authors utilize an Aggregation Tree (a variant of Hierarchical Well-Separated Trees) combined with a Range Cover technique. This multi-scale framework allows the data structure to "sketch" the point set at multiple resolutions, ensuring that queries can be handled efficiently regardless of their scale.

Theoretical Results

The paper's contributions are primarily theoretical, establishing new bounds for algorithmic complexity:

  • IFP Complexity: For a set of $n$ points in $d$ dimensions, the authors construct a data structure of size $\tilde{O}(dn^{1+\rho})$ that answers queries in $\tilde{O}(dn^\rho)$ time. Crucially, $\rho$ is a constant less than 1, ensuring sub-linear query performance.
  • MEB Approximation: The authors demonstrate that the IFP solution can be extended to provide a $(1+\epsilon)$-approximation for the Minimum Enclosing Ball problem with comparable time and space complexities.
  • Algorithmic Milestone: These results represent the first sub-linear query times for these specific aggregate functions in high dimensions.

Discussion and Future Work

The proposed framework decouples the scale of the query from the aggregation function itself. This suggests that the "Aggregation Tree + Range Cover" approach may serve as a general-purpose tool for other high-dimensional problems, such as computing the diameter or the minimum spanning tree of a range-restricted point set.

However, some limitations remain. As is common with LSH-based approaches, the hidden constants in the Big-O notation are sensitive to the approximation factors ($\epsilon$ and $\gamma$). As the requirement for accuracy increases, the computational overhead may grow. Additionally, the randomized nature of the algorithm means there is a small, albeit bounded, probability of failure. Future research may focus on refining these constants or applying the multi-scale framework to a broader library of geometric aggregates.

Summary updated

Abstract

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 $\epsilon>0$ that specifies the approximation ratio of the farthest distance and any $\gamma>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}_{\epsilon,\gamma}(dn^{1+\rho})$ in $\tilde{O}_{\epsilon,\gamma}(dn^{1+\rho})$ time such that given any $\mathbb{R}^d$ query ball $B$ and query point $q$, it outputs in $\tilde{O}_{\epsilon,\gamma}(dn^{\rho})$ time a point $p$ that is a $(1-\epsilon)$-approximation of the farthest point to $q$ among all points lying in a $(1+\gamma)$-expansion $B(1+\gamma)$ of $B$, where $0<\rho<1$ is a constant depending on $\epsilon$ and $\gamma$ and the hidden constants in big-O notations depend only on $\epsilon$, $\gamma$ 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+\epsilon)$-approximation for MEB.
BibTeX
@inproceedings{huang2022range,
  author = {Ziyun Huang and Jinhui Xu},
  title = {{In-Range Farthest Point Queries and Related Problem in High Dimensions}},
  booktitle = {ICALP},
  year = {2022},
  url = {https://openreview.net/forum?id=q8CnjtVyHOr},
}
Figure