快速最近邻搜索

Question

我有一个包含约三百万行记录的表格。每一行表示一个具有五个属性的对象。每个属性值都是浮点数，范围从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++）。

- a.oberon

---

请查看PostgreSQL的KNN搜索功能，例如http://www.sai.msu.su/~megera/postgres/talks/pgcon-2010-1.pdf。为了提供实际答案，我需要一些示例数据。 - Craig Ringer

Answer 1

进行快速KNN搜索需要能够在索引上执行此操作。使用自定义类型需要为该表指定整个索引支持范围，并编写函数来完成计算。因此，您需要做很多工作，答案并不简单。

您需要做的基本上是：

1. 查看支持的GIST运算符。 2. 编写支持计算任何或所有这些运算符的函数。 3. 创建将这些运算符绑定到GIST索引中的运算符类，最后 4. 使用该索引方法对整个表进行索引。如果您的表具有大字段，则可能会遇到问题（表继承可以帮助您解决问题，但这是另一个大主题）。

每个问题都足够广泛，可以成为自己的一系列问题，因此我认为您不能期望在这里得到解决方案。但这应该给您提供了一个基本路线图。

- Chris Travers