这是一个创建于 1049 天前的主题，其中的信息可能已经有所发展或是发生改变。
有三个集合，集合里是一些可以度量相似度的东西，比如一个数，可以用绝对值来衡量相似情况，又比如一个向量，大概就是这个意思，数学上应该有比较正式的定义。。。
有没有一种比较好的方案，可以找出三个集合中，有哪些二元组或者三元组，对应是比较相似的。
比如以整数集合为例
A (1,2,3) B (1,100) C (10,4,3)
假设以绝对值来衡量，相似的阈值设为 2
那么就有
(A0 B0 C2) (A1 B0 C2) (A1 C1) (A2 C1)
等等
 |
1
ipwx 2022-01-09 14:16:40 +08:00
最好的算法不清楚。
使用 Ball-tree 配合应该能有复杂度 O(N log N) 的算法， 但是常数较大。具体方法就是对 ABC 三个集合建 Ball-tree ，然后 ABC 分别枚举每一个元素，在另外两个 Ball-tree 找 distance < threshold 的点，最后用 hashtable 对三元组去重。 目测最优算法也是 O(N log N) 的，但是常数比这个小。 |
|
2
ipwx 2022-01-09 14:17:41 +08:00
哦一维情况下可以对三个集合先排序，然后用二分查找代替建树。
|
|
3
ipwx 2022-01-09 14:18:17 +08:00
|
Select Language