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

Ziyun Huang, Jinhui Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(·)) 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.

Original languageEnglish (US)
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772358
DOIs
StatePublished - Jul 1 2022
Event49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France
Duration: Jul 4 2022Jul 8 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume229
ISSN (Print)1868-8969

Conference

Conference49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Country/TerritoryFrance
CityParis
Period7/4/227/8/22

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'In-Range Farthest Point Queries and Related Problem in High Dimensions'. Together they form a unique fingerprint.

Cite this