News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.