M***0 发帖数: 1180 | 1 附件中的auto suggestion应该是根据popularity score来决定提示哪5条信息的吧?
实现上,是用SQL database(分表?)来存储每个item和search count好,还是用自己
的代码实现好?如果是用自己的代码,是用heapsort吗?
数据量100M条,这个功能要用在ajax auto suggestion上,速度不能太慢。 |
i*****o 发帖数: 1714 | 2 能先透露一下打了f之后怎么把所有以f开头的掉出来吗?同理,再打个a,怎么把fa开
头的再掉出来?
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 附件中的auto suggestion应该是根据popularity score来决定提示哪5条信息的吧? : 实现上,是用SQL database(分表?)来存储每个item和search count好,还是用自己 : 的代码实现好?如果是用自己的代码,是用heapsort吗? : 数据量100M条,这个功能要用在ajax auto suggestion上,速度不能太慢。
|
M***0 发帖数: 1180 | 3 不清楚你是哪个环节不懂,简而言之:
client side makes AJAX call
server side does a String wildcard search and returns a list of result
问题是下面的提示item是有选择性的而不是“所有”
【在 i*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能先透露一下打了f之后怎么把所有以f开头的掉出来吗?同理,再打个a,怎么把fa开 : 头的再掉出来?
|
g*****g 发帖数: 34805 | 4 Build a prefix tree. For weight, I'll probably start with
geometry proximity and mixed in the number of time it's been
selected.
【在 i*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能先透露一下打了f之后怎么把所有以f开头的掉出来吗?同理,再打个a,怎么把fa开 : 头的再掉出来?
|
i*****o 发帖数: 1714 | 5 lz说用sql,我想半天sql怎么也做不出这么厉害的功能。那自己做所有的都在ram里吗
?怎么做persitent?
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Build a prefix tree. For weight, I'll probably start with : geometry proximity and mixed in the number of time it's been : selected.
|
M***0 发帖数: 1180 | 6 如果是存在sql table里,那最简单的,如果你的数据量小的话
e.g. Oracle: select xxx from ttt where xxx like ‘fa%’ where rownum <5
返回前5条fa开头的记录(在xxx上建个Index)
如果要按字母顺序,在rownum<5前加order by xxx
如果是要按popularity来排,加order by popularity
不用sql table的话,就是自己用代码建b-tree或binary-tree,把output写到硬盘,实
际上这个查询会是一直用的,所以是长期在内存里的,我们的内存是100GB
这两天我又想了想,今天和全组的人讨论了一下,决定用建几棵树分别记录单字母,双
子母,三字母,etc, up to五字母表或六字母表
单字母表
prefix(key) top_5_search
a apple, aol, american airline, amazon, applebees
b bestbuy, boa, bbc, bing, burger king
c ...
...
(当搜索栏输入第一个字母a的时候,下面提示框提示apple, aol, american airline,
amazon, applebees, 这个查询就非常快了,因为前5名的已经提前计算好并存在这里了)
双字母表
..
ap apple, apple store, applebees, apple tv, applebees coupon
...
这个top 5不是什么time critical的东西,不需要real time update,所以虽然我们那
100M条记录会一直更新被搜索的次数,但是完全可以每24小时,e.g. at midnight再
来更新以上那些表,而实际上那些表被更新的可能性不大,因为top 5一般一直不怎么变
上面那几个表不大(比如zzzzz开头的总搜索量太小所以zzzzz根本不用出现在五字母表,
这个可以大大减少记录条数),用sql table完全可以了。
我们用自己的代码建树,是因为我们的代码是现成的,job schedule to rebuild
the tree at certain time interval也是现成的,所以就不劳烦sql database了
最后就是如果输入是6,7个以上的字母,就没这个字母表了,直接到原始的那个完整tree里
去查询top 5 popularity,一旦匹配了6,7个字母,数据量就不大了
这个是初步计划,实现起来可能会有预想不到的问题,不知道有没有有经验的人能帮忙看看
【在 i*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lz说用sql,我想半天sql怎么也做不出这么厉害的功能。那自己做所有的都在ram里吗 : ?怎么做persitent?
|
i*****o 发帖数: 1714 | 7 如果有现成的100m的数据库的话,你能不能先做一个你说的select,我很想知道这个要
用多长时间。谢谢啦:)
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是存在sql table里,那最简单的,如果你的数据量小的话 : e.g. Oracle: select xxx from ttt where xxx like ‘fa%’ where rownum <5 : 返回前5条fa开头的记录(在xxx上建个Index) : 如果要按字母顺序,在rownum<5前加order by xxx : 如果是要按popularity来排,加order by popularity : 不用sql table的话,就是自己用代码建b-tree或binary-tree,把output写到硬盘,实 : 际上这个查询会是一直用的,所以是长期在内存里的,我们的内存是100GB : 这两天我又想了想,今天和全组的人讨论了一下,决定用建几棵树分别记录单字母,双 : 子母,三字母,etc, up to五字母表或六字母表 : 单字母表
|
a9 发帖数: 21638 | 8 建上索引的话应该瞬间就完成了。
,实
【在 i*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果有现成的100m的数据库的话,你能不能先做一个你说的select,我很想知道这个要 : 用多长时间。谢谢啦:)
|
z***e 发帖数: 5393 | 9 用现成的search server,比如solr.
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 附件中的auto suggestion应该是根据popularity score来决定提示哪5条信息的吧? : 实现上,是用SQL database(分表?)来存储每个item和search count好,还是用自己 : 的代码实现好?如果是用自己的代码,是用heapsort吗? : 数据量100M条,这个功能要用在ajax auto suggestion上,速度不能太慢。
|
c****e 发帖数: 1453 | 10 If you put the whole thing in memory, it's best. Or you can put your trie db
on SSD. The disk IO response will be much much better. The uniram, bigram,
N-gram subtrees are essentially a hash-map based cache. You can tweak that
later.
For your complete trie When the depth is larger than a threshold, at each node you can remember top 5 from its children. Since you rebuild the whole thing everyday, computiation is not a concern. You can adjust the threshold to manage storage whithin your budget.
To get better scalability, you can partition the tree into multiple machines
, the add a simple aggregator before returning results to frontend. Of
course cache can be deployed at each level to reduce better latency.
There are many things you can do. But I think the basic approach should just
work.
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是存在sql table里,那最简单的,如果你的数据量小的话 : e.g. Oracle: select xxx from ttt where xxx like ‘fa%’ where rownum <5 : 返回前5条fa开头的记录(在xxx上建个Index) : 如果要按字母顺序,在rownum<5前加order by xxx : 如果是要按popularity来排,加order by popularity : 不用sql table的话,就是自己用代码建b-tree或binary-tree,把output写到硬盘,实 : 际上这个查询会是一直用的,所以是长期在内存里的,我们的内存是100GB : 这两天我又想了想,今天和全组的人讨论了一下,决定用建几棵树分别记录单字母,双 : 子母,三字母,etc, up to五字母表或六字母表 : 单字母表
|
|
|
l*******s 发帖数: 1258 | 11 不行,solr太慢了。那玩意是全文索引的,不是用来搞query提示的。
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用现成的search server,比如solr.
|
p*****b 发帖数: 291 | 12 GOOGL的用什么不知道,但你的绝对用SOLR(JQuery AutoCompletion PLugin) 肯定就可以了.
这就是SOLR的强项,而用DATABASE就完全不行了.去SOLR的网站去研究下如何定义
FIeld type, field,handler,和如何DUMP 数据从
Database 到SOLR index engine.非常有意思.
Solr这个基于LUCENE的开源INDEX/SEARCH Engine现在非常火,
但大多数WEB应用开发人员还不知道. |
M***0 发帖数: 1180 | 13 谢谢楼上各位
solr/lucene我们研究过了,速度太慢。我们自己的源代码,功能和lucene几乎完全相
似,但是针对我们自己的业务定制和优化过的,Performance比lucene好不少
lucene相当generic,适用于各种领域,比较适合小型项目,也因为它的优点,使得它针
对性不够强 |
M***0 发帖数: 1180 | 14 谢谢 your suggestion is invaluable! 有一处我没太懂,please see below
trie
db
bigram
,
that
each
node you can remember top 5 from its children. Since you rebuild the
whole
thing everyday, computiation is not a concern. You can adjust the
threshold
to manage storage whithin your budget.
你是指full tree只需存贮排名前5的children以节省时间/空间吗?
machines
should
just
good idea!不过我们的数据量还没那么大。我们现在先测试single machine,如果
performance不好,就改成你说的。
【在 c****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : If you put the whole thing in memory, it's best. Or you can put your trie db : on SSD. The disk IO response will be much much better. The uniram, bigram, : N-gram subtrees are essentially a hash-map based cache. You can tweak that : later. : For your complete trie When the depth is larger than a threshold, at each node you can remember top 5 from its children. Since you rebuild the whole thing everyday, computiation is not a concern. You can adjust the threshold to manage storage whithin your budget. : To get better scalability, you can partition the tree into multiple machines : , the add a simple aggregator before returning results to frontend. Of : course cache can be deployed at each level to reduce better latency. : There are many things you can do. But I think the basic approach should just : work.
|
p*****b 发帖数: 291 | 15
那你们的要求太高了.我们的数据量只有你的四分只一(50Million),
Solr即使随便放在一台五年前的老旧DELL上,速度都是可以接受的.
你的好象还只是Begin with类型的search.如果,我们配一个适合这种类型的field,
并只Search这个Field,速度应该 还会大幅提高.
Sol用于中型作用的数据,应该还是可以胜任的.
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢楼上各位 : solr/lucene我们研究过了,速度太慢。我们自己的源代码,功能和lucene几乎完全相 : 似,但是针对我们自己的业务定制和优化过的,Performance比lucene好不少 : lucene相当generic,适用于各种领域,比较适合小型项目,也因为它的优点,使得它针 : 对性不够强
|
z***e 发帖数: 5393 | 16 可以的,已经有这个feature了。而且谁给你说solr只能用于全文检索?明明是你自己
define不同的field和type,然后分别建立index.
【在 l*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不行,solr太慢了。那玩意是全文索引的,不是用来搞query提示的。
|
l*******s 发帖数: 1258 | 17 我说的全文索引,不是狭义的指某篇文章的全文,这里全文说的是对给定的某段text的
索引,因此也包括你说的define不同的field和type。当年我还把POS tagging跟
chunking加进去做索引呢。
至于新feature,已经两年不用了,这个不了解。
【在 z***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可以的,已经有这个feature了。而且谁给你说solr只能用于全文检索?明明是你自己 : define不同的field和type,然后分别建立index.
|
c****e 发帖数: 1453 | 18 It's simiar to your hash-map cache idea. You can cache the top 5 ranked
words at any level in the trie, ranther than only from root.
【在 M***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢 your suggestion is invaluable! 有一处我没太懂,please see below : : trie : db : bigram : , : that : each : node you can remember top 5 from its children. Since you rebuild the : whole
|