2
$\begingroup$

I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations:

  • empty is a DMV containing no keys.
  • enqueue(q,k) adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.
  • dequeue(q) deletes the key at the front of the DMV q, if one exists, and returns it.
  • delete(q,k) removes the key k from the DMV q.
  • depth(q,k) returns an natural number indicating the approximate number of keys between the key k and the front of the DMV q. Let $k_q$ denote the exact number of keys between k and the front of q. Then there must be some c such that for all k and q, $k_q/c$ < depth(q,k) < $ck_q$.

I think I know how to provide the queue operations in $\Theta(1)$ time and delete and depth in $\Theta(\lg n)$ time (all expected amortized). Is it possible to do better?

My proposed solution is as follows: Maintain a balanced tree with $O(1)$ operations at the ends. Nearly any finger tree will do. This tree will store the keys in queue order at its nodes. Also, annotate every non-spine node with its number of descendants.

Keep a hash table mapping keys to pointers to nodes in the tree.

To enqueue a key k, add k to the back of the tree. This invalidates $O(1)$ node pointers and creates $O(1)$ new node pointers, so we need only perform $O(1)$ hash table operations. Dequeue is similar.

To delete a key, we look it up in the hash table and find its location in the tree, then delete it from the tree. This takes $O(\lg n)$ time in the tree, and invalidates $O(\lg n)$ slots in the hash table. We must also maintain non-spine node size annotations in the tree, but this also only takes logarithmic time.

To find the depth of a key, we first annotate the spine nodes of the tree with their number of descendants. This takes $O(\lg n)$ time. We then look up the key in the hash table and find its location in the tree. We then follow parent pointers until we reach the root, summing the annotations at left siblings. Note that this is the exact depth.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Your solution can be modified to do everything in $O(1)$ amortized time. Instead of maintaining a balanced tree, just keep track of the number of successful enqueue operations (those in which something was actually added to the back of the queue) and attach that number to queue along with the item during a successful enqueue operation. To find the depth of a key, just take the difference between the number of successful enqueues when it was enqueued, and the number of successful enqueues when the item currently at the front of the queue was enqueued. Note that this gives exact depth.

If you're worried about storing excessively large values after many enqueue and dequeue operations, you can also keep track of the size of the queue and whenever the size is less than half the number of enqueues, re-number the number of enqueues for each entry to 1 through the size, and reset the number of enqueues to the size. Everything takes constant amortized time and each key takes at most one more bit than necessary to represent its depth at insertion.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Just to be clear, the hash table now points to queue entries. $\endgroup$
    – Dave
    Jun 25, 2011 at 21:59
  • $\begingroup$ How does delete work in your solution? $\endgroup$
    – jbapple
    Jun 26, 2011 at 0:53
  • $\begingroup$ It doesn't - I thought I must be missing something. $\endgroup$
    – Dave
    Jun 26, 2011 at 2:45
  • $\begingroup$ Deletions can be handled probabilistically by keeping track of the set of items that have been deleted in another hash table. We need only store the depth at which they were deleted. Now, when estimating the depth, we can randomly sample enqueue numbers between the item we're finding the depth of and the front of the queue to get an estimate of the proportion of these that are actually in the queue. This estimate will be good if it's a large fraction of the values. If it's a small fraction, we can re-number just the front of the queue in constant amortized time and get the exact depth. $\endgroup$
    – Dave
    Jun 27, 2011 at 17:42
  • 1
    $\begingroup$ If you take n samples uniformly at random (with replacement) to estimate the proportion of items not deleted in a range, the variance is proportional to $1/n$. So you only need $O(1/\epsilon^2)$ samples to get any desired probability of getting within $\epsilon$ of the true proportion. This is only problematic if the true proportion is so small that $\epsilon$ is more than a factor of $c$. In this case, most of the items have been deleted. So if you get an estimate that's too low, the numbering is paid for by the previous deletions, giving constant amortized time. $\endgroup$
    – Dave
    Jun 28, 2011 at 8:47
1
$\begingroup$

I think Andersson and Petersson's "Approximate Indexed Lists" are what I was looking for. If I am reading it correctly, they provide the updates I was looking for in constant amortized time and the queries I was looking for in constant worst-case time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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