Yeah we actually are much closer to the "old" ART than using the disciminating bit aproach of HOT.
Hot is a more complex data structure with a less deterministic structure which makes it less suited for set operations defined over it and makes it difficult to store the hashes of subtrees in the nodes, also it is not really suited for covering indices from what I can see.
The original ART is not a covering either because of their optimistic infix compression, but it's really easy to make it covering.
We also have the goal of being really "simple" in terms of moving parts, and "easy" in terms of implementation.
Our adaptiveness is not based on different node types but based on a single node type that comes in different sizes and uses perfect-consistent-locality-sensitive-cuckoo-hashing (yeah it's a mouthfull ^^'). We call the thing Persistent Adaptive Cuckoo Trie, or PACT (as in pact with the devil) for short.
The idea is that because of the 256-fanout, we can fine tune our hash functions, to be perfect and collision free, to preserve locality so that two adjacent byte keys will go into the same bucket, and to be consistent on resize, so that doubling the node size only requires a memcpy of the lower half of the new bucket array into the upper half (memory which needs to be initialised anyways, so we get the grow for free modulo reallocation overhead).
This not only saves us costly rehasing but also makes the implementation much simpler.
We figured if we want to build a competitor to RDF it better be implementable by anybody during a hackathon.
The binary triples (Tribles, get it?) that we store are 16byte unique entity id, 16byte unique attribute id, and 32byte value.
We don't do surrogate keys, to not only simplify the implementation and reduce latency, but to also be able to do range and limit queries from the primary indexes directly.
Because we store triples materializing all pssible indexes over our tables (3! + 3) is actually feasible.
This allows us to create a worst case optimal join algorithm that is completely skew resistant.
We're currently working on adding minhash heuristics into the PACT to always pic the optimal variable order for constraint propagation which should make things instance optimal (a first to our knowledge).
So yeah basically the idea is to have a immutable in-memory knowledge base that is amortized O(1) for everything. I.e. you pay per inserted element but not by how much was already inserted, you pay proportional to the size of the intersection of the operands for set ops and not propertional to sum of the operands, you pay proportional to your result size for a query and not propertional to the size of the data queried.
We also have a (still very stealthy) discord channel if you'd like to chat some more about this stuff at discord.gg/tribles :D
Hot is a more complex data structure with a less deterministic structure which makes it less suited for set operations defined over it and makes it difficult to store the hashes of subtrees in the nodes, also it is not really suited for covering indices from what I can see.
The original ART is not a covering either because of their optimistic infix compression, but it's really easy to make it covering.
We also have the goal of being really "simple" in terms of moving parts, and "easy" in terms of implementation.
Our adaptiveness is not based on different node types but based on a single node type that comes in different sizes and uses perfect-consistent-locality-sensitive-cuckoo-hashing (yeah it's a mouthfull ^^'). We call the thing Persistent Adaptive Cuckoo Trie, or PACT (as in pact with the devil) for short.
The idea is that because of the 256-fanout, we can fine tune our hash functions, to be perfect and collision free, to preserve locality so that two adjacent byte keys will go into the same bucket, and to be consistent on resize, so that doubling the node size only requires a memcpy of the lower half of the new bucket array into the upper half (memory which needs to be initialised anyways, so we get the grow for free modulo reallocation overhead).
This not only saves us costly rehasing but also makes the implementation much simpler.
We figured if we want to build a competitor to RDF it better be implementable by anybody during a hackathon.
The binary triples (Tribles, get it?) that we store are 16byte unique entity id, 16byte unique attribute id, and 32byte value.
We don't do surrogate keys, to not only simplify the implementation and reduce latency, but to also be able to do range and limit queries from the primary indexes directly.
Because we store triples materializing all pssible indexes over our tables (3! + 3) is actually feasible. This allows us to create a worst case optimal join algorithm that is completely skew resistant.
We're currently working on adding minhash heuristics into the PACT to always pic the optimal variable order for constraint propagation which should make things instance optimal (a first to our knowledge).
So yeah basically the idea is to have a immutable in-memory knowledge base that is amortized O(1) for everything. I.e. you pay per inserted element but not by how much was already inserted, you pay proportional to the size of the intersection of the operands for set ops and not propertional to sum of the operands, you pay proportional to your result size for a query and not propertional to the size of the data queried.
We also have a (still very stealthy) discord channel if you'd like to chat some more about this stuff at discord.gg/tribles :D