Re:Beating hash tables with trees? The ART-ful radix trie
by whatshisface on Saturday November 10, 2018 @02:45PM
(#18423105)
>How would we go about quantifying the preferring locality-ness of a query distribution?
For each level of the tree, treat the incoming stream of queries as a markov process where each state is a query that involves a certain node. So, if I have 7 nodes on level 2, I can build up a table of transition probabilities between vertices like "query involved node 3 on level 2" and "query involved node 7 on level 2." When the transitions between these vertices and themselves have high probability, the queries prefer locality. You can see which scale the locality is preferred on by doing this at each level of the tree.
Re:Beating hash tables with trees? The ART-ful radix trie
by leiroigh on Saturday November 10, 2018 @01:43PM
(#18422762)
>Isn't this a fairly common pattern?
Depends on the application. It is certainly not uncommon that queries fired at close times share a prefix.
>How would we go about quantifying the preferring locality-ness of a query distribution?
I know it when I see it?
Isn't this a fairly common pattern? How would we go about quantifying the preferring locality-ness of a query distribution?