<p><strong>Update:</strong> An idea very similar to this one is described in <a href="http://www.lsi.upc.es/~roura/reports/LSI-99-26-R.ps.gz" rel="nofollow">"Digital Access to Comparison-Based Tree Data Structures and Algorithms"</a>.</p>

<hr>

<p>Here's an idea for a structure that might meet these bounds.
It uses an balanced binary search tree where each node is annotated with a pair of integers in $[-1,k-1]$ to indicate how much of the prefix of the key does not need to be compared again with the search key.</p>

<h2>Notation</h2>

<p>A <strong>shared prefix pair</strong> is a pair of integers associated with a key, called the <strong>focus</strong>, and a set of string keys not containing the focus, called the <strong>context</strong>.
For a focus $f$ and context $c$, if $\forall y \in c, f &lt; y$, then the left shared prefix (the left value in the shared prefix pair) of $f$ and $c$ is $-1$.
Otherwise, let $g$ be the largest key in $c$ such that $g &lt; f$.
This is called the <strong>left neighbor</strong> of $f$ in $c$.
Then the left shared prefix $i$ is the largest integer such that $f[i] &gt; g[i]$ and $\forall j &lt; i, f[j] = g[j]$.
The <strong>right shared prefix</strong> and <strong>right neighbor</strong> are defined symmetrically.</p>

<h2>Search</h2>

<p>Annotate each node in a balanced binary search tree with a shared prefix pair, using the key at that node as the focus and they keys of its ancestors in the tree as the context.
I'll first describe how to search for a string key (the needle, as in "needle in a haystack") in an annotated tree, then describe insertion and deletion.</p>

<p>During search, maintain a shared prefix pair with the needle as the focus and the keys of the nodes inspected during the search as the context.
By the definition above, we start with a shared prefix pair of $(-1,-1)$.</p>

<p>Assume we are searching for the needle $d$ with shared prefix pair $(i,j)$ in a tree with root $v$ with key $z$ and shared prefix pair $(p,q)$.
Since the search proceeds from parent to child, the prefix pairs share the same context and the same left and right neighbors, $a$ and $b$.</p>

<p>Now, if $i &lt; p$, then $z[i] = a[i] &lt; d[i]$, and $z &lt; d$.
In this case, the search proceeds recursively to the right child of $v$.
$z$ is the new left neighbor of $d$ and $d$'s prefix pair stays the same.</p>

<p>If $i &gt; p$, then $d[p] = a[p] &lt; z[p]$, and $d &lt; z$.
In this case, the search proceeds recursively to the left child of $v$.
$z$ is $d$'s new right neighbor and $p$ is the new right shared prefix of $d$.</p>

<p>For $j \neq q$, proceed similarly.</p>

<p>In the remaining case, $i = p$ and $j = q$.
Assume w.l.o.g., that $i \geq j$.
Find the first $i^{\prime} &gt; i$ such that $d[i^{\prime}] \neq z[i^{\prime}]$ but $\forall n &lt; i^{\prime}, d[n] = z[n]$.
If $d[i^{\prime}] &lt; z[i^{\prime}]$, then $d &lt; z$, so proceed to the left child of $v$.
The new right neighbor of $d$ is $z$ and the new right shared prefix of $d$ is $i^{\prime}$.
If $d[i^{\prime}] &gt; z[i^{\prime}]$, then $d &gt; z$, so proceed to the right; $z$ is the new left neighbor of $d$, and $i^{\prime}$ is $d$'s new left shared prefix.
The $j &gt; i$ case is symmetric.</p>

<h3>Search Performance</h3>

<p>Letters are not compared unless $i=p$ and $j=q$.
At each step in which letters are compared, either the sum of the shared prefix pair increases or only one letter comparison is made.
We will discuss these two separately.</p>

<p>If only one letter comparison is made, a child pointer is immediately followed.
Since paths from the root to leaves are $O(\lg n)$ and $n \leq A^k$, fewer than $O(k \lg A)$ single-letter-comparison steps are taken.</p>

<p>If $p &gt; 1$ letter comparisons are made in a step, the sum $i+j$ of the shared prefix pair increases by at least $p-1$.
Since the maximum possible sum is $2k$, $O(k)$ letter comparisons are made in comparisons that result in larger shared prefix pair sums.
However, shared prefix pair sums may seemingly decrease in non-letter-comparison steps when $i &gt; p$ and $j$ is replaced by $p$ or $j &gt; q$ and $i$ is replaced by $q$.
This is not the case, though:
If $i &gt; p$ then $d &lt; z$, so $j \leq q$.
If $j &lt; q$, then $d$'s new right shared prefix is $j$, so $j = p$ and the shared prefix pair sum is not decreased.
Similarly, if $j = q$, then $d$'s new right shared prefix is $\geq j$, and the sum is not decreased.</p>

