(more points): 2. You could send the common part to the client itself, including the most frequent queries. Let's assume a 10 letter query (kind of long) as average and assume we're showing the top 5 queries. To cache the first level (first letter) we'll need about 26 (letters) * 5 (number of results) * 10 (length of query) bytes (disregarding the trie structure itself - it can be optimized by using a fixed width structure) = 1300 bytes. not too much. The 2nd level would be 1st level * 26 = 33800 bytes. 33Kib to download is ok, but starting to approach noticeable. Of course, since you control the browser you could pre-fetch it and even fetch deltas instead of re-fetching the full structure if needed. The next level is 878800 - almost a MiB. Kinda large - but may be worth it to save 3 levels of type-ahead on the client side. That will actually save you a lot of roundtrips as user behavior with a good type-ahead is to accept the results offered. Note that the 878KiB is the worst-case. Since distribution is not even, we'll likely end up with less. You could further optimize by sending an unbalanced tree that favor deeper levels on more frequent type-ahead prefixes.
I'd say, few hundreds of kilobytes for a typeahead is way too much data to transfer, especially when we also intend to cater to mobile devices (with expensive data plans).
The data is text with very low entropy, easy to compress ( gzip ) so, I will not worry about the size of the response.