Locality Sensitive Hashing 问题 - 未名空间MITBBS历史存档

Locality Sensitive Hashing 问题# DataSciences - 数据科学

s*h2015-10-11 07:10

1 楼

有点不是很明白它的理念。
比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
to the same bucket，然后再从筛选过的结果中寻找？
所以减少的其实是复杂运算的次数？

n*r2015-10-11 07:10

2 楼

LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
你算单机的复杂度没太大意义
举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。

【在 s*********h 的大作中提到】

: 有点不是很明白它的理念。
: 比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
: 使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
: to the same bucket，然后再从筛选过的结果中寻找？
: 所以减少的其实是复杂运算的次数？

s*h2015-10-11 07:10

3 楼

多谢回复。
我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
。对于这个讲解我还是不太明白。

【在 n******r 的大作中提到】

: LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
: 你算单机的复杂度没太大意义
: 举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
: 当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
: 作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。

l*n2015-10-11 07:10

4 楼

这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如coke，和pepsi，是很类似的饮料，相比较juice或者酒
这个similarity你是知道的
如果用最原始的办法存储，比如是原始的明文
coke
7 up
orange juice,
vodka
stella beer
.... 此处省略一万行
pepsi
你不能把这些东西都存在内存里，太大了，想想一个字符多大。你只能存在disk上。
一个简单的查询，输入coke，那么和它相似的饮料是什么？你需要在disk上，一个一个
的看，每个entry都要用你已经知道的similarity metric看，哪个算是相似。比如查到
pepsi，你发现similarity score是0.9 － ok找到了，return它。
这个查询要在disk上，很慢。
这时候就要用lsh。每个长长的字符串，都会变成一个很短的binary string 比如
0101010
而且是binary string的similarity，比如不同的个数，和原来你知道的字符串的
similarity近似
binary的字符串是很小的，因为是binary，一个小内存可以存放million个entry所对应
的hash binary字符串
这样，再来同样的query，你需要把coke，用lsh变成一个字符串，比如000111，然后在
内存中很精简的binary字符串中查找，谁是000110？ binary的查找比string的查找快
多了，找到以后，你再用单独存的一个反向查找表看000110代表的是什么字符串－在我
们的例子里，是pepsi
总之，你说的那句话的意思，就是说lsh可以用来大大的提升这种呢similarity item的
search时间。方法就是把原来的item变成binary string，第一，小，可以放在内存，
第二，binary string的操作本身也很快

【在 s*********h 的大作中提到】

: 多谢回复。
: 我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
: 没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
: 。对于这个讲解我还是不太明白。

n*r2015-10-11 07:10

5 楼

楼上的回复讲得很细致了，简单的说LSH就是把data快速分成多份的方法，一般来说存
储也要相应优化才有意义
比如你有N个data，内存只能装N/1000个data，假设LSH之后对应这个signature的那一
份data小于N/1000个，那么你只需要读这份进内存比较，这个时候就装的下了
你原帖里面提到的复杂度是假设所有的数据都能load进内存的情况，如果数据远大于内
存，那么对总体性能起主要影响的是磁盘读写操作的次数而不是在内存里的计算复杂度
。如果使用简单比较，你需要读1000次磁盘，而LSH情况下只需要一次。

【在 s*********h 的大作中提到】

: 多谢回复。
: 我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
: 没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
: 。对于这个讲解我还是不太明白。

s*h2015-10-11 07:10

6 楼

有点不是很明白它的理念。
比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
to the same bucket，然后再从筛选过的结果中寻找？
所以减少的其实是复杂运算的次数？

n*r2015-10-11 07:10

7 楼

LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
你算单机的复杂度没太大意义
举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。

【在 s*********h 的大作中提到】

: 有点不是很明白它的理念。
: 比如用来寻找相似项。原本需要过O(N^2)遍，但是每一次比较需要的运算量比较大？。
: 使用LSH也是需要过至少O(N^2)遍，但是先通过简单的比较来把可能相似的项hashing
: to the same bucket，然后再从筛选过的结果中寻找？
: 所以减少的其实是复杂运算的次数？

