Repository files navigation

A collection of multi-dimensional data structure and indexingalgorithm.

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 is a balanced-binary-tree based data structure efficientfor detecting all intervals (or segments) that contain a given point.
The segments may overlap with each other. The end points of storedsegments are not inclusive, that is, when an interval spans from 2 to6, an arbitrary point x within that interval can take a value of 2 <=x < 6.

Flat segment tree is a variant of segment tree that is designed tostore a collection of non-overlapping segments. This structure isefficient when you need to store values associated with 1 dimensionalsegments that never overlap with each other. Like segment tree,stored segments' end points are non-inclusive.

Point quad tree stores 2-dimensional points and provides an efficientway to query all points within specified rectangular region.

Multi-type vector allows storage of unspecified number of types in a singlelogical array such that contiguous elements of identical type are stored incontiguous segment in memory space.

Multi-type matrix is a matrix structure that allows storage of four differentelement types: numeric, string, boolean and empty. It uses multi-type vector asits underlying storage.

Sorted string map is a simple data structure that takes a pre-sorted list ofkey-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 thepre-sorted list provided by the caller.

Trie map is an associative container that stores multiple key-value pairswhere keys are stored in a trie structure to optimize for prefix searches.

Packed trie map is nearly identical to the trie map counterpart except thatthis one is immutable. It packs all its content in a contiguous array foroptimum storage and lookup efficiency. This implementation is based on thepaper titledTightly Packed Tries: How to Fit Large Models into Memory, and Make them Load Fast, Tooby Ulrich Germann, Eric Joanis, and Samuel Larkin.

R-tree is a tree-based data structuredesigned to store multi-dimensional geometric data with bounding boxes andprovide optimal performance on region- or point-based queries. The oneimplemented in this library is a variant of R-tree known asR*-tree.

Official API documentation for generalusers of the library.

Please see theReleases page forsource package downloads.

If you need old packages, please find themhere.

Please refer to theCONTRIBUTING.md file for build andinstallation instructions.

mdds is free software. You may copy, distribute, and modify it underthe terms of the License contained in the file COPYING distributedwith this package. This license is the same as the MIT/X Consortiumlicense.

These are the projects that are known to use mdds.

• LibreOffice
• Calligra
• libetonyek
• ixion
• orcus

If you use mdds and would like your project to be included in the above list,please let us know.