Crate extended_collections[−][src]
extended-collections-rs
extended-collections
contains various implementations of collections that are not found in the standard library.
Usage
Add this to your Cargo.toml
:
[dependencies]
extended-collections = "*"
and this to your crate root:
extern crate extended_collections;
References
Almeida, Paulo Sérgio, Carlos Baquero, Nuno Preguiça, and David Hutchison. 2007. “Scalable Bloom Filters.” Inf. Process. Lett. 101 (6). Amsterdam, The Netherlands, The Netherlands: Elsevier North-Holland, Inc.: 255–61. doi:10.1016/j.ipl.2006.10.007.
Bera, Suman K., Sourav Dutta, Ankur Narang, and Souvik Bhattacherjee. 2012. “Advanced Bloom Filter Based Algorithms for Efficient Approximate Data de-Duplication in Streams.” CoRR abs/1212.3964. http://arxiv.org/abs/1212.3964.
Blelloch, Guy E., and Margaret Reid-Miller. 1998. “Fast Set Operations Using Treaps.” In Proceedings of the Tenth Annual Acm Symposium on Parallel Algorithms and Architectures, 16–26. SPAA ’98. New York, NY, USA: ACM. doi:10.1145/277651.277660.
Fan, Bin, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. “Cuckoo Filter: Practically Better Than Bloom.” In Proceedings of the 10th Acm International on Conference on Emerging Networking Experiments and Technologies, 75–88. CoNEXT ’14. New York, NY, USA: ACM. doi:10.1145/2674005.2674994.
Flajolet, Philippe, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007. “Hyperloglog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm.” In IN Aofa ’07: PROCEEDINGS of the 2007 International Conference on Analysis of Algorithms.
Heule, Stefan, Marc Nunkesser, and Alexander Hall. 2013. “HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm.” In Proceedings of the 16th International Conference on Extending Database Technology, 683–92. EDBT ’13. New York, NY, USA: ACM. doi:10.1145/2452376.2452456.
Kirsch, Adam, and Michael Mitzenmacher. 2008. “Less Hashing, Same Performance: Building a Better Bloom Filter.” Random Struct. Algorithms 33 (2). New York, NY, USA: John Wiley & Sons, Inc.: 187–218. doi:10.1002/rsa.v33:2.
Pugh, William. 1990a. “A Skip List Cookbook.” College Park, MD, USA: University of Maryland at College Park.
Pugh, William. 1990b. “Skip Lists: A Probabilistic Alternative to Balanced Trees.” Commun. ACM 33 (6). New York, NY, USA: ACM: 668–76. doi:10.1145/78973.78977.
Modules
arena |
Fast, but limited allocator. |
avl_tree |
Self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. |
bit_array_vec |
Growable list of bit arrays. |
bit_vec |
Growable list of bits. |
bloom |
Space-efficient probabilistic data structure to test for membership in a set. |
bp_tree |
Disk-resident N-ary tree. |
cuckoo |
Space-efficient probabilistic data structure to test for membership in a set with the ability to remove items. |
hyperloglog |
Space-efficient probabilistic data structure to count the number of distinct items in a multiset. |
lsm_tree |
Hybrid tree comprised of disk-resident sorted runs of data and memory-resident tree. |
radix |
Space-optimized trie. |
skiplist |
Probabilistic linked hierarchy of subsequences. |
sync |
Lock-free data structures. |
treap |
Probabilistic binary search tree where each node also maintains the heap invariant. |