logo标签列表

如何使用固定范围进行高维范围查询？

algorithmkdtreerange-queryrange-tree
3
我有一个7维空间中的约10^4个点。为了某个应用程序，我需要做大约10^6次范围查询，以找到位于给定范围内的所有点。在该应用程序中，所有查询都使用相同的范围大小。对于这个问题，什么是合适的数据结构？
kd-tree似乎很合适，但对于7个维度和小输出大小的情况下，它的查询时间复杂度几乎是线性的。另一种方案是范围树，但对于此应用程序中输入数量较少的情况下建立它似乎过于复杂。此外，我没有看到任何这些结构将范围恒定大小作为优势利用的情况。例如，如果这是一个1D问题，则所有查询都会要求找到沿着数轴不同位置上大小为10的范围内的点。
这些查询是离线的还是需要按需执行？在在线情况下，我认为它们具有相同大小并不能给你任何东西。对于离线情况，我不确定，但您可以通过使用滑动窗口去掉一个维度。但这仍然可能不值得。 - Niklas B.
@NiklasB。这些查询是在线的，基于先前范围查询的结果生成的。 - Ashwin Nanjappa
哦，还有一个想法：如果你的点不是太密集，你可以将它们分成与查询大小相同的桶。一个查询最多会与这些桶中的2^d个（在你的情况下为128个）相交。如果点足够稀疏，这可能会节省一些严肃的工作。当然，然后还有一个问题，就是定位查询的正确桶，但是根据你的数据，可能没有太多非空桶，你可以使用线性搜索。当然，你也可以研究基于位置的哈希，但我认为如果你想要最优化，那并不是很好。 - Niklas B.
@NiklasB。谢谢！那是一个好主意。Samet在他的《空间数据结构》一书中建议使用这样一个单元大小等于范围大小的均匀网格。让我也看看基于位置的哈希。 - Ashwin Nanjappa
如果您的数据维度较小，比它们所嵌入的空间维度要小，那么值得研究一下Cover树。 - David Eisenstat
1个回答
0

嗯，这是一个晚回答，我不知道现在是否有用。您可以使用固定高度FQT（FHFQT或FHQT）[http://users.dcc.uchile.cl/~rbaeza/ftp/fqtrees.ps.gz]或固定查询数组（FQA）[http://www.dcc.uchile.cl/~gnavarro/ps/mtap01.pdf]。这些结构在这种相似性搜索中表现良好。此外，您需要使用良好的枢轴选择方法，如增量方法，以获得良好的结果。我假设您正在使用欧几里得距离，距离直方图是高斯分布。对我的英语表示抱歉...

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接