Displaying 1 to 18 from 18 results

gods - GoDS (Go Data Structures)

  •    Go

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.

go-datastructures

  •    Go

Go-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.

BoomFilters - Probabilistic data structures for processing continuous, unbounded streams.

  •    Go

Boom 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.

hyperloglog - HyperLogLog with lots of sugar (Sparse, LogLog-Beta bias correction and TailCut space reduction)

  •    Go

An 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".




golang-set - A simple set type for the Go language. Also used in Docker.

  •    Go

The 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.

bloom - Go package implementing Bloom filters

  •    Go

A 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.

gota - Gota: DataFrames and data wrangling in Go (Golang)

  •    Go

This 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.

bitset - Go package implementing bitsets

  •    Go

Package 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.


levenshtein - This is the Go implementation to calculate Levenshtein Distance.

  •    Go

The 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".

go-rquad - State of the art point location and neighbour finding algorithms for region quadtrees, in Go

  •    Go

Go-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.

merkletree - A Merkle Tree implementation written in Go.

  •    Go

An 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.

go-adaptive-radix-tree - Adaptive Radix Trees implemented in Go

  •    Go

This 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.

goskiplist - A skip list implementation in Go

  •    Go

This 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.

count-min-log - Go implementation of Count-Min-Log

  •    Go

Count-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.

cuckoofilter - Cuckoo Filter: Practically Better Than Bloom

  •    Go

Cuckoo 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%).

encoding - Integer Compression Libraries for Go

  •    Go

This is a set of integer compression algorithms implemented in Go. It is an (incomplete) port of the JavaFastPFOR by Dr. Daniel Lemire.