0

This presentation goes in depth into some indexing structures but doesn't go into XML indexes (or tree indexes). By tree indexes I don't mean B-trees and the like, which are used for indexing single-dimensional relational data, or even multi-dimensional index structures like R-trees. I mean indexing tree-structured data like XML or other trees.

In my search I have only encountered a few papers:

Some stuff seems to be under the category of "semistructured data", but I am looking for trees.

Specifically I would like to see indexes for:

  1. Exact paths in a tree.
  2. Exact subtrees in a tree.
  3. Inexact paths
  4. Inexact subtrees.
  5. N-number of branches of a tree.

Examples of these structures include:

1 -- 2 -- 3 -- 4

    1
  /   \
  2   6
  |   |
  3   7
/   \
4   5

1 -- * -- 3 -- (attr != "foo") -- 5

    1
  /   \
  2   *
  |   |
  *   8
/   \
4   (attr != "foo")
    |
    6

    1
  /   \
  2   6:(0..n of nodes)
  |   |
  3   7
/   \
4   5

I have found some stuff on querying for these structures, but not on specifically indexes for speeding up queries on these sorts of structures. I am basically looking for the equivalent of a B-tree or R-tree but for trees, like a T-tree or something.

One of the papers says:

Indexing techniques in relational or object-oriented databases depend on a fixed schema based on a known, strongly typed class hierarchy. Therefore, such techniques are not directly applicable in XML data.

Some papers refer to "traditional XML indexing methods", but I haven't seen those listed out or explained (and not sure if they match the 5 examples above).

Wondering if one could just list the names of such index structures, or perhaps links to a paper that describes them, for further checking.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.