Abstract: 就是 ANNS 加了一个范围查询（每个点多个属性，每次查询一个区间），为啥不是线段树来着。他说 《Segment Graph （查前缀 \(O(n)\)）》《2D Segment Graph（查区间构建 \(O(n \log n)\)）》

2. Preliminary

有太多 ANNs 负责优化找到的正确率？？

2.1 问题定义

\(I_A\) 属性区间
\(\mathcal{D}[I_A]\)： \(n\) 个点有哪些点属性在这个区间里
排完序 \(\mathcal{D_{i,j}}\) 每个对应一个区间 \([i, j]\)，这个二分可以找。
这样查询变成了 \(Q = (q, [i, j], k)\) 区间 KNN （q 是点

2.2 Graph-based ANNS - HNSW

保证图度数 \(\le M\)，空间 \(O(nM)\)

算法 1 - HNSW 上搜 KNN

ANNSEARCH(G, q, ep, K)
初始化就是 ep，选 K 个，每次维护一个答案集合 (ann) 和小根堆 (pool) 每次选出没访问最小的然后把出边当成候选扔进来。

算法 2 - 加边

构建：迭代算法（加边
EdgeInsertion
就是找一个点（任意顺序考虑每个点）的 knn（注意这个 knn 是现在 HNSW 图跑出来的） 然后连边 控制最大度数会剪枝 （PRUNE 策略之后写）

Domination （剪枝 base）

给定中心 \(o\)，\(u\) 支配 \(v\) 就是 \(d(o, u), d(u, v) < d(o, v)\) （\(ov\) 是三角形最长边？？？
![[Pasted image 20240924095437.png]]
中垂线右边

算法 3 - 剪枝

按照 \(d(o, u)\) 从小往大，每次排除一个半平面（中垂线。
这个剪枝判断有没有排除半平面是暴力平方的也太笨了。。感觉可以优化，不过 n 维超平面可能也有点难

算法 4 - 随机建图

随一个顺序跑 2。。

Idea?

HNSW 这个结构还是很简介的，如果采取这个范式可以考虑调整的有（还是说所有 Graph-based 都这样差不多？？

• 什么时候 dominate？他那个条件其实有点微妙的，直觉肯定是距离短，然后他还附加一个他们也没有太远，相当于三角形最长边 ... 不过还是比较难想象这样什么情况会找不到什么情况会找到。。
• 他这里剪枝控制度数 \(M\) 相当于指保留最小 \(M\) 个不冲突的（？
• 每次迭代用的图是之前的。。这有点神秘啊。。然后他的算法每次 eq 开始是 1 钦定其实可能和随机差不多？

3. RFANNS Half-bound (前缀)

都是在线查询，如果能离线就不用可持久化了。。

3.1 Baseline

按 \(v_{1\rightarrow n}\) 顺序跑算法 2 每个时刻就是那个图，提前预测用可持久化思想记一下就行了（，我也会！每次相当于就有加边删边操作，然后你要查询每个历史版本。。思考一下。。搞个可持久化数组，每次把改变出边的点的邻接表开头搞一下，不过如果可持久化数组是可持久化线段树的话每搞一个点就要 \(\log n\) （要么预处理 \(O(n^2)\) 查询 \(O(1)\) 要么都是 \(\log n\)）。。那好像不如他，他还是比较厉害）

3.2 区间图

观察到每个边出现是一个时间区间（或者说前缀区间）（有点高妙，有这个性质我 3.1 的思路可以优化一下，但还没法瞬间会）
他先规约成 \((v_j, b, e) \in G_{v_i}\) 了

算法 5 -

用算法 4 的范式 \(1 \rightarrow n\) 插入点，然后把每个边属于的区间记下来了。。
注意这里判断是否 \(> M\) 是看如今还到结尾的所有边（。。就是现存的边拉，不是的之前删了）

他用这个区间图相当于只走区间包含 \(z\) 这个前缀（时间戳的点）

这个定理 6 也是显然的，没明白为啥要证。。

算法 6 -

就是在这个前缀上搜，同算法 1
**但他好像就是 for 所有的出边 check z 是不是在这个区间里，。。。如果一个点出边很多但一个时刻保证 \(\le M\) 他就爆了。。但感觉这个图是均匀随机的，好像区别不大，这太蠢了。。所以效率没区别

