{"repo":"dice-group/hypertrie","free":true,"listed":false,"github":"https://github.com/dice-group/hypertrie","clone":"git clone https://github.com/dice-group/hypertrie.git","description":"A monolithic index that supports worst-case optimal joins (WCOJ) by providing all collation orders in a single redundancy eliminating datastructure.","language":"C++","stars":18,"topics":["tensor","column-oriented","database","hypertrie","index","rdf","sparql","worst-case-optimal-join-algorithms","wcoj"],"license":"Apache-2.0","category":"databases-storage","readme_excerpt":"Hypertrie Where is it used? - the backend of the commercial and research-prototype Tentris triple stores/RDF graph databases - a sparse tensor representation that supports slicing by any dimension and einstein summation - a monolithic index that supports worst-case optimal joins (WCOJ) by providing all collation orders in a single redundancy eliminating datastructure. What is it? Technically, a hypertrie stores $d$-tuples where $d$ is also called dimension (tensor) or depth (trie, index). It allows incremental slicing (tensor) by any dimension or select and project by any predicate (relational algebra). These properties are important to support worst-case optimal joins (WCOJ) efficiently. Asymptotic Guarantees A depth $d$ the hypertrie encoding a set of $z$ tuples requires at most $\\mathcal O (z\\cdot 2^{d-1}\\cdot d)$ space. The runtime complexity of applying (inserting or deleting) a changeset set $\\Delta$ of $d$-tuples to a depth $d$ hypertrie is bound by the space complexity $\\mathcal O ( \\Delta \\cdot 2^{d-1}\\cdot d)$ of a surrogate hypertrie that encodes the change set changeset $\\Delta$. build This is a template library. So there is nothing to build beyond tests. prerequisites Software was tested on Ubuntu-22.04 with gcc-13 and clang-17, both using libstdc++-13 as C++ STL. Install with: Ensure cmake 3.24 is installed. Build the Tests Some dependencies are not on Conan Center but only on our own Package repository. Add it with: Download conan provider.cmake to the project ","default_branch":null,"files":null,"tree":[],"storefront":"/r/dice-group","claimed":false,"request_supported":{"post":"https://gitbuyer.com/r/dice-group/hypertrie/request-supported","requests":0},"note":"indexed from public GitHub; nothing is for sale on this page. Clone it from GitHub. Paid listings live at /search."}