1

我有以下问题：

我正在寻找相似之处。因此，我有一个包含 200000 个条目的大源表和包含 10000 个条目的第二个表。现在我正在为每个表检索一个条目集，并将源表中的每一行与 java 中第二个表中的每一行进行比较（我正在使用一些 NeedleMan Gotoh 算法和类似的更复杂的算法）。这意味着要进行 10 亿次比较，这实在是太多太慢了……

目标是一个具有所有相似性的表（来自源表的 id、来自第二个表的 id 和相似性值）或至少类似于每个条目的最佳匹配（或最佳 x 匹配）......

谁能给我一些建议以在“正常”时间内进行此类计算？

编辑

主表

---+------+-------------+---------+-------+
id | name | address     | country | plz   | ...
---+------+-------------+---------+-------+
20 | Sony | Main Str. 1 | US      | 10000 |
---+------+-------------+---------+-------+

第二张表

---+------+-------------+---------+-------+
id | name | address     | country | plz   | ...
---+------+-------------+---------+-------+
30 | Soni | MainStr. 1  | US      | 10000 |
---+------+-------------+---------+-------+

目标（相似度表）：

---+---------------+--------------+-----------+
id | id_source_tbl | id_second_tbl| similarity|
---+---------------+--------------+-----------+
1  | 20            | 30           | 0.99      |
---+---------------+--------------+-----------+

simil_value 是一个值，表示源表中的公司与第二个表中的公司相同的可能性有多大

结果表明，这两行代表同一家公司...这两个条目只是因为拼写错误而有所不同...（0.99 是相似度，非常高 => 公司相同）相似度是用针线工计算的wunsch gotoh 算法（将 char 与 char 进行比较并考虑字符串中的位置等等......错别字应该导致高相似度值）

4

4 回答 4

1

这听起来像是一个令人尴尬的并行问题，因此作为第一步，您可以在多个内核和机器上进行分析。

于 2013-01-12T02:14:18.997 回答
1

通常让 MySQL 执行数据选择比检索海量数据集然后使用您自己的算法对其进行过滤更有意义。听起来您所做的只是一个相当简单的连接操作，例如：

SELECT source_id_column, second_id_column, similarity_column
FROM source_table, second_table
WHERE source_table.similarity_column = second_table.similarity;
于 2013-01-12T02:17:54.657 回答
0

在 SQL 中，您可以将其表示为：

选择 t1.id 作为 id1，t2.id 作为 id2，calculate_similarity(t1.name, t2.name) 作为来自 t1 交叉连接 t2 的相似度

现在，您要将相似度表定义为：

create table similarity (
    SimilarityID int not null auto_increment,
    id1 int,
    id2 int,
    similarity float
)

然后插入如下：

insert into similarity(id1, id2, similarity)
    select t1.id as id1, t2.id as id2,
           calculate_similarity(t1.name, t2.name) as similarity
    from t1 cross join
         t2

SQL 引擎应该并行执行交叉连接以及相似度计算。也许您有办法限制查询，例如要求公司处于相同的状态或以相同的字母开头。

于 2013-01-12T02:53:55.033 回答
0

其实问题是我自己做的...

我的解决方案如下：
1）不要重用连接，总是用相应的 ResultSet 关闭它们
2）使用事务
3）将工作拆分到线程
4）如果你和我一样，有单行的结果（一个单行的所有相似之处条目）并想在这个子结果上计算一些东西（就像在我的情况下，对于我想计算排名的所有相似之处），在 java 中执行此操作并使用子结果！！！！而不是事后在mysql中做

结果对我来说是大约 1 天的计算时间而不是 3 周...

谢谢您的帮助

于 2013-01-15T09:52:32.710 回答