Implementation of various data structures and algorithms in Go.Containers are either ordered or unordered. All ordered containers provide stateful iterators and some of them allow enumerable functions.
data-structure map tree set list stack iterator enumerable sort avl-tree red-black-tree b-tree binary-heap collections go-collectionGo-datastructures is a collection of useful, performant, and threadsafe Go datastructures.Interval tree for collision in n-dimensional ranges. Implemented via a red-black augmented tree. Extra dimensions are handled in simultaneous inserts/queries to save space although this may result in suboptimal time complexity. Intersection determined using bit arrays. In a single dimension, inserts, deletes, and queries should be in O(log n) time.
data-structure collections go-collectionBoom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable Bloom Filters, Counting Bloom Filters, Inverse Bloom Filters, Cuckoo Filters, several variants of traditional Bloom filters, HyperLogLog, Count-Min Sketch, and MinHash.Classic Bloom filters generally require a priori knowledge of the data set in order to allocate an appropriately sized bit array. This works well for offline processing, but online processing typically involves unbounded data streams. With enough data, a traditional Bloom filter "fills up", after which it has a false-positive probability of 1.
bloom-filter stable-bloom-filters cuckoo-filter probabilistic-programming counting-bloom-filters scalable-bloom-filters count-min-sketch data-stream filter data-structure collections go-collectionAn improved version of HyperLogLog for the count-distinct problem, approximating the number of distinct elements in a multiset using 20-50% less space than other usual HyperLogLog implementations.This work is based on "Better with fewer bits: Improving the performance of cardinality estimation of large data streams - Qingjun Xiao, You Zhou, Shigang Chen".
data-structure collections go-collectionThe missing set collection for the Go language. Until Go has sets built-in...use this.I have to give some credit for helping seed the idea with this post on stackoverflow.
set threadsafe datastructures data-structure collections go-collectionA Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item is a member of a set.A Bloom filter has two parameters: m, a maximum size (typically a reasonably large multiple of the cardinality of the set to represent) and k, the number of hashing functions on elements of the set. (The actual hashing functions are important, too, but this is not a parameter for this implementation). A Bloom filter is backed by a BitSet; a key is represented in the filter by setting the bits at each value of the hashing functions (modulo m). Set membership is done by testing whether the bits at each value of the hashing functions (again, modulo m) are set. If so, the item is in the set. If the item is actually in the set, a Bloom filter will never fail (the true positive rate is 1.0); but it is susceptible to false positives. The art is to choose k and m correctly.
bloom bloom-filters bloom-filter data-structure collections go-collectionThis is an implementation of DataFrames, Series and data wrangling methods for the Go programming language. The API is still in flux so use at your own risk.The term DataFrame typically refers to a tabular dataset that can be viewed as a two dimensional table. Often the columns of this dataset refers to a list of features, while the rows represent a number of measurements. As the data on the real world is not perfect, DataFrame supports non measurements or NaN elements.
data-structure collections go-collectionPackage bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.It provides methods for setting, clearing, flipping, and testing individual integers.
bitset data-structure collections go-collectionThe library is fully capable of working with non-ascii strings. But the strings are not normalized. That is left as a user-dependant use case. Please normalize the strings before passing it to the library if you have such a requirement.Words selected are - "levenshtein" and "frankenstein".
levenshtein levenshtein-distance data-structure collections go-collectionGo-rquad proposes various implementations of region quadtrees.A region quadtree is a special kind of quadtree that recursively subdivides a 2 dimensional space into 4 smaller and generally equal rectangular regions, until the wanted quadtree resolution has been reached, or no further subdivisions can be performed.
quadtree data-structure collections go-collectionAn implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with.At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case.
hashtree tree merkle-tree data-structure collections go-collectionThis library provides a Go implementation of the Adaptive Radix Tree (ART).The go-adaptive-radix-tree library overperforms go-art library. The go-adaptive-radix-tree doesn't allocate any memory during search operations. It also provides prefix based iteration over the tree.
data-structure collections go-collectionThis is a library implementing skip lists for the Go programming language (http://golang.org/).Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
data-structure collections go-collectionCount-Min Sketch is a widely adopted algorithm for approximate event counting in large scale processing. However, the original version of the Count-Min-Sketch (CMS) suffers of some deficiences, especially if one is interested in the low-frequency items, such as in text- mining related tasks. Several variants of CMS have been proposed to compensate for the high relative error for low-frequency events, but the proposed solutions tend to correct the errors instead of preventing them. In this paper, we propose the Count-Min-Log sketch, which uses logarithm-based, approximate counters instead of linear counters to improve the average relative error of CMS at constant memory footprint.This version implements the 16 bit register version. Will add back the 8-bit version soon.
data-structure collections go-collectionCuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space.Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%).
bloom-filter data-structure collections go-collectionThis is a set of integer compression algorithms implemented in Go. It is an (incomplete) port of the JavaFastPFOR by Dr. Daniel Lemire.
data-structure collections go-collectionA binary packer and unpacker.
unpacker packer data-structure collections go-collection
We have large collection of open source products. Follow the tags from
Tag Cloud >>
Open source products are scattered around the web. Please provide information
about the open source projects you own / you use.
Add Projects.