Approximate Range Emptiness in Constant Time and Optimal Space

Problem

• Approximate range emptiness represents n points so interval queries always detect nonempty intersections while allowing false positives on empty intervals.This generalizes approximate membership from single-point queries to intervals.Source: §1 · p. 2

Baseline

• The trivial construction uses approximate membership at false positive rate ε/L for each point in an interval, requiring n lg(L/ε) bits and O(L lg(L/ε)) query time.A union bound gives false positive probability ε for intervals of length at most L.Source: §1 · p. 2

Lower bounds

• Any structure answering intervals up to length L with false positive probability ε must use Ω(n lg(L/ε)) − O(n) bits, even when only length-L intervals are queried.The lower bound rules out asymptotic space improvements over the trivial construction.Source: §1 · pp. 2–3

Upper bound

• The proposed structure answers intervals of length ℓ≤L in O(1) time using n lg(L/ε)+o(n lg(L/ε))+O(n) bits, with false positive rate εℓ/L.It matches the lower bound up to a lower-order additive term when L/ε=ω(1).Source: §1 · p. 3

Additional contribution

• Its succinct non-approximate range-emptiness building block uses n lg(U/n)+O(n lg^δ(U/n)) bits and also reports k points in O(k) time.The paper identifies this one-dimensional range reporting structure as independently interesting.Source: §1 · p. 3

Two-sided errors

• For two-sided error, the paper proves additional lower bounds showing that substantial space savings remain impossible across specified small and moderate error regimes.These bounds also apply when only length-L intervals are queried.Source: §1 · p. 3

• Any data structure answering length-L intervals with false positive rate ε must use a lower-bounded amount of space when L ≤ U/5n.The proof encodes every L-well-separated point set using the data structure’s representation and query answers.Source: §2 · p. 4
• The lower-bound encoding restricts attention to L-well-separated sets, whose points are separated by at least 2L and remain away from universe boundaries.There are at least ((U − 4nL)/n)^n such sets for L ≤ U/4n.Source: §2 · p. 4
• The encoding queries top intervals and level-covering intervals, then uses their answers to recover each point’s location and binary bits.Top intervals contain at most one point, while the covering intervals selected from each level isolate the point according to its corresponding bit.Source: §2 · pp. 4–5
• The construction chooses a memory representation with few false positives, stores the representation, identifies occupied top intervals, and records only needed covering-interval bits.This makes the encoding length depend on the data structure’s space and error rate, yielding the lower bound after comparing it with the number of separable sets.Source: §2 · p. 5

2.1 Extension to two-sided errors

• The lower bound extends to two-sided error by additionally encoding false negatives before applying the one-sided decoding procedure.The extension uses a secondary encoding to identify false negatives and then runs the original encoding after correcting them.Source: §2.1 · pp. 7–9

Universe Reduction

• The construction hashes points into a universe of size r = nL/ε, then applies a non-approximate succinct range-emptiness structure to the hashed set.The hash is chosen to preserve locality while keeping collision probability small.Source: §3 · p. 9, §3.1 · p. 9
• n lg(L/ε)+O(n lg^δ(L/ε)) bits supports intervals of length at most L in constant time with false positive rate at most ε.This is the main upper-bound guarantee for any desired constant δ > 0.Source: §3 · p. 9
• For distinct points, the locality-preserving hash collides with probability at most 1/r.The collision probability is zero when both points lie in the same hash block and exactly 1/r otherwise.Source: §3.1 · p. 9
• A query interval maps to at most two intervals, and reporting non-emptiness of either mapped interval preserves no false negatives while false positives arise from hash collisions.The false-positive probability is bounded by a union bound over possible point-interval collisions.Source: §3.1 · pp. 9–10

Range Emptiness Data Structure

• The succinct range-emptiness structure partitions the universe into n subranges and combines rank/select indexes with local structures to answer each query part in constant time.A query splits into one spanning sequence and at most two boundary parts; each is answered in constant time.Source: §3.2 · p. 10

Range Reporting

• The same structure reports all k points in a query interval in O(k) time by scanning locally and using rank/select to locate subsequent non-empty subranges.It spends O(1) time per reported point.Source: §3.2 · p. 11