sql - 快速最近邻搜索

Question

我有一个包含约 300 万行的表格。每行代表一个具有 5 个属性的对象。每个属性值都是 float ，范围从 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 运算符。

2. 编写函数来支持计算任何或所有这些。

3. 创建一个运算符类，将它们绑定(bind)到 GIST 索引中，最后

4. 使用该索引方法为整个表建立索引。如果您的表有大字段，您可能会遇到问题(这里的表继承可以帮助您解决问题，但这是另一个大话题)。

其中的每一个问题本身都足以解决一系列问题，因此我认为您不能指望在这里找到解决方案。但这应该给你一个基本的路线图。