快速最近邻搜索

Question

我有一个表，大约有300万行。每一行代表一个具有5个属性的对象。每个属性值都是浮点型，范围从0到1。

表声明为

CREATE TABLE tbl (
  OBJECT_ID integer,
  property_1 float,
  property_2 float,
  property_3 float,
  property_4 float,
  property_5 float
);

我必须找到与指定对象最相似的前10个对象。

我的问题是：

select T2.OBJECT_ID,
       sqrt(
         (T1.property_1 - T2.property_1)^2 +
         (T1.property_2 - T2.property_2)^2 +
         (T1.property_3 - T2.property_3)^2 +
         (T1.property_4 - T2.property_4)^2 +
         (T1.property_5 - T2.property_5)^2
       ) similarity
  from tbl T1, tbl T2
 where T1.OBJECT_ID = 42
 order by 2
 limit 10;

如何提高搜索最相似对象的性能？

任何解决方案都可以接受(oracle、postgres、noSQL或C++)。

Answer 1

要进行快速的KNN搜索，需要能够在索引之外执行此操作。这样做需要为该表指定整个索引支持范围，并编写函数来完成计算。所以你有很多工作要做，答案并不简单。

基本上，你要做的是：

1. 查看GIST运算符supported.
2. Write函数以支持计算所有这些运算符。
3. 创建一个运算符类，将这些运算符类绑定到一个GIST索引中，最后使用该索引方法对整个表进行
4. 索引。如果你的表有很大的字段，你可能会有问题(这里的表继承可以帮助你，但那是另一个大的主题)。

其中的每一个都足够广泛，可以用来解决一系列问题，所以我认为你不能期望在这里有一个解决方案。但这应该会给你一个基本的路线图。