It is important to process the updates when nodes are
inserted into or deleted from the XML tree. All the
existing labeling schemes have high update cost, thus in
this paper we propose a novel Compact Dynamic Binary
String (CDBS) encoding to efficiently process the
updates. CDBS has two important properties which form
the foundations of this paper: (1) CDBS supports that
codes can be inserted between any two consecutive CDBS
codes with the orders kept and without re-encoding the
existing codes; (2) CDBS is orthogonal to specific
labeling schemes, thus it can be applied broadly to
different labeling schemes or other applications to
efficiently process the updates. We report our
experimental results to show that our CDBS is superior to
previous approaches to process updates in terms of the
number of nodes to re-label and the time for updating.
