我正在寻找一个空间索引,它可以有效地找到某个方向上最极端的 n 个点,即对于给定的 w,在数据集中找到 x[0:n],其中 x0 给出 wx 的最大值,而 x1 第二个wx 的最大值等...... 这种类型的查询有名称吗?什么是有效的数据结构?x 可能有大约 20 个维度。
谢谢!
我正在寻找一个空间索引,它可以有效地找到某个方向上最极端的 n 个点,即对于给定的 w,在数据集中找到 x[0:n],其中 x0 给出 wx 的最大值,而 x1 第二个wx 的最大值等...... 这种类型的查询有名称吗?什么是有效的数据结构?x 可能有大约 20 个维度。
谢谢!
该查询称为“top-k”查询,您可以使用排名立方体方法快速回答它。http://www1.se.cuhk.edu.hk/~hcheng/paper/vldb06_rankcube.pdf
本文没有推导时间复杂度。