<p>If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper:</p>

<p>Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353
  <a href="http://dx.doi.org/10.1007/3-540-55719-9_86" rel="nofollow">http://dx.doi.org/10.1007/3-540-55719-9_86</a></p>

<p>gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting nearest marked ancestor queries (i.e. the query time is <em>amortized</em> constant).</p>

CC BY-SA 3.0
2011-11-11T14:38:33.317Z
2011-11-11T14:38:33.317Z
hdbn
<p>Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).</p>

<p>I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.</p>

<p>This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.</p>

<p>Also in my case, a solution involving Informative Labeling [2] would be highly desirable.</p>

<ul>
<li>[1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998</li>
<li>[2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000</li>
</ul>

<hr>

<p>Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the <em>nearest</em> ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...</p>

<ul>
<li>[3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982</li>
</ul>

CC BY-SA 3.0
2011-04-21T04:45:21.787Z
What does it mean to "insert an internal node"?
Jeffε
CC BY-SA 3.0
2011-04-21T10:53:23.970Z
@JeffE -- many approaches make the compromise to allow tree modification only at the leaves. That is, the tree can grow only by adding leaves, or shrink by deleting leaves. Ideally I would be able to insert a vertex between two existing vertices. Of course, this can be simulated by removing the subtree first and and then re-adding all its vertices, but this comes with a huge performance penalty. However -- if I can manage to implement the dynamic version of Alstrup at all, it would already make my project advance quite a bit. So the middle paragraph is the most important one.
0__
CC BY-SA 3.0
2011-04-21T11:25:18.703Z
You may be asked to add any vertices to M later, and to handle this you have to remember the tree itself.  Therefore any data structure for your task requires Ω(|V|) space (more precisely Ω(|V| log |V|) bits).  (This may not apply to schemes based on informative labeling, which I do not know well.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-21T12:08:41.537Z
@Tsuyoshi -- That is correct. I should be more precise here: In fact I have multiple subsets of V, because there are different assignments possible, so there is a subset M, a subset N, etc. So I do keep track of the whole V, but I separately maintain M, N, etc.; each of the sets should require as little space as possible; at worst, it shouldn't grow exponentially, but maximally with a linear factor of the size of the tree or subset.
0__
CC BY-SA 3.0
2011-04-21T12:20:53.700Z
I see.  That makes more sense.  I do not know any answer but hope you get a good answer.
Tsuyoshi Ito
<ds.data-structures><tree><total-ordering><range-searching>
Dynamic Tree Marked Ancestor Queries
0__
# Dynamic Tree Marked Ancestor Queries

(Asked by: username_0 on 2011-04-20)

Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).

I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.

This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.

Also in my case, a solution involving Informative Labeling [2] would be highly desirable.

* [1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998
* [2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000

---

Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the *nearest* ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...

* [3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982

**Tags:** ds.data-structures, tree, total-ordering, range-searching

> **Comments:**
> **username_1**: What does it mean to "insert an internal node"?  
> **username_0**: @JeffE -- many approaches make the compromise to allow tree modification only at the leaves. That is, the tree can grow only by adding leaves, or shrink by deleting leaves. Ideally I would be able to insert a vertex between two existing vertices. Of course, this can be simulated by removing the subtree first and and then re-adding all its vertices, but this comes with a huge performance penalty. However -- if I can manage to implement the dynamic version of Alstrup at all, it would already make my project advance quite a bit. So the middle paragraph is the most important one.  
> **username_2**: You may be asked to add any vertices to M later, and to handle this you have to remember the tree itself.  Therefore any data structure for your task requires Ω(|V|) space (more precisely Ω(|V| log |V|) bits).  (This may not apply to schemes based on informative labeling, which I do not know well.)  
> **username_0**: @Tsuyoshi -- That is correct. I should be more precise here: In fact I have multiple subsets of V, because there are different assignments possible, so there is a subset M, a subset N, etc. So I do keep track of the whole V, but I separately maintain M, N, etc.; each of the sets should require as little space as possible; at worst, it shouldn't grow exponentially, but maximally with a linear factor of the size of the tree or subset.  
> **username_2**: I see.  That makes more sense.  I do not know any answer but hope you get a good answer.  

---

## 1 answers

### Answer by username_3 on 2011-11-11. Score: 4

If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper:

Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353
<http://dx.doi.org/10.1007/3-540-55719-9_86>

gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting nearest marked ancestor queries (i.e. the query time is *amortized* constant).


---

