知识卡片
范围查询按区域关系裁剪
对空间索引节点,若其包围区域与查询区域不相交则跳过子树;若查询区域完全包含该节点区域,可直接收集整棵子树;部分相交时检查节点并递归相关子树。输出r个点至少需要 Ω® 的工作。
标准平衡kd树在固定维度和相应构造假设下可得到 O(n^(1−1/d)+r) 的范围报告界;实际边界处理、数据分布和维度影响性能,不能无条件套用。
278要求d维输入与查询区域一致;矩形边界是否包含、重复点是否逐个输出和空结果如何表示需由接口明确。
281正文有一处将包含关系写反;03445代码为 space.contains(region),即查询区域包含节点区域时收集子树,而不是节点区域包含查询区域。子树收集仍需逐个输出点。
282的03446–03449比较不同维度与查询区域;当结果包含全部n点,输出本身就是 Ω(n),并非低效算法的充分证据。实验的交叉点与数据、维度及实现相关。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 范围查询按区域关系裁剪
- · 输入/输出
- · 解决方案
- · 分析
原书出处 · 4 处
- · 查看原书依据
范围查询 有一个矩形区域R[xlow,ylow,xhigh,yhigh],以及一个点集P,请问P中哪些点是在矩形区域R中的呢?穷举算法会检查所有的点,花费的时间为O(n),我们能够做得更好么?使用kd树,我们将会阐述如何高效地解决在笛卡儿平面上的范围查询。 r是在R中的点的个数。当然,当点是d维时,
- · 查看原书依据
维度是数据的维度保持一致。
- · 查看原书依据
drain方法会遍历子树的所有节点,并且将这些点加入结果集中。 查询的区域包含节点n的点吗? 如果是的话,将这个点加入到结果集中。 查询区域会和n表示的点相交吗? 有两种方法可以检查这种情况:如果查询范围寻找n左边的点,那么遍历n的下子树,否则应该遍历上子树。
- · 查看原书依据
结果集中点的数目。随着维度的增加,性能逐渐下降。图9-25是一个O(n1-1/d)算法的期望性能,该图表明在小维度下,算法的性能逐渐逼近O(n)。因为还需要考虑r,所以实际性能将会偏离图9-25的理想曲线。 图 9-25 O(n1-1/d)算法的期望性能 我们很难生成测试范围查询算法性能的数据。我们