<p>Similarly, each step requires $O(1+p/B)$ block transfers if it makes $p-1$ letter comparisons.</p>

<h2>Insertion and Deletion</h2>

<p>To perform an insertion, first locate where the node with the key $d$ would be found if it were in the tree.
After modification, perform the necessary $O(\log n)$ restructuring necessary to restore balance.
Rotations might invalidate shared prefix pairs.</p>

<p>Consider the case of a left rotation:</p>

<pre><code>  B
 / \
A   D
   / \
  C   E

    D
   / \
  B   E
 / \
A   C
</code></pre>

<p>The shared prefix pairs at A, C, and E all remain valid.
The left shared prefix of B and the right shared prefix of D also remain valid.
The right shared prefix at B is the left shared prefix at D from before the rotation.
The left shared prefix of D is the minimum of the left shared prefixes of D and B from before the rotation.</p>

<p>The right rotation and deletion cases are the same, mutatis mutandis. </p>

CC BY-SA 2.5
2011-02-26T19:18:29.687Z
2011-02-27T16:20:07.270Z
2011-02-27T16:20:07.270Z
jbapple
<p>Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory transfers and $O(k\log A)$ letter comparisons, where $B$ is the block size?</p>

<p>By predecessor problem I mean the problem of maintaining a set under insertion, deletion, and predecessor, where predecessor(k) finds the largest key in the set that is $\leq k$.</p>

<p><a href="http://www.cs.princeton.edu/~rs/strings/" rel="nofollow">Ternary search trees</a> achieve the letter comparison bound and are very simple, but can require $\Theta(k\log A)$ memory transfers.</p>

<p><a href="http://scholar.google.com/scholar?cluster=8403065314983295610" rel="nofollow">String B-trees</a> do better than the I/O bound I'm looking for, but they are not simple, and the <a href="http://www.cs.sunysb.edu/~bender/pub/PODS06-BFK.pdf" rel="nofollow">cache-oblivious ones</a> are even more complex and do not achieve the I/O bound in the worst-case. (String B-trees might achieve the comparison bound I'm looking for; I'm not sure.)</p>

<p>My intuition is that by fixing the size of the keys and relaxing the I/O bound, a simpler structure might be possible.</p>

<ds.data-structures><cache-oblivious>
Simple and cache-oblivious tries on fixed-length strings
jbapple
# Simple and cache-oblivious tries on fixed-length strings

(Asked by: username_0 on 2011-02-24)

Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory transfers and $O(k\log A)$ letter comparisons, where $B$ is the block size?

By predecessor problem I mean the problem of maintaining a set under insertion, deletion, and predecessor, where predecessor(k) finds the largest key in the set that is $\leq k$.

