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.

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?