添加994字节、
2018年8月22日 (三) 13:43 关系代数 （Relational Algebra）
=集合运算=
==集合（Set）==
For a set of integers: S = {1, 2, 3, 1000}. Set operations include:
membership test: x ∈ S?
Set intersection: S1 ∩ S2
Set union: S1 ∪ S2
Set differences: S1 ∖ S2
Jaccard Index (Tanimoto similarity) ∣S1 ∩ S2 ∣/∣S1 ∪ S2 ∣
==有序集合（Ordered Set） ==
* Iterate:
in sorted order,
in reverse order,
skippable iterators (jump to first value ≥ x)
* Rank: how many elements of the set are smaller than k? (counting the number of ones up to a given position)
* Select: find the kth smallest value (finding the position of the k-th bit set)
* Min/max: find the maximal and minimal value
[https://lucene.apache.org/core/4_5_0/core/org/apache/lucene/util/BroadWord.html Broadword Implementation of Rank/Select Queries]
研究论文：
# Vigna, Sebastiano. "Broadword implementation of rank/select queries." In International Workshop on Experimental and Efficient Algorithms, WEA 2008.