{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib7nn2whsma7f3rpgmd645v7cnj62txcncwva4a4m6wsuyeu5yweu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgw2pdzmclq2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.12106v1",
  "publishedAt": "2026-03-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Andreas Kalavas",
    "Ioannis Psarros"
  ],
  "textContent": "**Authors:** Andreas Kalavas, Ioannis Psarros\n\nWe study the following range searching problem in high-dimensional Euclidean spaces: given a finite set $P\\subset \\mathbb{R}^d$, where each $p\\in P$ is assigned a weight $w_p$, and radius $r>0$, we need to preprocess $P$ into a data structure such that when a new query point $q\\in \\mathbb{R}^d$ 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+\\varepsilon)r$ away from $q$ may be taken into account, where $\\varepsilon>0$ is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in $n^{1-Θ(\\varepsilon^4/\\log(1/\\varepsilon))}+t_q^{\\varrho}\\cdot n^{1-\\varrho}$, for some $\\varrho=Θ(\\varepsilon^2)$, where $t_q$ is the number of points of $P$ in the ambiguity zone, i.e., at distance between $r$ and $(1+\\varepsilon)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 $\\varepsilon>0$) and query time that remains sublinear for any sublinear $t_q$. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.",
  "title": "Space-Efficient Approximate Spherical Range Counting in High Dimensions"
}