w***g
发帖数: 5958 | 1 目前这个不是基于LSH的，而是用的KGraph。LSH和KGraph各有优缺。KGraph精度较高，
但是难以用精度换速度。LSH可以做得超快，但是精度较低。我已经找到一个愿意实现L
SH的同学了。计划把LSH也加进去，然后把索引做成可配置。我自己也研究过LSH，LSHK
IT就是我写的，有一些现成的LSH代码可以用，实现上应该没啥问题。刚才还收到
另一个对集群感兴趣的，不知道是不是你。K-NN搜索计算量太大，用集群来提高吞吐
量还可以，如果数据量大到要用机群来提高单个查询的速度，那吞吐量势必会非常低，
并由此导致各种稳定性问题。除非你每个查询能卖一笔钱，不然成本太大，可能会得不
尝失。
你那篇paper我认为很经典。L2 distance的话kmeans就是比以前那些基于random proje
ction的LSH要强（也就等于在很大程度上否认了之前LSH相关的研究）。这就是随机算法
和基于训练的算法的本质差异。
我这里有个Benchmark你可以看眼。KGraph比kmeans还快。KGraph目前没有开源，当初
想卖钱的，所以代码也按不开源的方式写了，为此还有一些速度上的损失。如... 阅读全帖 |
|
w***g
发帖数: 5958 | 2 正好我也是LSH专家。这个论文的方法我觉得:
1. 没法在GPU上实现，只能在CPU上实现。如果在GPU上做，他用LSH加速的
那部分计算iteration速度至少下降两倍。如果要evaluate出来他这个95%，
只能是算浮点数乘法的计算次数，但是随之来的是非乘法计算的增加，
cache hit rate降低，单次乘法速度变慢。这个牛吹得太大了。
2. 目前这个规模的网络用LSH是很难加速的，并且对准确度损失会很大。
并且我在2011年左右就已经实现了用社交网络算法吊打LSH并且对k-NN搜索
社区完成了拨乱反正。Benchmark在此：
https://github.com/erikbern/ann-benchmarks
kgraph是我的项目。最高那条线是个毛子，走的是我的路线。但我确实干不过他。
这paper很可能就是用了我implement的multi-probe LSH。
发明multi-probe的是我师姐, 但她的代码没公开。所以现在能找到的最
标准的multi-probe实现是我的版本。multi-probe针对的是内存不足的情况。
绝大部分引用multi-probe... 阅读全帖 |
|
l*******m
发帖数: 1096 | 3 lsh? 如果kd tree ball tree太慢，好像只有lsh。当然lsh有很多实现方法 |
|
n******r
发帖数: 4455 | 4 LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
你算单机的复杂度没太大意义
举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。 |
|
l******n
发帖数: 648 | 5 这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如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，一... 阅读全帖 |
|
n******r
发帖数: 4455 | 6 楼上的回复讲得很细致了，简单的说LSH就是把data快速分成多份的方法，一般来说存
储也要相应优化才有意义
比如你有N个data，内存只能装N/1000个data，假设LSH之后对应这个signature的那一
份data小于N/1000个，那么你只需要读这份进内存比较，这个时候就装的下了
你原帖里面提到的复杂度是假设所有的数据都能load进内存的情况，如果数据远大于内
存，那么对总体性能起主要影响的是磁盘读写操作的次数而不是在内存里的计算复杂度
。如果使用简单比较，你需要读1000次磁盘，而LSH情况下只需要一次。 |
|
n******r
发帖数: 4455 | 7 LSH一般用于常规手段不好解决的场合，比如数据量大，高维度，分布式存储的情况，
你算单机的复杂度没太大意义
举个简单例子，你可以把服务器排上号，LSH值相同的数据存在同一个服务器上，那么
当你要找一个输入相似项的时候，只需要LSH以后到对应的那个服务器去找就行了，操
作是local的。否则，你需要遍历整个网络所有服务器才能完成操作。 |
|
l******n
发帖数: 648 | 8 这个很好理解
比如你做一个数据查询服务，用来存储所有的饮料
比如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，一... 阅读全帖 |
|
n******r
发帖数: 4455 | 9 楼上的回复讲得很细致了，简单的说LSH就是把data快速分成多份的方法，一般来说存
储也要相应优化才有意义
比如你有N个data，内存只能装N/1000个data，假设LSH之后对应这个signature的那一
份data小于N/1000个，那么你只需要读这份进内存比较，这个时候就装的下了
你原帖里面提到的复杂度是假设所有的数据都能load进内存的情况，如果数据远大于内
存，那么对总体性能起主要影响的是磁盘读写操作的次数而不是在内存里的计算复杂度
。如果使用简单比较，你需要读1000次磁盘，而LSH情况下只需要一次。 |
|
a**********0
发帖数: 422 | 10 需要一个family of hash functions 具体大家都选用什么hash function呢？
另外wiki上写minhash是LSH的特例 我自己也觉得minhash也需要k个hash functions
但是大多数的document processing都把minhash和LSH算作独立的两个stage。。。 |
|
p*******r
发帖数: 71 | 11 新红楼与87版红楼或红楼梦原著 就像萝卜干和牛肉干
我爱吃袋装的牛肉干，有新口味的牛肉干出厂我绝对去买。最近，一家叫lsh的公司出
了盒装的牛肉干，于是我兴致勃勃地第一时间买来吃了。包装华丽丽，看上去也不错，
我急不可耐地撕开包装，结果发现是萝卜干。于是我怒了，提着盒子去找lsh，希望他
们能给我解释。结果人家说，袋装牛肉干与盒装牛肉干不是同一种东西，叫我区别对待
。我很郁闷，既然不是同一种东西，为啥你还要叫牛肉干呢？我将自己的疑惑告诉了周
围的人，其中一些人与我同感，但另外一些喜欢萝卜干的人的观点与我大有不同。
红雷梦托某：你不喜欢吃萝卜干就别吃啊，没人求你吃。
我：这话说的不错，但是因为它叫牛肉干所以我买来吃了，而且如果我不吃
，我怎么知道它实际上是萝卜干呢？
红雷梦托某：人家能生产出来已经不错了，你应该感谢人家，要不你连萝卜干
都吃不上呢。
我：不喜欢萝卜干，我情愿什么都不吃也不愿吃萝卜干啊。
红雷梦托某：有本事你自己去做！！
我：我买牛肉干吃，打开发现是萝卜干，我去找厂家投诉，结果厂家说有本事
你自己去生产。大家评评理，这合适么？
红雷梦托某：你只不过撕开包装看看，你又没吃，你 |
|
p*******r
发帖数: 71 | 12 我爱吃袋装的牛肉干，有新口味的牛肉干出厂我绝对去买。最近，一家叫lsh的公司出
了盒装的牛肉干，于是我兴致勃勃地第一时间买来吃了。包装华丽丽，看上去也不错，
我急不可耐地撕开包装，结果发现是萝卜干。于是我怒了，提着盒子去找lsh，希望他
们能给我解释。结果人家说，袋装牛肉干与盒装牛肉干不是同一种东西，叫我区别对待
。我很郁闷，既然不是同一种东西，为啥你还要叫牛肉干呢？我将自己的疑惑告诉了周
围的人，其中一些人与我同感，但另外一些喜欢萝卜干的人的观点与我大有不同。
红雷梦托某：你不喜欢吃萝卜干就别吃啊，没人求你吃。
我：这话说的不错，但是因为它叫牛肉干所以我买来吃了，而且如果我不吃
，我怎么知道它实际上是萝卜干呢？
红雷梦托某：人家能生产出来已经不错了，你应该感谢人家，要不你连萝卜干
都吃不上呢。
我：不喜欢萝卜干，我情愿什么都不吃也不愿吃萝卜干啊。
红雷梦托某：有本事你自己去做！！
我：我买牛肉干吃，打开发现是萝卜干，我去找厂家投诉，结果厂家说有本事
你自己去生产。大家评评理，这合适么？
红雷梦托某：你只不过撕开包装看看，你又没吃，你有什么资格说它不好。
我：好吧，那我吃完再评论
（吃 |
|
p*******r
发帖数: 71 | 13 新红楼与87版红楼或红楼梦原著 就像萝卜干和牛肉干
我爱吃袋装的牛肉干，有新口味的牛肉干出厂我绝对去买。最近，一家叫
lsh的公司出了盒装的牛肉干，于是我兴致勃勃地第一时间买来吃了。包装华丽丽，看
上去也不错，我急不可耐地撕开包装，结果发现是萝卜干。于是我怒了，提着盒子去找
lsh，希望他们能给我解释。结果人家说，袋装牛肉干与盒装牛肉干不是同一种东西，
叫我区别对待。我很郁闷，既然不是同一种东西，为啥你还要叫牛肉干呢？我将自己的
疑惑告诉了周围的人，其中一些人与我同感，但另外一些喜欢萝卜干的人的观点与我大
有不同。
红雷梦托某：你不喜欢吃萝卜干就别吃啊，没人求你吃。
我：这话说的不错，但是因为它叫牛肉干所以我买来吃了，而且如果我不吃
，我怎么知道它实际上是萝卜干呢？
红雷梦托某：人家能生产出来已经不错了，你应该感谢人家，要不你连萝卜干
都吃不上呢。
我：不喜欢萝卜干，我情愿什么都不吃也不愿吃萝卜干啊。
红雷梦托某：有本事你自己去做！！
我：我买牛肉干吃，打开发现是萝卜干，我去找厂家投诉，结果厂家说有本事
你自己去生产。大家评评理，这合适么？
红雷梦托某：你只不过撕开包装看看，你又没吃， |
|
h*i
发帖数: 3446 | 14 我正需要一个能作快速KNN的NoSQL数据库。有几个技术问题：
1. 你说这个是NoSQL,但大家一般想象中的NoSQL数据库都不是单机的，而是
distributed，这样可以横向scale，你这个也是这么打算的么？
2. 你这个技术是基于LSH的，对么？
3. 你对下面这片文章提到，简单的用K-means来实现LSH的办法怎么看？
L. Paulev ́e, H. J ́egou, and L. Amsaleg. Locality sensitive
hashing: a comparison of hash function types and querying
mechanisms. PR Letters, 2010
和这个比起来，你的技术有什么优势？ |
|
s*********h
发帖数: 6288 | 15 多谢回复。
我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
。对于这个讲解我还是不太明白。 |
|
s*********h
发帖数: 6288 | 16 多谢回复。
我是在看Ullman的讲解。他并没有特别提到LSH在分布式下的重要性。你说的这个确实
没错。但是我感觉Ullman的意思是用LSH可以把本来不可能塞下内存的查找塞进内存去
。对于这个讲解我还是不太明白。 |
|
|
a****a
发帖数: 3411 | 18 Mr Cameron also suggested that similar proposals would in future apply to We
lsh and Northern Irish MPs.
Mr Cameron pledged the unionist parties would keep promises made to Scotland
in the heat of the referendum campaign.
But he added: "In Wales, there are proposals to give the Welsh Government an
d Assembly more powers and I want Wales to be at the heart of the debate for
how to make our United Kingdom work for all our nations.
"In Northern Ireland, we must work to ensure the devolved instituti... 阅读全帖 |
|
|
|
|
|
t*********r
发帖数: 122 | 23 Supported Cars:
Acura ILX 2016 with AcuraWatch Plus
Due to use of the cruise control for gas, it can only be enabled above 25mph
Honda Civic 2016-2018 with Honda Sensing
Due to limitations in steering firmware, steering is disabled below 12 mph
Note that the hatchback model is not supported
Honda CR-V Touring 2015-2016
Can only be enabled above 25 mph
CR-V 2017 also works, but needs a special connector/Bosch Giraffe connector
see:
Honda Odyssey 2018 with Honda Sensing (alpha!)
Can only be enable... 阅读全帖 |
|
n***e
发帖数: 651 | 24 co lz, lsh first second |
|
l**********e
发帖数: 336 | 25 补充下，如果维度高的话，hashing不错，比如LSH～～ |
|
c****7
发帖数: 4192 | 26 LSH果然牛逼，tmd都是phd论文，让我interview怎么想出来，靠。 |
|
A*********c
发帖数: 430 | 27 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
A*********c
发帖数: 430 | 28 本来我是带着娱乐的态度来回帖的，但是既然碰到了大牛，请educate我。
请告诉我任意一个数据结构，比inverted list 更重要，并且广泛地应用到了实际的
text retrieval system中.
请告诉我任意一个document retrieval model，比vector space model 或者 Okapi
BM25, Statistically significantly better for general purpose document
retrieval. Either implemented in Lucene or Lemur.
请告诉我任意一个clustering algorithm，other than Kmeans，will be your safe
first choice of clustering when you see some arbitrary data.
对于Classification，Old Stuff Like KNN works well in many cases. Kernel
algorithms are go... 阅读全帖 |
|
a**********0
发帖数: 422 | 29 这个问题我自己解决了
LSH的某个scheme就是minhash的形式:
对集合S进行排列 每个元素将会有一个index 取一个S的子集 设为A 则A中每个元素皆
有一个permutated index 定义哈希函数为依照此permutation的最小的index 完全符合
minhash的定义 如何产生若干hash function？ 多取几个permutation就是了 |
|
|
a****f
发帖数: 17 | 31 lsh, locality sensitive hashing |
|
c**********n
发帖数: 13712 | 32 rebate还没做，东西就随手送朋友了，receipt上打印的是
PHYFRM LSH BS PURP |
|
n*****h
发帖数: 1334 | 33 物理系的熟人，大概就剩台湾小老头LSH乐.... |
|
|
|
s***o
发帖数: 6934 | 36 来自主题: Basketball版 - 科粉要淡定 lbj老去，还有千千万万的lsh，lgz站出来，不过这些跟科比毛关系？ |
|
|
s****y
发帖数: 18685 | 38 自然应该是LSH老上海，剑指篮坛大帝老北京
比较好 |
|
|
|
|
|
|
|
|
|
D********n
发帖数: 1595 | 47 看来是赤裸裸的地域歧视啊。
“上海”就比“吉林”强多了。 |
|
s****y
发帖数: 3071 | 48 吉林更好一点儿，双层含义表达得又含蓄
虽然我是上海人～ |
|
|
G**Y
发帖数: 33224 | 50 倾向于上Kerley，有点小伤，主场对IND
LSH好久没上场了，主场对Bills
J Jones对Texans？ |
|
