V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
996635
V2EX  ›  问与答

google 是如何存储上亿 simhash 的?目标:存储并可快速匹配

  •  
  •   996635 · 2017-03-23 18:45:30 +08:00 · 3193 次点击
    这是一个创建于 2563 天前的主题,其中的信息可能已经有所发展或是发生改变。

    simhash 算法简单又高效.

    但是问题来了,如何对亿级 hash 进行存储,同时达到高效 查找的目的

    目前的做法:

    将 64bit 的 hash 分为 8 片, 然后分别以每片的值做 key,其余所有作为 set 的 value 存储在 redis 中,

    每次新来一个 hash 就将其分片,去 redis 查 8 次,然后遍历所有 再进行抑或得到海明距离小于 2 的结果.

    这样下来 每次查询都需要 100ms 左右, 请问有更好的方式么?

    7 条回复    2017-03-24 11:03:24 +08:00
    solos
        1
    solos  
       2017-03-23 19:39:00 +08:00
    可以分表吧
    paradoxs
        2
    paradoxs  
       2017-03-23 19:42:42 +08:00 via iPhone
    hadoop
    xiusedelang
        3
    xiusedelang  
       2017-03-23 19:46:47 +08:00 via Android
    这个查询技巧在谷歌的论文里也给出来了吧
    mooncakejs
        4
    mooncakejs  
       2017-03-23 20:32:11 +08:00 via iPhone
    用 8 个 redis
    wzha2008
        5
    wzha2008  
       2017-03-24 10:46:03 +08:00
    996635
        6
    996635  
    OP
       2017-03-24 10:55:59 +08:00
    @wzha2008 #5 这篇的回答被推翻了
    996635
        7
    996635  
    OP
       2017-03-24 11:03:24 +08:00
    @xiusedelang #3
    irl.cs.tamu.edu/people/sadhan/papers/cikm2011.pdf 你说的这篇吗? 貌似不好实现
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2873 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 13:50 · PVG 21:50 · LAX 06:50 · JFK 09:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.