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:
- find all descendants of node A that are of type T
- 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.