LSF-Join：局部敏感的偏置下分布所有对集相似性过滤
PDF格式 | 584KB |
更新于2025-01-16
| 191 浏览量 | 举报
2998
→
→
（
）
下
一
页
（
）
下
一
页
（）（）
(3)
≤ ≤
LSF - J oi n
：局部敏感的偏置下分布所有对集相似性过滤
赛勒斯
·
拉什奇安
UCSD
crashtchian@eng.ucsd.edu
Aneesh
SharmaGoogle
an
eesh@google.com
David P.
伍德拉夫
CMU
dwoodruf@cs.cmu.edu
摘要
全对集相似性是一个广泛使用的数据挖掘任务，即使
是大型和
高维数据集。传统上，相似性搜索集中在发现非常相似的对，其
中各种有效的算法是已知的。然而，最近的工作
已经强调了发现
具有
相对较小的交叉尺寸的集合对的重要性。例如，在推荐
系统
中，两个用户可能是相似的，即使他们的兴趣只在一小部分项
目上重叠。 在这样的系统中
，一些维度是高度偏斜的也是常见
的，因为它们非常流行。 这两个属性一起使得以前的
方法对于大
输入大小是不可行的。 为了解决这个问题，
我们提出了一个新的分
布式算法，
LSF-Join
，近似
所有对集相似性。算法的核心是基于局
部敏感过滤的随机选择过程特别是，我们的方法偏离了以前的近似算
法，这是
基于局部敏感哈希。理论上，我们表明，
LSF
连接有效
地找到最接近的对，即使是小的相似性阈值和倾斜的输入集。 我
们证明了
LSF-Join
的
通信，工作和最大负载的保证，我们还通过
实验
证明了它在多个图上的准确性。
CCS
概念
•
信息系统 最近邻搜索;协同过滤;社交网络;·计
算理论MapReduce算法。
关键词
相似性搜索，分布式算法，社交网络
ACM参考格式：
Cyrus Rashtchian
，
Aneesh Sharma
，
and David P.
伍德拉夫
2020
年。
LSF-Join
：局部敏感过滤，用于偏斜下的分布式所有对集相似性
。 在
网络会
议
2020
（
WWW
'20
）的会议记录，
2020
年
4
月
20
日至
24
日，台北，台湾。
ACM
，美
国纽约州纽约市，
7
页。
https://doi.org/10
。
1145
/3366423.3380069
1引言
相似性搜索是数据挖掘应用中广泛使用的原语，特别是所有对相
似性是常见的数据挖掘操作
[1
，
5
，
18
，
29]
。受推荐系统和社交
网络的启发，我们设计了用于计算所有对集合
相似性（也称为，
集合相似性连接）。特别是，我们认为
本文在知识共享署名
4.0
国际
（
CC-BY 4.0
）许可下发布。作者保留在其个人和公
司网站上以适当的署名传播作品的权利
WWW
©2020 IW 3C 2（国际万维网大会委员会），
在知识共享CC-BY 4.0许可下发布。
ACM ISBN 978-1-4503-7023-3/20/04
。
https://doi.org/10.1145/3366423.3380069
二分图中节点的相似性我们希望从图的一侧确定相似的节点
对对于右边的每个节点v，我们考虑它左边的邻域Γv等价地，
我们可以把Γv看作是图中v的邻居的集合 使用这种表示，许多
基于图的相似性问题可以被公式化为寻找
具有显著重叠邻域的
节点对。我们关注于表示为高维向量的
对Γ v和Γ u之间的余弦相
似性。
尽管集合相似性搜索在过去的几年中受到了广泛的关注，
在文献中，现代系统有三个方面尚未得到充分解决。具体地说，
我们的目标是开发
具有可证明保证的算法，并处理
以下三个标
准：
(1)
分布式和可扩展性。
该算法应该在
MapReduce
这样的分
布式环境中工作得很好，并且应该
使用大量处理器扩展
到大型图形。
(2)
相似度低
该算法应该输出具有相对低的归一化集合相似性
的大多数集合对，例如
取值0的余弦相似性τ的设置。1 τ
0。五、
极端倾斜。
即使维度（左边的度数）高度
不规
则和倾斜，该算法也应该可以很好地工作。
这些标准的动机来自推荐系统和社交网络。 对于第一个标准，
我们考虑
具有大量顶点的图。对于第二种情况，我们希望找到
语义相似但
余弦值不大的节点对。这种情况在协同过滤
和用户
相似
性中很常见[ 23 ]，其中两个用户可能是相似的，即使他
们在少量项目上重叠（例如，歌曲、电影或
引文）。以前的工
作未能处理所有上述三个
crite- ria
。当发现低相似性项目时（例
如，余弦相似度
0.5
），像局部敏感哈希
[13
，
24
，
31]
这样的标准
技术不再有效（因为哈希迭代的次数太大）。最近，有几个解决
这个问题的建议，最接近我们的是来自
[23]
的楔形采样然而，
[23]
中的方法有一个严重的缺点：它要求每个维度具有相对较低的频率
（即，二分图具有小的左度）。
在这项工作中，我们通过提出一种新的分布式
算法
LSF-Join
近似所有对相似性，可以扩展到具有高偏斜度的大
型图作为一个主要的贡献，我们提供了理论上的保证，我们的算
法，表明它达到了非常高的精度。 我们还提供了
通信，工作，并
在分布式环境中的最大负载
与大量的处理器的保证。
我们的方法使用局部敏感过滤（
LSF
）
[9]
。这是一
局部 敏感哈 希 （
Locality Sensitive Hashing
，
LSH
）。
LSF
和
LSH
之间的主要区别在于
LSF
构建了一个
下载后可阅读完整内容，剩余6页未读，立即下载
相关推荐
cpongm
- 粉丝: 6
我的内容管理
展开
最新资源
- Web远程教学系统需求分析指南
- 禅道6.2版本发布，优化测试流程，提高安全性
- Netty传输层API中文文档及资源包免费下载
- 超凡搜索：引领搜索领域的创新神器
- JavaWeb租房系统实现与代码参考指南
- 老冀文章编辑工具v1.8：文章编辑的自动化解决方案
- MovieLens 1m数据集深度解析：数据库设计与电影属性
- TypeScript实现tca-flip-coins模拟硬币翻转算法
- Directshow实现多路视频采集与传输技术
- 百度editor实现无限制附件上传功能
- C语言二级上机模拟题与VC6.0完整版
- A*算法解决八数码问题：AI领域的经典案例
- Android版SeetaFace JNI程序实现人脸检测与对齐
- 热交换器效率提升技术手册
- WinCE平台CPU占用率精确测试工具介绍
- JavaScript实现的压缩包子算法解读
