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.