倒排索引的一些算法调研-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

倒排索引的一些算法调研

简介:

下面的文章专门针对搜索引擎里的倒排列表 sorted sets研究交集算法,思路类似快排,非常值得一看

www.cs.ucr.edu/~stelo/cpm/cpm04/25_Baeza-yates.pdf
 

合并sorted sequence算法:

https://github.com/rklaehn/rklaehn.github.io/blob/master/_posts/2016-01-05-binarymerge.md

 

汇总资料:https://github.com/TechConf/CodeMash2016/blob/master/Great%20Galloping%20Cuckoos-%20Algorithms%20Faster%20than%20log(n)/index.html

关键信息:

  ## Comparisons of Set Intersections
   
  <small>Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)</small>
   
  Algorithm | # of comparisons
  -----------|----------------:
  Sequential | 119479075
  Adaptive | 83326341
  Small Adaptive | 68706234
  Interpolation Sequential | 55275738
  Interpolation Adaptive | 58558408
   
   
  </markdeep></section><section><markdeep>
  ## Comparisons of Set Intersections
   
  <small>Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)</small>
   
  Algorithm | # of comparisons
  -----------|----------------:
  Sequential | 119479075
  Interpolation Small Adaptive | 44525318
  Extrapolation Small Adaptive | 50018852
  Extrapolate Many Small Adaptive | 44087712
  Extrapolate Ahead Small Adaptive | 43930174

 

## Resources: Sets
  - [A Fast Set Intersection Algorithm for Sorted Sequences](http://www.cs.ucr.edu/~stelo/cpm/cpm04/25_Baeza-yates.pdf)
  - [Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences](https://cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf)
  - [Experimental Comparison of Set Intersection Algorithms for Inverted Indexing](http://ceur-ws.org/Vol-1003/58.pdf)
  - [Fast Set Intersection in Memory](http://research.microsoft.com/pubs/142850/p255-dingkoenig.pdf)
  - [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)
  - [Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions](http://www.vldb.org/pvldb/vol8/p293-inoue.pdf)
  - [SIMD Compression and the Intersection of Sorted Integers](http://arxiv.org/abs/1401.6399)

 

https://github.com/lemire/SIMDCompressionAndIntersection 

A C++ library to compress and intersect sorted lists of integers using SIMD instructions
里面提及的一些资料:

Documentation

This work has also inspired other work such as...

 
提及较多的:
https://github.com/Randl/CS/tree/master/Hwang-Lin













本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6591201.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: