首页 文章

查询的数据结构/算法：按A过滤，按B排序，返回N个结果

提问于
浏览 次
6

想象一下，你有一大堆具有 A 和 B 属性的 #m 对象 . 您可以使用哪种数据结构作为索引（或哪种算法）来提高以下查询的性能？

find all objects where A between X and Y, order by B, return first N results;

也就是说，按范围 A 过滤并按 B 排序，但仅返回前几个结果（例如，最多1000个） . 插入非常罕见，因此可以接受繁重的预处理 . 我对以下选项不满意：

  • With records (or index) sorted by B ：以 B 顺序扫描记录/索引，返回第 N ，其中 A 与X-Y匹配 . 在最糟糕的情况下（少数对象匹配范围X-Y，或匹配位于记录/索引的末尾），这变为 O(m) ，对于大小为 m 的大型数据集来说，这不够好 .

  • With records (or index) sorted by A ：进行二分查找，直到找到第一个与X-Y范围匹配的对象 . 扫描并创建对与范围匹配的所有 k 对象的引用数组 . 按B排序数组，返回第一个 N . 那是 O(log m + k + k log k) . 如果 k 很小那么真的是 O(log m) ，但是如果 k 很大，那么排序的成本会比所有 m 对象的线性扫描成本更差 .

  • Adaptative 2/1 ：对范围X-Y的第一个匹配进行二分搜索（使用A上的索引）;对该范围的最后一个匹配进行二进制搜索 . 如果范围很小，则继续算法2;否则回到算法1.这里的问题是我们恢复算法1的情况 . 虽然我们检查了"many"对象通过了过滤器，这是算法1的好例子，但这个"many"最多是一个常数（渐近 O(n) 扫描）将永远战胜 O(k log k) 排序） . 所以我们仍然有一些 O(n) 算法用于某些查询 .

是否有算法/数据结构允许在次线性时间内回答此查询？

如果没有，那么为达到必要的性能有什么好的妥协呢？例如，如果我不保证返回对象 B 属性的最佳排名（召回<1.0），那么我只能扫描B索引的一小部分 . 但是，我能否以某种方式限制结果的质量呢？

algorithm search data-structures indexing

6 回答

  • 2

    你问的问题基本上是一个更通用的版本：

    问：您有一个排序的单词列表，其中的权重与每个单词相关联，并且您希望所有与给定查询q共享前缀的单词，并且您希望此列表按相关权重排序 .

    我对吗？

    如果是这样，您可能需要查看本文讨论如何在O（k log n）时间内执行此操作，其中k是所需输出集中的元素数，n是原始输入集中的记录数 . 我们假设k> log n .

    http://dhruvbird.com/autocomplete.pdf

    （我是作者） .

    更新：我可以补充的另一个改进是，您要问的问题与二维范围搜索有关，您希望在给定X范围内的所有内容和前一组中的前K，按Y范围排序 .

    2D范围搜索可让您找到X / Y范围内的所有内容（如果您的两个范围都已知） . 在这种情况下，您只知道X范围，因此您需要重复运行查询并在Y范围内进行二进制搜索，直到获得K结果 . 如果采用分数级联，则可以使用O（log n）时间执行每个查询;如果采用简单方法，则可以使用O（log2n）执行每个查询 . 它们中的任何一个都是次线性的，所以你应该没问题 .

    此外，列出所有条目的时间将为您的运行时间添加额外的O（k）因子 .

    回复于
  • 2

    假设 N << k < n ，它可以在 O(logn + k + NlogN) 中完成，类似于您在选项2中的建议，但节省了一些时间，您不需要对所有k个元素进行排序，而只需要N，这要小得多！

    数据库按A排序

    (1) find the first element and last element, and create a list containing these
    elements.
(2) find the N'th biggest element, using selection algorithm (*), and create a new 
    list of size N, with a second iteration: populate the last list with the N highest 
    elements.
