diff options
Diffstat (limited to '')
| -rw-r--r-- | README.md | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100644 index 0000000..3ae66f5 --- /dev/null +++ b/README.md @@ -0,0 +1,126 @@ +Multi-Dimensional Data Structure (mdds) +======================================= +A collection of multi-dimensional data structure and indexing +algorithm. + +Overview of data structures included in mdds +-------------------------------------------- + +This library implements the following data structures: + +* segment_tree +* flat_segment_tree +* point_quad_tree +* multi_type_vector +* multi_type_matrix +* sorted_string_map +* trie_map +* packed_trie_map +* rtree + +### Segment Tree + +Segment tree is a balanced-binary-tree based data structure efficient +for detecting all intervals (or segments) that contain a given point. +The segments may overlap with each other. The end points of stored +segments are not inclusive, that is, when an interval spans from 2 to +6, an arbitrary point x within that interval can take a value of 2 <= +x < 6. + +### Flat Segment Tree + +Flat segment tree is a variant of segment tree that is designed to +store a collection of non-overlapping segments. This structure is +efficient when you need to store values associated with 1 dimensional +segments that never overlap with each other. Like segment tree, +stored segments' end points are non-inclusive. + +### Point Quad Tree + +Point quad tree stores 2-dimensional points and provides an efficient +way to query all points within specified rectangular region. + +### Multi Type Vector + +Multi-type vector allows storage of unspecified number of types in a single +logical array such that contiguous elements of identical type are stored in +contiguous segment in memory space. + +### Multi Type Matrix + +Multi-type matrix is a matrix structure that allows storage of four different +element types: numeric, string, boolean and empty. It uses multi-type vector as +its underlying storage. + +### Sorted String Map + +Sorted string map is a simple data structure that takes a pre-sorted list of +key-value pairs that are known at compile time, and allows efficient lookup. +It does not allocate memory to duplicate its content, as it directly uses the +pre-sorted list provided by the caller. + +### Trie Map + +Trie map is an associative container that stores multiple key-value pairs +where keys are stored in a trie structure to optimize for prefix searches. + +### Packed Trie Map + +Packed trie map is nearly identical to the trie map counterpart except that +this one is immutable. It packs all its content in a contiguous array for +optimum storage and lookup efficiency. This implementation is based on the +paper titled [Tightly Packed Tries: How to Fit Large Models into Memory, and Make them Load Fast, Too](https://www.aclweb.org/anthology/W09-1505/) +by Ulrich Germann, Eric Joanis, and Samuel Larkin. + +### R-tree + +[R-tree](https://en.wikipedia.org/wiki/R-tree) is a tree-based data structure +designed to store multi-dimensional geometric data with bounding boxes and +provide optimal performance on region- or point-based queries. The one +implemented in this library is a variant of R-tree known as +[R*-tree](https://en.wikipedia.org/wiki/R*_tree). + + +Documentation +============= +[Official API documentation](https://mdds.readthedocs.io/en/latest/) for general +users of the library. + +Packages +======== + +Please see the [Releases](https://gitlab.com/mdds/mdds/-/releases) page for +source package downloads. + +If you need old packages, please find them [here](OLD-DOWNLOADS.md). + + +Installation +============ +Please refer to the [CONTRIBUTING.md](CONTRIBUTING.md) file for build and +installation instructions. + + +License +======= + +mdds is free software. You may copy, distribute, and modify it under +the terms of the License contained in the file COPYING distributed +with this package. This license is the same as the MIT/X Consortium +license. + + +Who uses mdds? +============== + +These are the projects that are known to use mdds. + +* [LibreOffice](http://www.libreoffice.org) +* [Calligra](https://www.calligra.org/) +* [libetonyek](https://wiki.documentfoundation.org/DLP/Libraries/libetonyek) +* [ixion](https://gitlab.com/ixion/ixion) +* [orcus](https://gitlab.com/orcus/orcus) + +If you use mdds and would like your project to be included in the above list, +please let us know. + |