English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Range-aggregate query is an important type of queries with numerousapplications. It aims to obtain some structural information (defined by anaggregate function $F(\cdot)$) of the points (from a point set $P$) inside agiven query range $B$. In this paper, we study the range-aggregate queryproblem in high dimensional space for two aggregate functions: (1) $F(P \capB)$ 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$. Forproblem (1), called In-Range Farthest Point (IFP) Query, we develop abi-criteria approximation scheme: For any $\epsilon>0$ that specifies theapproximation ratio of the farthest distance and any $\gamma>0$ that measuresthe "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 pointslying in a $(1+\gamma)$-expansion $B(1+\gamma)$ of $B$, where $0<\rho<1$ is aconstant depending on $\epsilon$ and $\gamma$ and the hidden constants in big-Onotations depend only on $\epsilon$, $\gamma$ and $\text{Polylog}(nd)$. Forproblem (2), we show that the IFP result can be applied to develop query schemewith similar time and space complexities to achieve a$(1+\epsilon)$-approximation for MEB.

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