3
$\begingroup$

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only have one type. Let's also assume that our tree is somewhat balanced, and that there are far more nodes in the tree than there are unique types. Assuming I have already created some sort of index on the tree, I need to know the state of the art time complexity for the following types of queries (using whatever type of index / data structure you like):

Where A is some arbitrary node in the tree and T is some arbitrary type:

  1. find all descendants of node A that are of type T
  2. find the number of descendants of node A that are of type T

If the tree is static and no updates to the index are required, I have a data structure that will do 1 and 2 in $O(1)$. If the tree can have nodes added/removed, I also have a data structure that will do 1 and 2 in $O(\log m)$ where m is the total number of nodes of type T in the tree ($m << n$), and that can update the index when changes are made to the tree in $O(k\log m)$ where k is the number of nodes affected.

Are my data structures state of the art for these types of queries, or on par with state of the art? What existing work is out there that can match or beat this performance, if any?

(assume that any indexing structure we use must take less than $O(n^2)$ time and memory to construct)

(assume that any indexing structure we use for the case where the tree/index can be modified, that modifications can be handled in better than $O(n)$)

My understanding is that XML indexing generally has the state-of-the-art indexing schemes for dealing with trees where there are typed nodes, so I assume something with XML indexing will crop up here. I've tried looking through a number of papers myself but it's very difficult to get actual time complexities out of people in that field for some reason.

|cite|improve this question
$\endgroup$
  • $\begingroup$ When you mention "added/removed", are nodes added/removed only at the leaves? Or are you also concerned with removing internal nodes? (I presume it's not possible to add non-leaf nodes?) $\endgroup$ – D.W.♦ Oct 15 '15 at 17:58
  • $\begingroup$ I do also care about adding/removing internal nodes, but the vast majority of the time it would just be leaves. Most complicated modification I can think of would be removing a node by setting all of it's children to be direct children of the node's parent. My data structure is able to deal with this efficiently without needing to update other nodes (at least in an amortized sense). I'm basically looking for indexing schemes that can handle these types of updates in better than linear time in the number of nodes in the tree. $\endgroup$ – Sam Johnson Oct 15 '15 at 18:07
  • $\begingroup$ a. I'm a bit puzzled how you can find all descendants in $O(1)$ time (or $O(\log m)$ time for that matter), as the number of descendants might be $\Omega(1)$ (and $\Omega(\log m)$). b. It's not clear to me what is meant by "the number of nodes affected": does that mean the number of nodes that are inserted/deleted? $\endgroup$ – D.W.♦ Oct 16 '15 at 6:00
  • $\begingroup$ I consider it O(1) if you can return the first element in the list of descendants in O(1), and you can keep iterating over the remaining elements in O(1) per element. $\endgroup$ – Sam Johnson Oct 16 '15 at 22:04
  • $\begingroup$ Number of nodes affected would be if there is a subtree being removed... number of nodes in that case = number of nodes in the subtree. $\endgroup$ – Sam Johnson Oct 16 '15 at 22:12
1
$\begingroup$

For the static case, if you have a solution with $O(1)$ running time, I can't see any opportunity for improvement in the running time, as you can't do better than $O(1)$. So I'll focus on the dynamic case, i.e., where we want to support insertions and deletions.

One strategy is to augment the tree, so that for each type $T$ each node $x$ contains:

  • A count of the number of descendants of type $T$
  • A pointer to each immediate type-$T$ descendant of $x$ (i.e., a link to each $z$ such that $z$ has type $T$, $z$ is a descendant of $x$, and there is no descendant $y$ of $x$ such that $y$ has type $T$ and $z$ is a descendant of $y$)
  • A pointer to the immediate type-$T$ parent of $x$ (i.e., the lowest ancestor of $x$ that has type $T$)

This allows 'count' queries to run in essentially $O(1)$ time: given a node $x$, you can count the number of type-$T$ descendants of $x$ in $O(1)$ time. (Simply find $x$'s immediate type-$T$ parent, then use the field in the parent that stores the count of number of type-$T$ descendants.)

Also, 'enumerate' queries run in $O(k)$ time: given a node $x$, you can enumerate all type-$T$ descendants of $x$ in $O(k)$ time, where $k$ is the number of type-$T$ descendants of $x$. (Simply find $x$'s immediate type-$T$ parent, then traverse the fields that list the immediate type-$T$ descendants, recursively.)

The running time to insert a new leaf at depth $d$ in $O(d)$ time, since you only need to update the fields in the nodes along the path from that leaf to the root. If the tree is balanced, this is $O(\log n)$ time.

The running time to delete a leaf at depth $d$ is the same, for the same reasons.

This is the best I know how to do. I don't know if it is possible to do better.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is fantastic -- do you know of any paper that uses a setup similar to this? $\endgroup$ – Sam Johnson Oct 16 '15 at 22:03
  • $\begingroup$ Also, I assume this requires that the tree is balanced? Do you know of a different approach that would work for arbitrarily structured trees? The index my algorithm builds will work in that case as well, though I' can't get that $O(1)$ count time yours gets. $\endgroup$ – Sam Johnson Oct 16 '15 at 22:18
  • 1
    $\begingroup$ @SamKelly, right, inserts/deletes might be very slow if the tree is unbalanced. I don't know if there's something better you can do for unbalanced trees. I don't know if this is described in any paper; this is off the top of my head, using standard techniques for augmenting data structures. I don't know if it would be considered novel enough to be publishable. For instance, the trick of "augment the data structure by adding a field to each node that counts the number of descendants" is standard and found in algorithm/data structure textbooks. $\endgroup$ – D.W.♦ Oct 17 '15 at 0:27
  • $\begingroup$ Thanks for your help. The setup I'm using works in $(\log n)$ for completely unbalanced trees as it involves constructing and maintaining a separate data structure that is balanced. Getting this to work is a lot more complicated and involves working directly with depth-first indices in a way that still allows for insertions. For example, by representing depth-first indices as a float, you can do insertions between two depth-first indices, and then bubble offsets of these indices up the tree. $\endgroup$ – Sam Johnson Oct 17 '15 at 22:32

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.