google guava>> pdstl>> 返回
项目作者： zaghaghi

项目描述 ：
Probabilistic Data Structure Template Library
高级语言： C++
项目地址: git://github.com/zaghaghi/pdstl.git
创建时间： 2020-05-24T20:13:01Z
项目社区：https://github.com/zaghaghi/pdstl
开源协议：Apache License 2.0
下载


PDSTL

Documentation Status
Build Status

PDSTL, is a header only template library for probabilistic data structures.

Build Example

To Build examples do as follows.

  1. # Setup project with meson
  2. meson build
  3. # Build with ninja
  4. ninja -C build -j 4
  5. # Build docs
  6. cd docs
  7. make html

Documentation

Read the reference documentations on pdstl.readthedocs.io

Implemented Data Structures

Membership

Data Structure Insert Delete
Bloom Filter Supported Not Supported
Counting Bloom Filter Supported Supported
Quotient Filter Supported Not Implemented
Quotient Hash Table Supported Not Implemented
Cuckoo Filter Supported Supported

Cardinality

Data Structure Insert Delete
Linear Counting Supported Not Supported
Flajolet–Martin Counting Supported Not Supported

References

  • Probabilistic Data Structures and Algorithms for Big Data Applications by Andrii Gakhov, 2019, ISBN: 978-3748190486 (paperback) ASIN: B07MYKTY8W (e-book)
  • Fan, L., et al. (2000) “Summary cache: a scalable wide-area web cache sharing protocol”, Journal IEEE/ACM Transactions on Networking, Vol. 8 (3), pp. 281–293.
  • Bender, M., et al. (2012) “Don’t Thrash: How to Cache your Hash on Flash”, Proceedings of the VLDB Endowment, Vol. 5 (11), pp. 1627–1637.
  • Fan, B., et al. (2014) “Cuckoo Filter: Practically Better Than Bloom”, Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, Sydney, Australia — December 02–05, 2014, pp. 75–88, ACM New York, NY.
  • Whang, K.-Y., Vander-Zanden, B.T., Taylor H.M. (1990) “A Linear-Time Probabilistic Counting Algorithm for Database Applications”, Journal ACM Transactions on Database Systems,
    Vol. 15 (2), pp. 208–229.
  • Flajolet, P., Martin, G.N. (1985) “Probabilistic Counting Algorithms for Data Base Applications”, Journal of Computer and System Sciences, Vol. 31 (2), pp. 182–209.