s*h2015-10-11 07:10

8 楼

多谢回复。
我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
。对于这个讲解我还是不太明白。

【在 n******r 的大作中提到】

: LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
: 你算单机的复杂度没太大意义
: 举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
: 当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
: 作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。

l*n2015-10-11 07:10

9 楼

这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如coke，和pepsi，是很类似的饮料，相比较juice或者酒
这个similarity你是知道的
如果用最原始的办法存储，比如是原始的明文
coke
7 up
orange juice,
vodka
stella beer
.... 此处省略一万行
pepsi
你不能把这些东西都存在内存里，太大了，想想一个字符多大。你只能存在disk上。
一个简单的查询，输入coke，那么和它相似的饮料是什么？你需要在disk上，一个一个
的看，每个entry都要用你已经知道的similarity metric看，哪个算是相似。比如查到
pepsi，你发现similarity score是0.9 － ok找到了，return它。
这个查询要在disk上，很慢。
这时候就要用lsh。每个长长的字符串，都会变成一个很短的binary string 比如
0101010
而且是binary string的similarity，比如不同的个数，和原来你知道的字符串的
similarity近似
binary的字符串是很小的，因为是binary，一个小内存可以存放million个entry所对应
的hash binary字符串
这样，再来同样的query，你需要把coke，用lsh变成一个字符串，比如000111，然后在
内存中很精简的binary字符串中查找，谁是000110？ binary的查找比string的查找快
多了，找到以后，你再用单独存的一个反向查找表看000110代表的是什么字符串－在我
们的例子里，是pepsi
总之，你说的那句话的意思，就是说lsh可以用来大大的提升这种呢similarity item的
search时间。方法就是把原来的item变成binary string，第一，小，可以放在内存，
第二，binary string的操作本身也很快

【在 s*********h 的大作中提到】

: 多谢回复。
: 我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
: 没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
: 。对于这个讲解我还是不太明白。

n*r2015-10-11 07:10

10 楼

楼上的回复讲得很细致了，简单的说LSH就是把data快速分成多份的方法，一般来说存
储也要相应优化才有意义
比如你有N个data，内存只能装N/1000个data，假设LSH之后对应这个signature的那一
份data小于N/1000个，那么你只需要读这份进内存比较，这个时候就装的下了
你原帖里面提到的复杂度是假设所有的数据都能load进内存的情况，如果数据远大于内
存，那么对总体性能起主要影响的是磁盘读写操作的次数而不是在内存里的计算复杂度
。如果使用简单比较，你需要读1000次磁盘，而LSH情况下只需要一次。

【在 s*********h 的大作中提到】

: 多谢回复。
: 我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
: 没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
: 。对于这个讲解我还是不太明白。

s*h2015-10-11 07:10

11 楼

非常感谢！

【在 l******n 的大作中提到】

: 这个很好理解
: 比如你做一个数据查询服务，用来存储所有的饮料
: 比如coke，和pepsi，是很类似的饮料，相比较juice或者酒
: 这个similarity你是知道的
: 如果用最原始的办法存储，比如是原始的明文
: coke
: 7 up
: orange juice,
: vodka
: stella beer

s*h2015-10-11 07:10

12 楼

感谢！

【在 n******r 的大作中提到】

: 楼上的回复讲得很细致了，简单的说LSH就是把data快速分成多份的方法，一般来说存
: 储也要相应优化才有意义
: 比如你有N个data，内存只能装N/1000个data，假设LSH之后对应这个signature的那一
: 份data小于N/1000个，那么你只需要读这份进内存比较，这个时候就装的下了
: 你原帖里面提到的复杂度是假设所有的数据都能load进内存的情况，如果数据远大于内
: 存，那么对总体性能起主要影响的是磁盘读写操作的次数而不是在内存里的计算复杂度
: 。如果使用简单比较，你需要读1000次磁盘，而LSH情况下只需要一次。