TY - GEN

T1 - A General Technique for Searching in Implicit Sets via Function Inversion

AU - Aronov, Boris

AU - Cardinal, Jean

AU - Dallant, Justin

AU - Iacono, John

N1 - Publisher Copyright:
Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - 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] → [2w]d for some w = polylog(N) and is computable in constant time, then, for any 0 < α < 1, we can obtain a data structure using Õ(N1−α/3) words of space such that, for a given d-dimensional axis-aligned box B, we can search for some x ∈ [N] such that f(x) ∈ B in time Õ(Nα). This result is obtained simply by combining integer range searching with the Fiat-Naor function inversion scheme, which was already used in data-structure problems previously. 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.

AB - 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] → [2w]d for some w = polylog(N) and is computable in constant time, then, for any 0 < α < 1, we can obtain a data structure using Õ(N1−α/3) words of space such that, for a given d-dimensional axis-aligned box B, we can search for some x ∈ [N] such that f(x) ∈ B in time Õ(Nα). This result is obtained simply by combining integer range searching with the Fiat-Naor function inversion scheme, which was already used in data-structure problems previously. 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.

UR - http://www.scopus.com/inward/record.url?scp=85187783701&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187783701&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85187783701

T3 - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

SP - 215

EP - 223

BT - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

A2 - Parter, Merav

A2 - Pettie, Seth

PB - Society for Industrial and Applied Mathematics Publications

T2 - 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024

Y2 - 8 January 2024 through 10 January 2024

ER -