Luí*_*ues 6 algorithm indexing search data-structures
试想一下,你有一大组#m具有属性的对象A和B.您可以使用哪种数据结构作为索引(或哪种算法)来提高以下查询的性能？
find all objects where A between X and Y, order by B, return first N results;
也就是说,按范围过滤A并按排序B,但只返回前几个结果(例如,最多1000个).插入非常罕见,因此可以接受繁重的预处理.我不开心以下选项:
与由乙排序记录(或索引):扫描中的记录/索引B顺序,返回第一个N,其中A相匹配XY.在最糟糕的情况下(很少的对象匹配范围XY,或匹配位于记录/索引的末尾),这变得O(m)很大,对于大型数据集来说,这m不够好.
使用按A排序的记录(或索引):执行二进制搜索,直到找到与范围XY匹配的第一个对象.扫描并创建k与范围匹配的所有对象的引用数组.按B排序数组,返回第一个数组N.那是O(log m + k + k log k).如果k很小那么确实如此O(log m),但如果k很大则排序成本甚至比所有m对象的线性扫描成本更差.
自适应2/1:对范围XY的第一个匹配进行二分搜索(使用A上的索引); 对该范围的最后一个匹配进行二进制搜索.如果范围很小,继续算法2; 否则回到算法1.这里的问题是我们回到算法1的情况.虽然我们检查了"很多"对象通过过滤器,这是算法1的好例子,但这个"很多"最多是一个常量(渐渐地,O(n)扫描将总是胜过O(k log k)排序).所以我们仍然有O(n)一些算法用于某些查询.
是否有算法/数据结构允许在次线性时间内回答此查询？
如果没有,那么达到必要性能的好处是什么呢？例如,如果我不保证返回对象的最佳排名B(召回<1.0),那么我只能扫描B索引的一小部分.但是,我能否以某种方式限制结果的质量呢？
您问的问题本质上是一个更通用的版本：
问：您有一个已排序的单词列表，每个单词都有一个关联的权重，并且您希望所有单词与给定查询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(log 2 n) 时间执行。它们中的任何一个都是次线性的，所以你应该没问题。
此外，列出所有条目的时间会给您的运行时间增加一个额外的 O(k) 因子。