A General Technique for Searching in Implicit Sets via Function Inversion

doi:10.1007/s00453-026-01385-5

2026-04-13

PRE

DOI：10.1007/s00453-026-01385-5

原文链接

原文求助

摘要

En 中文

近年来，Fiat-Naor函数逆方案已被用于推翻精细粒度复杂性理论中的猜想，并为多种组合问题设计出当前最优的数据结构。我们遵循这一研究方向，探讨其应用于在隐式集合中搜索的数据结构，该集合被定义为函数的像。给定一个从集合[N]到d维整数网格的函数f，我们考虑允许在f的像中进行高效正交范围搜索查询的数据结构，而无需显式存储该像。我们证明，如果f的形式为[N]→[2(w)](d)，其中w=polylog(N)，且可在常数时间内计算，那么对于任意0<α<1，我们可以得到一个使用O(N^{1-α/3})空间的数据结构，使得对于给定的d维轴对齐盒子B，可以在时间O(N^{-α})内搜索满足f(x)∈B的某个x∈[N]。(这里O(.)记法忽略了多项式对数因子。)利用类似技术，我们进一步获得了以下数据结构：• 用于范围计数和报告、前驱、选择、排序查询及其组合的数据结构，作用于集合f([N])；• 用于给定f值的前像大小和前像选择查询的数据结构；• 用于在d空间中点元组计算出的几何量上的选择和排序查询的数据结构。这些结果统一并推广了先前已知的3SUM索引和字符串搜索结果，可作为黑盒广泛应用于各类问题。特别地，我们给出了一种广义间隔字符串索引的数据结构，并展示了如何预处理整数网格上的点集，以便在次线性时间内高效计算：对于包含在给定轴对齐盒子中的点，计算它们的Theil-Sen估计量、第k大三角形面积或距离原点第k远的诱导超平面。

Keyword:

Function inversion

Data structures

String indexing

Computational geometry