In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a number of combinatorial problems. We pursue this line of research by considering its application to data structures for searching in implicit sets, defined as the image of a function. Given a function f from the set [N] to a d-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of f, without explicitly storing it. We show that if f is of the form <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$[N]\rightarrow [2^{w}]^d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">[</mo> <mi>N</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">→</mo> <msup> <mrow> <mo stretchy="false">[</mo> <msup> <mn>2</mn> <mi>w</mi> </msup> <mo stretchy="false">]</mo> </mrow> <mi>d</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for some <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$w=\textrm{polylog} (N)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>w</mi> <mo>=</mo> <mtext>polylog</mtext> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and is computable in constant time, then, for any <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$0<\alpha <1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo><</mo> <mi>α</mi> <mo><</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, we can obtain a data structure using <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\tilde{O}(N^{1-\alpha / 3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mrow> <mn>1</mn> <mo>-</mo> <mi>α</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> space such that, for a given d-dimensional axis-aligned box B, we can search for some <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$x\in [N]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mi>N</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$f(x) \in B$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>B</mi> </mrow> </math></EquationSource> </InlineEquation> in time <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\tilde{O}(N^{\alpha })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mi>α</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. (Here the <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\tilde{O}(.)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <mo>.</mo> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> notation omits polylogarithmic factors.) Using similar techniques, we further obtain<UnorderedList Mark="Bullet"> <ItemContent> data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set f([N]), </ItemContent> <ItemContent> data structures for preimage size and preimage selection queries for a given value of f, and </ItemContent> <ItemContent> data structures for selection and ranking queries on geometric quantities computed from tuples of points in d-space. </ItemContent> </UnorderedList> These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the kth largest area triangle, or the induced hyperplane that is the kth furthest from the origin.

A General Technique for Searching in Implicit Sets via Function Inversion

期刊论文
发表日期：

2026年4月13日

查看全文

Boris Aronov,
Jean Cardinal,
Justin Dallant,
John Iacono

摘要

In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a number of combinatorial problems. We pursue this line of research by considering its application to data structures for searching in implicit sets, defined as the image of a function. Given a function f from the set [N] to a d-dimensional integer grid, we consider data structures that allow efficient orthogonal range searching queries in the image of f, without explicitly storing it. We show that if f is of the form $[N]\rightarrow [2^{w}]^d$ $[N] \to {[2^{w}]}^{d}$ for some $w=\textrm{polylog} (N)$ $w = polylog (N)$ and is computable in constant time, then, for any $0<\alpha <1$ $0 < α < 1$ , we can obtain a data structure using $\tilde{O}(N^{1-\alpha / 3})$ $\tilde{O} (N^{1 - α / 3})$ space such that, for a given d-dimensional axis-aligned box B, we can search for some $x\in [N]$ $x \in [N]$ such that $f(x) \in B$ $f (x) \in B$ in time $\tilde{O}(N^{\alpha })$ $\tilde{O} (N^{α})$ . (Here the $\tilde{O}(.)$ $\tilde{O} (.)$ notation omits polylogarithmic factors.) Using similar techniques, we further obtain

data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set f([N]),

data structures for preimage size and preimage selection queries for a given value of f, and

data structures for selection and ranking queries on geometric quantities computed from tuples of points in d-space.

These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the kth largest area triangle, or the induced hyperplane that is the kth furthest from the origin.