Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2311.12471 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908986243022848 |
|---|---|
| author | Aronov, Boris Cardinal, Jean Dallant, Justin Iacono, John |
| author_facet | Aronov, Boris Cardinal, Jean Dallant, Justin Iacono, John |
| contents | 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.
We show that, if $f$ is of the form $[N]\to [2^{w}]^d$ for some $w=polylog(N)$ and is computable in constant time, then, for any $0<α<1$, we can obtain a data structure using $Õ(N^{1-α/3})$ space such that, for a given $d$-dimensional axis-aligned box $B$, we can search for some $x\in [N]$ such that $f(x) \in B$ in time $Õ(N^α)$. (Here the $Õ(.)$ 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 $k$th largest area triangle, or the induced hyperplane that is the $k$th furthest from the origin. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_12471 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A General Technique for Searching in Implicit Sets via Function Inversion Aronov, Boris Cardinal, Jean Dallant, Justin Iacono, John Data Structures and Algorithms 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. We show that, if $f$ is of the form $[N]\to [2^{w}]^d$ for some $w=polylog(N)$ and is computable in constant time, then, for any $0<α<1$, we can obtain a data structure using $Õ(N^{1-α/3})$ space such that, for a given $d$-dimensional axis-aligned box $B$, we can search for some $x\in [N]$ such that $f(x) \in B$ in time $Õ(N^α)$. (Here the $Õ(.)$ 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 $k$th largest area triangle, or the induced hyperplane that is the $k$th furthest from the origin. |
| title | A General Technique for Searching in Implicit Sets via Function Inversion |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.12471 |