Why can't we use hash table of prefixes to achieve the same thing (instead of using trie)? We can have a word hash table storing (word, count) and a prefix hash table storing (prefix, top 10 reference to (word, count)). Each time we need to do an update, we first do a word table update. Let's say we have (CAPTAIN, 10) becoming (CAPTAIN, 11) Then we just enumerate all the prefixes of this word (for example, for CAPTAIN, we enumerate C, CA, CAP, CAPT ..) and then check if (CAPTAIN, 11) made to top 10. If yes, replace that row of the prefix table When we query, we just fetch one single row from prefix table. We can do batch offline update & partitioning similarly (probly even easier this way) and the rows that we need for prefix table is about the same as the node of tries.