倒排索引的一些算法调研

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

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

 ## Comparisons of Set Intersections Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf) Algorithm | # of comparisons -----------|----------------: Sequential | 119479075 Adaptive | 83326341 Small Adaptive | 68706234 Interpolation Sequential | 55275738 Interpolation Adaptive | 58558408
## Comparisons of Set Intersections Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf) 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

+ 订阅