知识卡片

普通读书笔记卡 · 8093.q.6 · 生成模型:未记录

范围查询按区域关系裁剪

理解等级:中级

对空间索引节点,若其包围区域与查询区域不相交则跳过子树;若查询区域完全包含该节点区域,可直接收集整棵子树;部分相交时检查节点并递归相关子树。输出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)算法的期望性能 我们很难生成测试范围查询算法性能的数据。我们

    参考来源

    - 位置:《算法技术手册》第9章《范围查询》(spine1669;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1632.html;u277-ch09-007)。 - 结论依据:277全文及03443–03444公式与伪代码实读。 - 原始内容:范围查询 有一个矩形区域R[xlow,ylow,xhigh,yhigh],以及一个点集P,请问P中哪些点是在矩形区域R中的呢?穷举算法会检查所有的点,花费的时间为O(n),我们能够做得更好么?使用kd树,我们将会阐述如何高效地解决在笛卡儿平面上的范围查询。 r是在R中的点的个数。当然,当点是d维时, - 位置:《算法技术手册》第9章《输入/输出》(spine1669;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1632.html;u278-ch09-007)。 - 结论依据:278要求d维输入与查询区域一致;矩形边界是否包含、重复点是否逐个输出和空结果如何表示需由接口明确。 - 原始内容:维度是数据的维度保持一致。 - 位置:《算法技术手册》第9章《解决方案》(spine1672;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1635.html;u281-ch09-007)。 - 结论依据:281正文有一处将包含关系写反;03445代码为 space.contains(region),即查询区域包含节点区域时收集子树,而不是节点区域包含查询区域。子树收集仍需逐个输出点。 - 原始内容:drain方法会遍历子树的所有节点,并且将这些点加入结果集中。 查询的区域包含节点n的点吗? 如果是的话,将这个点加入到结果集中。 查询区域会和n表示的点相交吗? 有两种方法可以检查这种情况:如果查询范围寻找n左边的点,那么遍历n的下子树,否则应该遍历上子树。 - 位置:《算法技术手册》第9章《分析》(spine1673;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1636.html;u282-ch09-007)。 - 结论依据:282的03446–03449比较不同维度与查询区域;当结果包含全部n点,输出本身就是 Ω(n),并非低效算法的充分证据。实验的交叉点与数据、维度及实现相关。 - 原始内容:结果集中点的数目。随着维度的增加,性能逐渐下降。图9-25是一个O(n1-1/d)算法的期望性能,该图表明在小维度下,算法的性能逐渐逼近O(n)。因为还需要考虑r,所以实际性能将会偏离图9-25的理想曲线。 图 9-25 O(n1-1/d)算法的期望性能 我们很难生成测试范围查询算法性能的数据。我们