3 ms·

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 ot

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.

gpderetta 3y ago
It seems to me that an hybrid solution using a pruning trie for prefixes and a normal trie for almost complete completions would work.
- gchamonlive 3y ago
  You mean you do both in parallel, asynchronously, return the first top 10 results, and by the time the user gets to the point it needs the rest of the results, the classical trie is done, or at least it is close to ready?
ok123456 3y ago
He keeps the sorted frequency count. It doesn't have to be the top 10. You can query arbitrary k.
gwern 3y ago
OP includes the entire trie if you set the minimum rank to -INF, so that's not an issue with the data structure but the UX, I would think? The data structure can show all the results, it's just a matter of knowing when the user wants to see more. You'd need something like a button for 'show more results', or perhaps use a timeout ('if no user action in 10s, assume the desired result is missing & show more results) where it increases the _n_ limit (say, doubling each time). Then the user only pays for what they use, and the common case remains accelerated.
- swader999 3y ago
  You could use scroll event(s) to trigger more results.
mgaunard 3y ago
Not "part", this is the whole basis of the data structure.

gpderetta 3y ago

It seems to me that an hybrid solution using a pruning trie for prefixes and a normal trie for almost complete completions would work.

gchamonlive 3y ago
You mean you do both in parallel, asynchronously, return the first top 10 results, and by the time the user gets to the point it needs the rest of the results, the classical trie is done, or at least it is close to ready?

ok123456 3y ago

He keeps the sorted frequency count. It doesn't have to be the top 10. You can query arbitrary k.

gwern 3y ago

OP includes the entire trie if you set the minimum rank to -INF, so that's not an issue with the data structure but the UX, I would think? The data structure can show all the results, it's just a matter of knowing when the user wants to see more. You'd need something like a button for 'show more results', or perhaps use a timeout ('if no user action in 10s, assume the desired result is missing & show more results) where it increases the _n_ limit (say, doubling each time). Then the user only pays for what they use, and the common case remains accelerated.

swader999 3y ago
You could use scroll event(s) to trigger more results.

mgaunard 3y ago

Not "part", this is the whole basis of the data structure.