@inproceedings{kaushik2002updates,
author = {Kaushik, Raghav and Bohannon, Philip and Naughton, Jeffrey F. and Shenoy, Pradeep},
title = {Updates for Structure Indexes},
booktitle = {VLDB},
year = {2002},
month = {January},
abstract = {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.},
publisher = {Very Large Data Bases Endowment Inc.},
url = {http://approjects.co.za/?big=en-us/research/publication/updates-for-structure-indexes/},
edition = {VLDB},
}