I think the best way to approach this problem is to use two data structures: one to hold the searches with their individual counts and one to hold the current top 100 unique ones.

We can use a hash table to hold the search strings. We’d want to use a table of one billion slots and choose a hash function that assures a uniform distribution of our strings over the slots. In terms of memory consumption, we must store one billion strings and one integer (32-bit, since 10^9 = ~2^30) for each of those strings. Assume that the average length of the string is 100 characters or less. This is probably a good estimate; the actual average length is probably more like 10 or 15 than 100 since most of the time people search using only one or two words. Assume each character requires two bytes of memory. Therefore, we need:

(2 bytes/char * 100 char/str * 10^9 str) + (4 bytes/int * 10^9 int)
= 200 GB + 4GB = 204 GB memory

Lookup and insertion into the hash table run in constant time with respect to n, the number of search strings.

Another data structure we can use to store the strings and their counts is a radix tree or a Patricia trie. A radix tree is a tree in which the edges are labeled with characters and internal nodes are shared by strings that have their prefixes in common. The leaf nodes hold a special termination character and, in this case, our count. This data structure will take up less space than the hash table since the strings are not stored explicitly and instead share nodes. In the worst case, where every search string is unique, the radix tree becomes quite large and unwieldy, but of course we do not expect such a case to happen since the input is not at all random.

The data structure that we can use to store our top 100 unique searches is a priority queue. A priority queue is a queue in which the elements are ordered by some priority value that is provided at insert time. In this case, we’d use the search count for each string as its priority and the last element in the queue would be the string with the highest search count. We could also maintain this highest search count value separately to add processing.

So, for every incoming string, check if it’s in the hash table. If it is, check if its old count is less than or equal to the highest search count in the priority queue. If that is true, the string may be in the priority queue, so we remove it from the priority queue if it is there. Next, increment its count. If its new count is still less than than highest search count in the priority queue, add it to the queue. If the item is not in the hash table, add it to both the hash table and the priority queue with a count of 1. Remove the 1001th item from the priority queue and reset the highest search count value.

---------------------------

Obviously this approach requires a *ton* of memory. Does anyone have a better solution?