3 ms·
Python and C++ standard libraries should include the prefix trie, suffix array, Bloom filter, T/Q Digest, and Count-min sketch. Also generic dense/sparse matrix
by crb002 8y ago
Python and C++ standard libraries should include the prefix trie, suffix array, Bloom filter, T/Q Digest, and Count-min sketch. Also generic dense/sparse matrix-matrix multiply, and lazy/streaming algorithm interfaces to operate on network supplied data.
- sitkack 8y agoMore importantly, those libraries should use the same on-disk representation so that bloom filters and HLL can be exchanged. Most libraries provide no way for these to be reused, or they require the library be everywhere. Some systems cannot install your (the library author's) libraries.
- TeMPOraL 8y agoThat's a serialization/deserialization problem, which is mostly orthogonal to the implementation of the data structure itself.
- sitkack 8y agoThe hashing algorithms and their configuration parameters need to be fully specified, or the whole lib needs to be compiled into WASM. We need a portable standard for the external encoding of Bloom and HLL that captures important internal implementation details. I can serialize a map as a list of key values, but I cannot do that with a Bloom filter. The same case could be made for maps, when one has multiple GB hashmaps, rehashing and inserting on load could make it untenable. CaptnProto aadresses some of this, but more work needs to done to treat the heap as a portable database with internal visibility.