data structure admitting top items with prefix

Question

A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and deletion and takes $O(n)$ space.

Now suppose each item has a score. I am looking for a data structure that can answer a related query: give me the top $m$ items by score with a certain prefix. Ideally search, insertion, and deletion would have the same time as a trie, up to a constant factor, and space would be $O(n)$ as well. To this end we may assume items are short (of length $O(\log n)$).

This problem can be solved with $O(\log^2 n)$ insertion and deletion and $O(n \log n)$ space by forming a trie where every node contains a sorted set of items with that prefix sorted by score. But this approach uses excess time and space compared to a trie. Can we do better?

Answer 1

You can achieve $O(\log n)$ time insert, $O(\log n)$ time delete, $O(n)$ space, and $O(m \log m + \log n)$ time search by augmenting the trie.

Store in each leaf the weight of the corresponding item. Also, at each internal node, add a field with a pointer to the leaf of maximum weight that's reachable from that node.

It's easy to see how to perform insertion in $O(\log n)$ time, and it's easy to see why this still uses only $O(n)$ space.

Search for the top $m$ items with a certain prefix can be done in $O(m \log m + \log n)$ time. First, find the node $x$ corresponding to that prefix. Use that node to identify the first item of the output (the highest-weight item with that prefix). Next, look at the children $y_1,\dots,y_k$ of node $x$, and for each, look at the highest-weight item with that prefix. Add these $k$ nodes to a priority queue, keyed on the weight of the corresponding item. Extract the highest-weight item from the queue; that's the second item of the output. Look at the children of the node you just extracted, and add them to the queue. Repeat until you have output $m$ items; in each iteration, you extract the node of highest weight from the priority queue, output the corresponding item, and add the children of that node to the priority queue. Remove duplicates as you go. Stop once you've output $m$ items. You do $O(\log n)$ time to find the first node corresponding to the prefix, and then each subsequent iteration takes $O(\log m)$ time (since operations on a priority queue of size $O(m)$ can be done in $O(\log m)$ time), and you do $m$ iterations, for a total running time of $O(\log n + m \log m)$.

Deletion can be done in $O(\log n)$ time. To delete an item, traverse the trie to find that item. Then, update each node that you visited during that traversal. To update a node $x$, if the maximum-weight leaf under $x$ is the the item you're deleting, check the children of $x$ to find the next-highest-weight leaf under $x$, and update $x$. This does $O(1)$ work per node you traverse, and the traversal visits $O(\log n)$ nodes, so the total time for deletion is $O(\log n)$ time.