Updates for Structure Indexes

The problem of indexing path queries
in semistructured/XML databases has re-
ceived considerable attention recently, and
several proposals have advocated the use of
structure indexes as supporting data struc-
tures for this problem. In this paper, we
investigate ecient update algorithms for
structure indexes. We study two kinds of
updates | the addition of a subgraph, in-
tended to represent the addition of a new
le to the database, and the addition of
an edge, to represent a small incremental
change. We focus on three instances of
structure indexes that are based on the no-
tion of graph bisimilarity. We propose al-
gorithms to update the bisimulation parti-
tion for both kinds of updates and show how
they extend to these indexes. Our experi-
ments on two real world data sets show that
our update algorithms are an order of mag-
nitude faster than dropping and rebuilding
the index. To the best of our knowledge,
no previous work has addressed updates for
structure indexes based on graph bisimilar-
ity.