Note - ICML24 - Approximate Nearest Neighbor Search with Window Filters

DMoRanSky / 2024-10-10 / 原文

他这个好像保证一个界的 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乱搞慢一两杯左右，但感觉这个没保证的。。】