他这个好像保证一个界的 window / range filter
Github: RangeFilteredANN
adversarially 对抗生成，75x （75倍）快于？召回率差不多
![[Pasted image 20241007142744.png]]
那我看的上一篇是啥？虽然可能也 trivial，没事了。
贡献：很多区间搜索方法（他这里叫 window search) （① 模块化基于树的框架 [我猜是线段树。。] modular tree-based framework（使用 Vamana ANNS 算法的特定实例化） and 标签空间划分方法 a labelspace partitioning approach. [讨论最优划分方法]）
感觉恨我理解意义上的通法很像，还会很bsaic吗？？
https://www.aimodels.fyi/papers/arxiv/approximate-nearest-neighbor-search-window-filters
这是ai生成的，搁着搁着。
他说不能支持动态的？
![[Pasted image 20241007144508.png]]
KD 树筛选举行
平凡做法
- prefiltering 前筛
- postfiltering 后筛
他们好像就是线段树。
Def
\((D, l)\) 一组数据 \(D\) 是空间 (\(R^{10}\)， \(l(x)\) 是 \(x\) 这个点的属性)
可以定义筛数据是 \(D_{(a,b)}\)
\(c\)-近似，不超过最小的 \(c\) 倍返回一个（而且在区间里）
算法
朴素 baseline
\(β-WST\) : Window Search Tree
分 \(\beta\) 份，但最后 \(<\beta\) 就不分了。
他就是 \(\beta\) （k） 叉线段树。。真的有用吗，（为啥我觉得不如正常二叉）
\(A(D)\) 创建一个新节点，然后存儿子和 每个儿子sz（）
4.2 查询线段树
就直接线段树分成 log 个节点查。
4.3 附加查询方法
OptimizedPostfiltering
找一个最大的区间后筛（我还以为是分治的，就最后扫吗，太蠢了》。。。最大的扩展区间也最多是两倍，就每次找 K 近的如果没有就倍增 (*2) 找，感觉有点笨的
ThreeSplit
找到最小的包含他区间然后执行两次 OptimizedPostfilering，没明白。。
SuperPostfiltering
任意数据结构
5. Theoretical Analysis
不想看了，感觉就线段树啊。。log
6. 实验
2.20GHz Intel Xeon machine with 40 cores and two-way hyper-threading, 100 MiB L3 cache, and 504 GB of RAM.
80 hyper-threads, query -> 16 threads.
separate 2.10GHz Intel Xeon machine with 96 cores and two way hyper-threading, 132 MiB L3 cache, and 1.47 TB of RAM
还返回了前十个的召回率。
Filter Fraction: \(1/2^i\) 这种意思
Data：没细看
查询方法超参：大部分都是正常线段树 \(\beta = 2\)。
![[Pasted image 20241009233107.png]]
看起来都是他的 Super Postfiltering 要好点，不太明白，就正常高线段树很菜？
![[Pasted image 20241009233432.png]]
这里看起来又是普通线段树好了？
总结
emm 感觉也没有啥创新 idea，就是复合了个 k 叉线段树上去（他说的主要贡献就是比暴力快 75倍，这很正常吧就因为暴力 \(O(n)\) 线段树 \(\log n\)，确实该这么快。。）（prefiltering）然后他的后筛相当于不是 log 哥区间了烧着一点
...
疑问：
- 他一开始说 c 近似，后面好像又跟 c 没关系了就是下找的？
不过 ICML 这种简短风格感觉比 SIGMOD 要舒服一点。（虽然可能是我理论和附录 skip 了 ...
可能的提升？
- 还是上一篇同样的，如果里面这个 ANN 结构支持可持久化存储前缀插入信息，这样就可以分治精准变成两个区间的查询。这样 \(\log\) 个就变成 \(2\) 个，速度应该还会快，但不知道他用的这个 Vamana 行不行，但我感觉我魔改一下 HNSW 应该会科学点（感觉挺有道理变快的。【相当于线段树其实不慢，但在第一个图里面比分治 *k的post乱搞慢一两杯左右，但感觉这个没保证的。。】
