TY - GEN
T1 - In-Range Farthest Point Queries and Related Problem in High Dimensions
AU - Huang, Ziyun
AU - Xu, Jinhui
N1 - Publisher Copyright:
© Ziyun Huang and Jinhui Xu; licensed under Creative Commons License CC-BY 4.0
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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(·)) 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 ∩ B) is the farthest point in P ∩ B to a query point q in ℝd and (2) F(P ∩ B) is the minimum enclosing ball (MEB) of P ∩ 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 Õϵ,γ(dn1+ρ) in Õϵ,γ(dn1+ρ) time such that given any Rd query ball B and query point q, it outputs in Õϵ,γ(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 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. To the best of our knowledge, these are the first theoretical results on such high dimensional range-aggregate query problems. Our results are based on several new techniques, such as multi-scale construction and ball difference range query, which are interesting in their own rights and could be potentially used to solve other range-aggregate problems in high dimensional space.
AB - 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(·)) 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 ∩ B) is the farthest point in P ∩ B to a query point q in ℝd and (2) F(P ∩ B) is the minimum enclosing ball (MEB) of P ∩ 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 Õϵ,γ(dn1+ρ) in Õϵ,γ(dn1+ρ) time such that given any Rd query ball B and query point q, it outputs in Õϵ,γ(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 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. To the best of our knowledge, these are the first theoretical results on such high dimensional range-aggregate query problems. Our results are based on several new techniques, such as multi-scale construction and ball difference range query, which are interesting in their own rights and could be potentially used to solve other range-aggregate problems in high dimensional space.
UR - http://www.scopus.com/inward/record.url?scp=85133472024&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85133472024&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2022.75
DO - 10.4230/LIPIcs.ICALP.2022.75
M3 - Conference contribution
AN - SCOPUS:85133472024
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
A2 - Bojanczyk, Mikolaj
A2 - Merelli, Emanuela
A2 - Woodruff, David P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Y2 - 4 July 2022 through 8 July 2022
ER -