用于高效检索集合中最近元素的数据结构

tl; dr如何才能像Mathematica的Nearest那样有效地实现？用于高效检索集合中最近元素的数据结构

Mathematica有一个名为Nearest功能，将采取“东西”的列表（它们可以是数字，在n维空间，字符串等坐标），并返回一个NearestFunction对象。此对象是一个函数，应用于x时，将返回最接近x某个距离度量标准的列表元素。距离度量可以作为参数传递给Nearest：默认情况下，它使用数值数据的欧氏距离和字符串的某种编辑距离。

实例（这将有望使这一问题更加清晰）：

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50]将返回58，最接近50的元素。 nf[50, 2]将返回两个最接近的元素{58, 39}。

问题：什么是实现这一功能的有效途径？ NearestFunction什么样的数据结构可能在内部使用？为不同类型的数据计算最近的元素的最佳复杂度是多少？

对于一个简单的数字列表排序他们和做一个二进制搜索将工作，但Nearest与多维数据以及与任意距离函数，所以我想它使用更通用的东西。但是，如果事实证明它专门用于某些类型的数据/距离功能，我不会感到惊讶。

来源

2012-02-27 Szabolcs

你见过：http://www.google.co.uk/search?q=adjacency+data+structure – Marcin 2012-02-27 10:19:30

@Marcin我对这个词不熟悉。 – Szabolcs 2012-02-27 10:21:53

对于性能良好的距离函数，有许多专门为此而优化的数据结构。对于多维数据，k-d tree（和其他binary space partitioning trees）可以给出优秀的nearest-neighbor searches，通常在次线性时间。您也可能想要查看metric trees，它们是经过优化的树结构，以支持最近邻居搜索的方式存储某些度量空间中的点。根据特定的度量空间（欧几里得距离，编辑距离等），不同的数据结构可能更合适或更不合适。

对于行为没有限制的任意距离函数（例如，甚至不包括三角不等式的事情），那么您可以做的最好的是线性搜索，因为距离函数可能对所有人都是无限的除了集合中的一个特定点之外的点。

希望这会有所帮助！

来源

2012-02-27 10:20:09 templatetypedef

优秀的总结！你给这两个关键字搜索（重要）和一些链接。 – Szabolcs 2012-02-27 11:33:58

它完全取决于数据和度量。阅读所有关于它的地方：Nearest Neighbour Search

来源

2012-02-27 10:22:18 YXD

你有没有注意到你的图标有swastik的形式？ – Marcin 2012-02-27 10:31:27

你是对的...我应该改变它的好东西。 – YXD 2012-02-27 10:32:53

@Marcin - 现在好了... – YXD 2012-02-27 10:39:43

用于高效检索集合中最近元素的数据结构

回答

相关问题