所以感觉他这个前缀优化就是把整个图减出来了然后多个区间，这个图还是完整的图，结果在上面暴力 if。。说不定比我的 log 快

4. 任意区间查询*

4.1 二维区间图

\(G_z\) 是 \(z\) 开始的后缀建的这个区间图。
然后他的观察 2 是每个边在存在的 \(G\) 也是个区间（这个有点难想，很神奇。

算法 7

跟 6 一样只不过两维度的限制。。

注意这个区间严格在那个边存在区间的签名，这个比较显然。。

算法 8

先不剪枝了（就是邻居 >M摆烂不管了***），可以把那个区间图搞出来，\(j\) 从 1 到 n 插入，然后设一个 \(i\)，每次找 \([i, j - 1]\) 的 KNN，找里面下表最小的 \(i'\) 然后 \(i = i' +1\)，相当于 \([i, i']\) 这里开始 KNN 都是这 n 个，然后边也是一样的，然后期望好像是对的。。（\(\log\) 个。
最坏 \(O(n^2M)\) 笨死了。
平均调用 KNN 搜 \(O(n \log n)\) 次（调用算法 7 次数
除掉搜是 \(O(nM^2 \log n)\) 的？好吧一次剪枝是 \(O(M^2)\) 的也很笨。
所以你这算法不保证度数了吗？？

4.2 Leap Optimizations

优化 1

\(i'\) 设置成剪枝完的最左边的。

优化 2

设置成最右边的，那就跳麻了，但信息全错了。
还有设置成中位数的，那也有点错。

4.3 Discussions

conjunctive query and 查询

他比我的线段好的就是他多个 if 就行了，但我多维度就炸了。。但我感觉我一维效果比他好的应该。而且他这个只能把一个当索引，另外一个限制相当于没用，但我线段树降一维肯定是好的或者总用一个 \(\log\) 降维，\(k\) 个就是 \(\log ^k\) （但可能就不如 bitset 了。

disjunctive or

可以两个分别做合并
Using One Index on Multiple Attributes. 两队建立大小关系也行。那不就是一个 等于白说。

他总结的限制。

1. 他觉得 and 查询只有一个索引主太笨了。multiple：（但想我之前说的，多一个多个 log
2. 而且他说只能插入最大的值。。

总结

1. 看了 15 页，感觉基本理解了，舒适区。
2. 可能提升的点：
   • \(O(M^2)\) 剪枝函数，每次抠掉半平面，相当于高维半平面交，能做吗？好像有点难
   • Half-bound 他是暴力 if 所有边的，但没给出一个整个图出度的限制 （但随机意义感觉就是 \(O(M)\) 的？，如果度很大，那不如用可持久化数组，这样就不用遍历所有边了。
   • 二维区间图没明白，他好像没减掉邻居的>M啊？他是摆烂不管了吗？要回去看代码。。确认一下。
     • 如果我用普通的线段树，那构造和搜索好像完全和这个是一样的 \(O(nM^2 \log n)\) 的。（每个节点把那些插进去，如果这么比，这个算法虽然看起来复杂，但好像被严格替代了（除了查询部分，是在 \(\log\) 个图上找而不是一个，但 \(\log n\) 个图变小了，有好处吗？并行找回变快吗）。。而且还不是平均随机 \(\log n\) 是严格对的。要跑实验试一下吗？
     • 如果用分治+两个拼用他一维的做，好像复杂度和普通线段树的一样的，然后多一个好处是不是 \(\log\) 个图而是两个图。而不用管那个破二维区间了。

5. 实验

先和自己比。这相当于就是调参的过程然后写进论文水了4页。。
然后和别人比，别人好像也都是暴力扫（存疑，没好好看），那可不快么。。用 grid search 把最优参搜出来了

注意区间小的时候跑的不好，不如搞个暴力，最底下分块暴力之类的（不过我觉得我的线段树应该不会太差）
https://www.cnblogs.com/dmoransky/p/14957063.html

为啥这些 recall 都那么高，高达 0.9x 正确率也太高了吧。。。

6. 相关工作

太乱了不好好看