知识卡片

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

几何查询须计入预处理与输出

理解等级:中级

凸包可用排序加扫描构造;线段两两测试有 n(n−1)/2 对,报告所有交点至少需要输出相关工作;空间索引可加速多次最近邻或范围查询,但要计入建索引和更新成本。

书中给出的kd树 O(log n) 最近邻和 O(√n+r) 范围查询依赖维度、树平衡和输入等假设,不能作为任意数据分布下的保证;最坏情况下最近邻仍可能访问线性数量节点。

271指出小数据集或高维数据可能使kd树不划算;维度阈值不是普遍常数,应对目标分布、索引构建及查询负载做测量。

279提醒高维kd树可能退化,应比较构建、更新与查询总成本,而不是预设某个维度阈值。

280指出kd树可复用于最近邻和范围查询;两者分别基于距离下界和区域相交关系进行剪枝。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      计算几何经典问题 我们通过阐述一些经典问题来解释计算几何关注的领域。程序员要高效解决这些问题,首先必须理解一些在其他领域也非常有用的关键数据结构和算法技术。我们将会在阐述问题的过程中简单地描述和分析解决问题的原始算法,得知算法的期望运行时间。在本章剩余部分,我们将会提出一些更加优雅和高效的算法,这些

    • · 查看原书依据

      维数 随着维度的增加,构建kd树的开销也越来越大。一些权威人士认为,当维度超过20时,这个方法不如穷举高效。 输入的点数 当点很少时,构建kd树的开销大于其在性能方面的改善。

    • · 查看原书依据

      高维度下非常差,算法在高维度下,性能会退化。

    • · 查看原书依据

      kd树用途非常广泛,因此这个结构也能够为其他的算法用来改进效率。上述两种算法的高效得益于kd树的使用。

    参考来源

    - 位置:《算法技术手册》第9章《计算几何经典问题》(spine1646;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1609.html;u251-ch09-003)。 - 结论依据:251全文、03402–03409公式、图、代码及API表实读。 - 原始内容:计算几何经典问题 我们通过阐述一些经典问题来解释计算几何关注的领域。程序员要高效解决这些问题,首先必须理解一些在其他领域也非常有用的关键数据结构和算法技术。我们将会在阐述问题的过程中简单地描述和分析解决问题的原始算法,得知算法的期望运行时间。在本章剩余部分,我们将会提出一些更加优雅和高效的算法,这些 - 位置:《算法技术手册》第9章《使用环境》(spine1663;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1626.html;u271-ch09-003)。 - 结论依据:271指出小数据集或高维数据可能使kd树不划算;维度阈值不是普遍常数,应对目标分布、索引构建及查询负载做测量。 - 原始内容:维数 随着维度的增加,构建kd树的开销也越来越大。一些权威人士认为,当维度超过20时,这个方法不如穷举高效。 输入的点数 当点很少时,构建kd树的开销大于其在性能方面的改善。 - 位置:《算法技术手册》第9章《使用环境》(spine1670;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1633.html;u279-ch09-003)。 - 结论依据:279提醒高维kd树可能退化,应比较构建、更新与查询总成本,而不是预设某个维度阈值。 - 原始内容:高维度下非常差,算法在高维度下,性能会退化。 - 位置:《算法技术手册》第9章《驱动因素》(spine1671;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1634.html;u280-ch09-003)。 - 结论依据:280指出kd树可复用于最近邻和范围查询;两者分别基于距离下界和区域相交关系进行剪枝。 - 原始内容:kd树用途非常广泛,因此这个结构也能够为其他的算法用来改进效率。上述两种算法的高效得益于kd树的使用。