[Ternary search trees](http://www.cs.princeton.edu/~rs/strings/) achieve the letter comparison bound and are very simple, but can require $\Theta(k\log A)$ memory transfers.

[String B-trees](http://scholar.google.com/scholar?cluster=8403065314983295610) do better than the I/O bound I'm looking for, but they are not simple, and the [cache-oblivious ones](http://www.cs.sunysb.edu/~bender/pub/PODS06-BFK.pdf) are even more complex and do not achieve the I/O bound in the worst-case. (String B-trees might achieve the comparison bound I'm looking for; I'm not sure.)

My intuition is that by fixing the size of the keys and relaxing the I/O bound, a simpler structure might be possible.

**Tags:** ds.data-structures, cache-oblivious

---

## 1 answers

### Answer by username_0 on 2011-02-26. Score: 1 | Accepted answer

Update: An idea very similar to this one is described in "Digital Access to Comparison-Based Tree Data Structures and Algorithms".

Here's an idea for a structure that might meet these bounds.
It uses an balanced binary search tree where each node is annotated with a pair of integers in $[-1,k-1]$ to indicate how much of the prefix of the key does not need to be compared again with the search key.
Notation
A shared prefix pair is a pair of integers associated with a key, called the focus, and a set of string keys not containing the focus, called the context.
For a focus $f$ and context $c$, if $\forall y \in c, f < y$, then the left shared prefix (the left value in the shared prefix pair) of $f$ and $c$ is $-1$.
Otherwise, let $g$ be the largest key in $c$ such that $g < f$.
This is called the left neighbor of $f$ in $c$.
Then the left shared prefix $i$ is the largest integer such that $f[i] > g[i]$ and $\forall j < i, f[j] = g[j]$.
The right shared prefix and right neighbor are defined symmetrically.
Search
Annotate each node in a balanced binary search tree with a shared prefix pair, using the key at that node as the focus and they keys of its ancestors in the tree as the context.
I'll first describe how to search for a string key (the needle, as in "needle in a haystack") in an annotated tree, then describe insertion and deletion.
During search, maintain a shared prefix pair with the needle as the focus and the keys of the nodes inspected during the search as the context.
By the definition above, we start with a shared prefix pair of $(-1,-1)$.
Assume we are searching for the needle $d$ with shared prefix pair $(i,j)$ in a tree with root $v$ with key $z$ and shared prefix pair $(p,q)$.
Since the search proceeds from parent to child, the prefix pairs share the same context and the same left and right neighbors, $a$ and $b$.
Now, if $i < p$, then $z[i] = a[i] < d[i]$, and $z < d$.
In this case, the search proceeds recursively to the right child of $v$.
$z$ is the new left neighbor of $d$ and $d$'s prefix pair stays the same.
If $i > p$, then $d[p] = a[p] < z[p]$, and $d < z$.
In this case, the search proceeds recursively to the left child of $v$.
$z$ is $d$'s new right neighbor and $p$ is the new right shared prefix of $d$.
For $j \neq q$, proceed similarly.
In the remaining case, $i = p$ and $j = q$.
Assume w.l.o.g., that $i \geq j$.
Find the first $i^{\prime} > i$ such that $d[i^{\prime}] \neq z[i^{\prime}]$ but $\forall n < i^{\prime}, d[n] = z[n]$.
If $d[i^{\prime}] < z[i^{\prime}]$, then $d < z$, so proceed to the left child of $v$.
The new right neighbor of $d$ is $z$ and the new right shared prefix of $d$ is $i^{\prime}$.
If $d[i^{\prime}] > z[i^{\prime}]$, then $d > z$, so proceed to the right; $z$ is the new left neighbor of $d$, and $i^{\prime}$ is $d$'s new left shared prefix.
The $j > i$ case is symmetric.
Search Performance
Letters are not compared unless $i=p$ and $j=q$.
At each step in which letters are compared, either the sum of the shared prefix pair increases or only one letter comparison is made.
We will discuss these two separately.
If only one letter comparison is made, a child pointer is immediately followed.
Since paths from the root to leaves are $O(\lg n)$ and $n \leq A^k$, fewer than $O(k \lg A)$ single-letter-comparison steps are taken.
If $p > 1$ letter comparisons are made in a step, the sum $i+j$ of the shared prefix pair increases by at least $p-1$.
Since the maximum possible sum is $2k$, $O(k)$ letter comparisons are made in comparisons that result in larger shared prefix pair sums.
However, shared prefix pair sums may seemingly decrease in non-letter-comparison steps when $i > p$ and $j$ is replaced by $p$ or $j > q$ and $i$ is replaced by $q$.
This is not the case, though:
If $i > p$ then $d < z$, so $j \leq q$.
If $j < q$, then $d$'s new right shared prefix is $j$, so $j = p$ and the shared prefix pair sum is not decreased.
Similarly, if $j = q$, then $d$'s new right shared prefix is $\geq j$, and the sum is not decreased.
Similarly, each step requires $O(1+p/B)$ block transfers if it makes $p-1$ letter comparisons.
Insertion and Deletion
To perform an insertion, first locate where the node with the key $d$ would be found if it were in the tree.
After modification, perform the necessary $O(\log n)$ restructuring necessary to restore balance.
Rotations might invalidate shared prefix pairs.
Consider the case of a left rotation:
  B
 / \
A   D
   / \
  C   E

    D
   / \
  B   E
 / \
A   C

The shared prefix pairs at A, C, and E all remain valid.
The left shared prefix of B and the right shared prefix of D also remain valid.
The right shared prefix at B is the left shared prefix at D from before the rotation.
The left shared prefix of D is the minimum of the left shared prefixes of D and B from before the rotation.
The right rotation and deletion cases are the same, mutatis mutandis.


---

