PruningRadixTrie – Faster Radix trie for prefix search and auto-complete

It's 1000x compared to a very naive baseline, exhaustive traversal of the matching subtree. Nobody in practice would do that, storing the maximum score for each subtree so you can prune is a very common technique, definitely not novel here.

Even doing a Levenshtein-bounded beam search along the trie is pretty much common practice, see for example this paper [1] from 2011.

There are more sophisticated ways of doing this in space-efficient ways, for example this paper [2] I co-authored in 2013.

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...

[2] https://www.microsoft.com/en-us/research/wp-content/uploads/...

Part of the optimization here seems to be that you only return the top 10 results. This might result in a really annoying UX though if you can't page through other results.

For example to tag someone on LinkedIn in a post you have to type their name (this comes up when I share someone's blog post on LinkedIn who I'm not connected with). But if their name doesn't come up within the top 10 results there seems to be literally no way to tag them.

And this isn't a permissions issue about tagging people I'm not connected with either. If the person I'm trying to tag who I'm not connected with has an uncommon name, I can normally find them in the auto complete list and tag them. If they have a common name, I often can't.

I'm not posting this to ask for solutions, just to say that being arbitrarily limited to top results can sometimes be infuriating.

The fine-grained results look like:

- 1444x faster for single character prefixes

- 252x faster for two character prefixes

- 55x faster for three character prefixes

- ~20x faster for 4 and 5 character prefixes

- <= 5x faster for longer prefixes

I used to work on a production auto-complete system operating at over 100k peak QPS. For prefixes of length one and two we would not even bother hitting the server, just from a quality perspective, not because of latency/throughput considerations. Btw, up until 3 characters, you could store everything in an in-memory hash map. 20x speedup on length 4 and 5 prefixes is still very impressive, but not quite 1000x speedup either.

Here is what I hate in modern completion UIs.

You type one character, and the thing scampers off like a rabid squirrel, hogging the CPU, so that the UI becomes unresponsive to me typing the remaining characters.

If you just prioritize the interactive response, the algorithm is almost moot.

When the user types m, you could as well show a completely random selection of 20 things that start with m. Or nothing. Take your time; the user will type more stuff.

When there are enough characters of context so that the selection is pruned down, there you need to be responsive. The user starts to see meaningful things in the list. When they type another character to refine it, they want it updated instantly.

Completion that is too eager is exactly like a person who doesn't wait for you to finish talking, jumps to conclusions about what you're going to say and starts replying.

Here is another thing I hate: when I see a completion I like that is itself not complete, let me continue! Sometimes the completion gives me the word I was going to type, but there is more; i.e. I wanted just to complete a part of my typing, not to choose that item as the result of the query.

I find myself manually typing the word I see in the completion list, because I know that if I click on it, it will search for that, which is not what I want.

The completion should always go into the query box, where the user can refine it before submitting it. Or at least make it an option.

It doesn't actually cost an extra click. All it means that if I use down arrow to go into the completions, the currently selected completion is copied to the query box. Then I can type more characters, or hit Enter to dispatch the query. If all I want is to dispatch the completion, it's the same number of keystrokes: down arrow to pick a completion, then Enter.

Do not have it so that when I hit down arrow, the text I typed stays the same, so that the only choice I have is to hit Enter to dispatch "microsoft" or else continue my original text from "micr". Maybe I want the word "microsoft" and then continue typing " teams" or whatever.

I wrote something like this for contact auto completion - running in the browser we had to ensure that both tree construction was fast, and also that completion was instantaneous. So the next level of optimization is to amortize tree construction over searches (using the observation that most of the tree is never accessed)

https://github.com/superhuman/trie-ing

In the game "keep talking and nobody explodes" one of the puzzles has you match a limited set of characters in each position to a dictionary of possible words. A task I was having a lot of trouble doing in the limited time provided. I ended up rewriting the dictionary as a prefix tree and including it as a addendum to the manual.

It was neat seeing seeing these algorithms work at human scale and how much better it made the process.

This is interesting, I am curious if it's possible to add more than 10 results and how it would look.

Also if it makes sense to use something like this for code autocomplete - I would prefer I could just scroll to find everything.

I think though in case of code parsing through the code and add things to the dictionary may be more expensive than looking through it.

Inspiring, but we use Postgres full text search for all autocomplete functionality and it has worked just fine.

What is the state of art in longest prefix matching e.g for router prefixes in routing tables?

Nice piece of engineering and surely worth a read. The ideas are hardly novel, tho.

Or put a cache in front.