1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How can you assume the priority queue has size $O(m)$? Do you assume $O(1)$ fanout? $\endgroup$ – Solomonoff's Secret Mar 14 '18 at 13:56
  • $\begingroup$ @Solomonoff'sSecret, yes. The fanout is at most $|\Sigma|$, the size of the alphabet, and I treat that as constant. If you want to know the dependence on $|\Sigma|$ or on the fanout as well, I suggest editing the question to state that. I suspect there may be a way to handle the high fanout case efficiently as well, e.g., by adding only the second-highest-weight child to the priority queue instead of adding all children to the queue (requires you to augment the data structure to store the children in sorted order, sorted by the weight of their highest-weight descendant, or something). $\endgroup$ – D.W. Mar 14 '18 at 15:35
  • $\begingroup$ Sorry, I did not even assume there was an alphabet, per se. But as tries are commonly used for character sequences it's a reasonable assumption. $\endgroup$ – Solomonoff's Secret Mar 14 '18 at 16:57
  • $\begingroup$ One more thing. It seems in general that you could pop a node with a particular item up to $\log n$ times. Wouldn't that introduce a factor of $\log n$ in the $m \log m$ term? $\endgroup$ – Solomonoff's Secret Mar 14 '18 at 17:01
  • $\begingroup$ @Solomonoff'sSecret, I suspect you're asking about how to remove duplicates. That can be done by never pushing duplicates onto the priority queue, which can be done for example with backpointers from a leaf into the queue (if it is present in the queue). $\endgroup$ – D.W. Mar 14 '18 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.