(3) sort the last list by B.

    Selection algorithm：找到第N个最大的元素 . 它在这里是 O(n) 或 O(k) ，因为列表的大小是k .

    complexity ：
    第一步很简单 O(logn + k) .
    步骤2是 O(k) [选择]，另一个迭代也是 O(k) ，因为该列表只有k个元素 .
    第3步是 O(NlogN) ，一个简单的排序，最后一个列表只包含N个元素 .

    回复于
  • 1

    如果要返回的项目数量很少 - 最多约为项目总数的1％ - 那么简单的堆选择算法效果很好 . 见When theory meets practice . 但它不是亚线性的 .

    对于预期的子线性性能，您可以按 A 对项目进行排序 . 查询时，使用二进制搜索查找 A >= X 的第一个项目，然后使用我在该博客文章中概述的堆选择技术依次扫描项目直到 A > Y .

    这应该为初始搜索提供 O(log n) ，然后是 O(m log k) ，其中 m 是 X <= A <= Y 的项目数， k 是您想要返回的项目数 . 是的，对于某些查询，它仍然是 O(n log k) . 决定因素将是 m 的大小 .

    回复于
  • 1

    在A上设置segment tree，并为每个设置segment，预先计算范围中的前N个 . 要查询，请将输入范围分解为O（log m）段并合并预先计算的结果 . 查询时间为O（N log log m log m）;空间是O（m log N） .

    回复于
  • 2

    这不是一个完全充实的解决方案，只是一个想法 . 如何在A轴和B轴上构建quadtree？你会以一种广度优先的方式沿着树走下去;然后：

    • 每当你发现A值超出给定范围[X，Y]的子树时，就丢弃该子树（并且不递归）;

    • 每当你发现一个A值都在给定范围[X，Y]内的子树时，你就把那个子树添加到一个你自己的集合S中;

    • 每当你在[X，Y]范围内找到一些含有一些A值的子树时，你就可以进入它 .

    现在你有了所有最大子树的集合S，其中A坐标在X和Y之间;这些子树中最多有O（sqrt（m）），我将在下面给出 .

    其中一些子树将包含O（m）条目（当然它们将包含所有相加的O（m）条目），因此我们不能对所有子树的所有条目执行任何操作 . 我们现在可以在S中创建一堆子树，这样每个子树的B最小值小于堆中子节点的B最小值 . 现在从堆的顶部节点中提取B-minimal元素，直到你有N个;每当从具有k个元素的子树中提取元素时，您需要将该子树分解为不包含最近提取的元素的O（log（k））子树 .

    现在让我们考虑复杂性 . 找到O（sqrt（m））子树最多需要O（sqrt（m））步（读者练习，使用下面证明中的参数） . 我们应该在找到它们时将它们插入堆中;这将采用O（sqrt（m）* log（sqrt（m）））= O（sqrt（m）* log（m））步骤 . 从堆中的k元素子树中提取单个元素需要O（sqrt（k））时间来查找元素，然后插入O（log（sqrt（k）））= O（log（k））子树进入大小为O（sqrt（m））的堆需要O（log（k）* log（sqrt（m）））= O（log（k）* log（m））步 . 我们可能更聪明地使用势，但我们至少可以将k绑定为m，因此留下N （O（sqrt（k）log（k） log（m）））= O（N （sqrt（m） ）log（m）^ 2）= O（N * sqrt（m））步骤用于提取，O（sqrt（m）（N log（m）））步骤总数...在m中是次线性的 .

    这是O（sqrt（m））子树的界限的证明 . 构建四叉树有几种策略，但为了便于分析，我们假设我们制作了一棵二叉树;在根节点中，我们根据A坐标围绕具有中位A坐标的点分割数据集，然后我们根据具有中位B坐标的点周围的B坐标分割数据集（即，该半树中包含的一半点的中位数），并继续交替每个级别的方向 .

    树的高度是log（m） . 现在让我们考虑一下我们需要递归多少个子树 . 如果子树包含A坐标X，或者它包含A坐标Y或两者，我们只需要递归 . 在第（2 * k）级下，总共有2 ^（2 * k）个子树 . 到那时，每个子树的A范围已经被细分k次，每次我们这样做时，只有一半的树包含A坐标X.所以最多2 ^ k个子树包含A坐标X.同样，在大多数2 ^ k将包含A坐标Y.这意味着总共我们将递归到最多2 * sum（2 ^ k，k = 0 .. log（m）/ 2）= 2 *（2 ^（ log（m）/ 2 - 1）1）= O（sqrt（m））子树 .

    由于我们在第（2 * k）'级别检查最多2 ^ k个子树，我们还可以在该级别最多添加2 ^ k个子树到S.这给出了最终结果 .

    回复于
  • 2

    您描述的结果是大多数搜索引擎要构建的（排序，过滤，分页） . 如果您还没有这样做，请查看像Norch或Solr这样的搜索引擎 .

    回复于

相关问题