<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-25T21:59:00.527Z
Just to be clear, the hash table now points to queue entries.
Dave
CC BY-SA 3.0
2011-06-26T00:53:56.560Z
How does delete work in your solution?
jbapple
CC BY-SA 3.0
2011-06-26T02:45:54.853Z
It doesn't - I thought I must be missing something.
Dave
CC BY-SA 3.0
2011-06-27T17:42:53.770Z
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.
Dave
CC BY-SA 3.0
2011-06-28T05:49:43.287Z
Sounds promising. I'd like to hear more - How many samples do we need to take? What is the probability that our depth estimate is off by more than a constant factor? Can you explain in greater detail how we know that renumbering is amortized constant time?
jbapple
CC BY-SA 3.0
2011-06-28T08:47:27.050Z
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.
Dave
CC BY-SA 3.0
2011-06-25T21:57:17.347Z
2011-06-25T21:57:17.347Z
Dave
<p>I think Andersson and Petersson's <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.1496&amp;rep=rep1&amp;type=pdf" rel="nofollow">"Approximate Indexed Lists"</a> 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.</p>

CC BY-SA 3.0
2011-07-23T05:31:11.323Z
2011-07-23T05:31:11.323Z
jbapple
<p>I'm interested in a data structure (let's call it a <em>DMV queue</em>, or <em>DMV</em> for short) over keys (say, strings) with the following operations:</p>

<ul>
<li><strong>empty</strong> is a DMV containing no keys.</li>
<li><strong>enqueue(q,k)</strong> adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.</li>
<li><strong>dequeue(q)</strong> deletes the key at the front of the DMV q, if one exists, and returns it.</li>
<li><strong>delete(q,k)</strong> removes the key k from the DMV q.</li>
<li><strong>depth(q,k)</strong> returns an natural number indicating the <em>approximate</em> number of keys between the key k and the front of the DMV q. Let $k_q$ denote the <em>exact</em> 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$ &lt; depth(q,k) &lt; $ck_q$.</li>
</ul>

<p>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?</p>

<p>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.</p>

<p>Keep a hash table mapping keys to pointers to nodes in the tree.</p>

<p>To <strong>enqueue</strong> 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. <strong>Dequeue</strong> is similar.</p>

<p>To <strong>delete</strong> 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.</p>

<p>To find the <strong>depth</strong> 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 <em>exact</em> depth.</p>

<ds.data-structures>
Keyed queues with depth queries and delete
jbapple
# Keyed queues with depth queries and delete

(Asked by: username_0 on 2011-06-17)

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.

**Tags:** ds.data-structures

---

## 2 answers

### Answer by username_1 on 2011-06-25. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_1**: Just to be clear, the hash table now points to queue entries.  
> **username_0**: How does delete work in your solution?  
> **username_1**: It doesn't - I thought I must be missing something.  
> **username_1**: 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.  
> **username_0**: Sounds promising. I'd like to hear more - How many samples do we need to take? What is the probability that our depth estimate is off by more than a constant factor? Can you explain in greater detail how we know that renumbering is amortized constant time?  
> **username_1**: 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.  

---

### Answer by username_0 on 2011-07-23. Score: 1

I think Andersson and Petersson's ["Approximate Indexed Lists"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.1496&rep=rep1&type=pdf) 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.


---

