We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set P ⊂ ℝᵈ, where each p ∈ P is assigned a weight wₚ, and radius r > 0, we need to preprocess P into a data structure such that when a new query point q ∈ ℝᵈ arrives, the data structure reports the cumulative weight of points of P within Euclidean distance r from q. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to (1+ε) r away from q may be taken into account, where ε > 0 is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in n^1-Θ (ε⁴/log (1/ε) ) +tq^ϱ⋅n^1-ϱ, for some ϱ = Θ (ε²), where tq is the number of points of P in the ambiguity zone, i. e. , at distance between r and (1+ε) r from the query q. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any ε > 0) and query time that remains sublinear for any sublinear tq. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.
Kalavas et al. (Thu,) studied this question.