論文 / 著書情報
Article / Book Information
Title

A Low-Storage-ConsumptionXML Labeling Method forEfficient
Structural Information Extraction

Author

Wenxin Liang, Akihiro Takahashi, Haruo Yokota

Journal/Book name

Database and Expert Systems Applications of LNCS (Proc. of
DEXA2009), , ,

発行日 / Issue date2009, 9

DOI

http://dx.doi.org/10.1007/978-3-642-03573-9̲2

権利情報 / Copyright

The original publication is available at www.springerlink.com.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

A Low-Storage-Consumption
XML Labeling Method forEﬃcient Structural Information Extraction
Wenxin Liang1 , Akihiro Takahashi2 , and Haruo Yokota2,3
1School of Software, Dalian University of Technology
Department of Computer Science, Tokyo Institute of Technology
3
Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology
liang@computer.org, akihiro@de.cs.titech.ac.jp, yokota@cs.titech.ac.jp
2

Abstract. Recently, labeling methods to extract and reconstruct thestructural information of XML data, which are important for many applications such as XPath query and keyword search, are becoming more
attractive. To achieve eﬃcient structural information extraction, in thispaper we propose C-DO-VLEI code, a novel update-friendly bit-vector
encoding scheme, based on register-length bit operations combining withthe properties of Dewey Order numbers, which are not able to be implemented in other relevant existing schemes such as ORDPATH. Meanwhile, the proposed method also achieves lower storage consumption because it does not require either preﬁx schema or any reserved codes fornode insertion. We performed experiments to evaluate and compare theperformance and storage consumption of the proposed method with thoseof the ORDPATH method. Experimental results show that the execution times for extracting depth information and parent node labels using
the C-DO-VLEI code are about 25% and 15% less, respectively, andthe average label size using the C-DO-VLEI code is about 24% smaller,
comparing with ORDPATH.

1

Introduction

The Extensible Markup Language (XML) has rapidly become the de facto standard for representing and exchanging data on the Internet, because it is portable
for representing diﬀerent types of data from multiple sources. An XML document can be modeled as a nested tree structure in which each element is treatedas a node with a start tag and end tag. An example XML document and its
corresponding XML tree are shown in Figure 1 and Figure 2, respectively.
To handle the hierarchical tree model of XML data, XML labeling methods are required to extract and reconstruct the structural information of the
XML document, which are commonly used for many applications such as XPathThis work was done when the author was with Japan Science and Technology Agency(JST) and Tokyo Institute of Technology.

The author is currently with NTT Data Corporation.

<BOOK ISBN = “1-55860-438-3”><SECTION><TITLE>Bad Bugs</TITLE>
Nobody loves bad bugs
<FIGURE CAPTION=“Sample bug” /></SECTION><SECTION><TITLE>Tree Frogs</TITLE>
All right-thinking people<BOLD>love</BOLD>free frogs.
</SECTION></BOOK>

Fig. 1. Example XML document

Depth 0BOOK

Element nodeISBN

Text node

Depth 1

Depth 2Depth 3

SECTION

TITEL Nobody… FIGURE

Attribute node

SECTION

TITEL

All…

BOLD free…

CAPTIONlove

Fig. 2. Example XML tree

query [19] and keyword search [16]. XML labeling methods assign a label to eachnode of the XML tree, and each labeled node is stored as a tuple containing the
tag information for element nodes or the Parsible Character Data values of text
nodes together with the label. Structural information, such as containment relationship, order of sibling and depth of nodes in the XML tree, is possible tobe obtained from the regularity of the labels.
A number of XML labeling methods based on numbering schemes such as
the preorder–postorder [10] and Dewey Order (DO) [19] have been proposed.
The preorder–postorder method assigns preorder and postorder numbers to allnodes to maintain the containment and order information between nodes. The
DO method uses a delimiter to separate the label of a parent node from thecode that expresses the sibling order among its children. The parent–child andancestor–descendant relationships, and the relative sibling order, can be deducedby comparing the labels at corresponding positions determined by the delimiters.
The DO method is eﬀective for obtaining the labels of parent and ancestor
nodes and for determining common ancestors of multiple nodes by using thedelimiters. These properties of the DO method are useful for achieving eﬃcient
XPath query [19] and keyword search [16]. For example, the parent, ancestor
and depth information can be directly determined by analyzing the delimiters,
which is valuable to enable eﬃcient XPath axis determination in XPath queryand eﬃcient LCA or SLCA extraction in keyword search. However, using simple
numerical values for the sibling order in the preorder–postorder and DO methods
has the problem of expensive update costs. If a new node is inserted in anintermediate position of the XML tree, many node labels have to be renumbered
to maintain the proper sibling order.
To address the update problem, several update-friendly XML labeling methods such as DO Variable-Length-Endless-Insertable (DO-VLEI) code [13] and
ORDPATH [17] have been proposed. The DO-VLEI labeling method inherits features of the DO method, but reduces the update cost for insertion operations. It
uses the VLEI code [13] for expressing the sibling order by a unique magnitude relationship, which enables the unlimited insertion of new nodes with no relabelingrof other nodes being required. ORDPATH, which is implemented in Microsoft
SQL ServerT M 2005, is also an update-friendly labeling method based on the DO
number. [18] reported that ORDPATH achieves both better structural information extraction and storage consumption than the existing preﬁx-based labelingmethods such as LSDX [8] and persistent labeling schemes [9, 12]. DO-VLEI

achieves eﬃcient structural information extraction as ORDPATH does. However, the size of DO-VLEI codes becomes larger when numbering large-scale
XML documents.
Other two update-friendly labeling schemes, namely QED [14] and CDBS [15],are more eﬃcient than ORDPATH in respect to data updates. However, QED
works worse in some cases and CDBS results in both worse structural information extraction and storage consumption than ORDPATH. Therefore, it isessential to have both eﬃcient structural information extraction and low storage
consumption and for large-scale XML data in update-friendly methods. The ORDPATH method uses a Compressed binary representation (C-ORDPATH) anda preﬁx schema to reduce the size of node labels and to achieve eﬀective structural information extraction. However, as criticized in MonetDB/XQuery [5, 6],
C-ORDPATH has problems of expensive manipulation and storage costs. On the
structural information extraction point of view, the features of C-ORDPATH
cause the problem of high manipulation cost because decode of C-ORDPATH
requires to traverse from the head through the whole code and refer to the preﬁx
schema. With respect to the storage consumption, the label in the C-ORDPATH
cannot be optimized during the initial labeling, because negative integers andeven numbers are reserved for node insertions. In addition, the labels available
for assignment to the XML nodes are limited by the preﬁx schema. Therefore,
the preﬁx schema used for C-ORDPATH must be changed when handling large
XML documents, which causes further expensive manipulation and storage costs.
To achieve both eﬃcient structural information extraction and low storageconsumption for large XML documents with high update frequency, in this paper
we propose the Compressed-bit-string DO-VLEI (C-DO-VLEI) code, an updatefriendly XML labeling method. To achieve eﬃcient structural information extraction, we propose a novel and eﬃcient method based on register-length bit
operations combining with the properties of DO numbers, which are not able
to be implemented in other bit-vector encoding schemes including ORDPATH.
Meanwhile, C-DO-VLEI also achieves lower storage consumption by using acompressed binary representation using DO numbering schemes without any
preﬁx schema. We performed experiments to evaluate and compare the storage consumption and performance of the proposed method with those of the
C-ORDPATH method. Experimental results show that the proposed method
outperforms the ORDPATH method with respect to both structural information extraction and storage consumption, particularly for documents of large
size and depth.
The main contributions of this paper can be listed as follows.
1. We propose a novel update-friendly bit-vector encoding scheme, C-DO-VLEI
code, for eﬃciently extracting the structural information between nodes fromthe C-DO-VLEI code. The proposed method enables eﬃcient structural information extraction based on register-length bit operations combining withthe properties of DO numbers instead of bit-by-bit comparisons utilized in
the C-ORDPATH method.

2. The C-DO-VLEI code is also able to shorten the label length and thereby
reduce the storage consumption required for the labeling of large-scale XML
documents, because it does not require either preﬁx schema or any reserved
codes for node insertion.
3. We performed experiments to compare the performance and storage consumption of the proposed method with those of C-ORDPATH which is
veriﬁed in [18] that it outperforms other existing methods in both storage consumption and performance. Experimental results indicate that: 1)
the execution times for extracting depth information and parent node labels
using the C-DO-VLEI code are about 25% and 15% less, respectively, thanfor C-ORDPATH, which enables the proposed method to achieve high performance in such applications as XPath query and keyword search; 2) thelabel size using the C-DO-VLEI code is about 24% smaller than that using
C-ORDPATH, which means taht the proposed method also outperforms the
ORDPATH method with respect to storage consumption.
The remainder of the paper is organized as follows. In Section 2, we brieﬂy
introduce related work. Section 3 proposes the C-DO-VLEI code. Section 4 describes the method for extracting structural information from the C-DO-VLEI
code. Section 5 describes the experiments and the evaluation of the proposed
methods. Finally, Section 6 concludes the paper.

2

Related WorkOne traditional labeling method is the preorder–postorder method [10], whichassigns preorder and postorder numbers to all nodes. Another traditional method
is the DO method [19], which uses a delimiter “.” to separate a parent label fromits child’s label. However, when simple consecutive integers are used for nodelabeling in these methods, many nodes must be relabeled to satisfy sibling order
following the insertion of a new node into an intermediate position.
To tackle this problem, several methods have been proposed. The QuarteringRegions Scheme [4] uses ﬂoating-point numbers with the preorder–postordermethod. Range labeling methods [7] prepare appropriate intervals between preorder–
postorder labels in advance. However, these methods still require relabeling ofmany nodes when the prepared intervals for node insertions are used up. MonetDB is an open-source database system for high-performance applications indata mining, OLAP, GIS, XML query, text and multimedia retrieval [1]. MonetDB/XQuery [5, 6] encodes XML documents based on the preorder–postordermethod but achieves reasonable update costs by using a technique based on
logical pages. However, MonetDB/XQuery still cannot completely avoid renumbering the size and level ﬁelds of some nodes when updating the document.
Therefore, it is predicted that the update costs will degrade the performance ofMonetDB/XQuery, especially when processing large-scale XML documents withhigh update frequency.
Labeling methods that are capable of unrestrictedly inserting nodes without
relabeling any nodes, have been proposed [13–15, 17, 20]. In [20], the label of a

newly inserted node is made from the product of a prime number and the label of
its parent node. The label of the ancestor node can be extracted by factorizing thelabel of the child node. However, the factorization is still quite expensive. In [18],it was reported that the ORDPATH method [17] achieves both better structural
information extraction and storage consumption than the existing preﬁx-basedlabeling methods such as LSDX [8] and persistent labeling schemes [9,12]. Other
two update-friendly labeling schemes, namely QED [14] and CDBS [15], are more
eﬃcient than the ORDPATH method in respect to data updates. However, QED
has worse performance in some cases and CDBS results in both worse structural
information extraction and storage consumption than the ORDPATH method.
The DO-VLEI code [13] can achieve eﬃcient structural information extraction
as the ORDPATH method does. However, the size of DO-VLEI codes becomeslarger when labeling large-scale XML documents. The DO-VLEI code [13], whichis the basis of our proposed method, and the ORDPATH method, which is thebaseline of comparison in our experiments, will be described in detail in thefollowing two subsections.
2.1

DO-VLEI CodeWe ﬁrst introduce the deﬁnition of the VLEI (Variable Length Endless Insertable) code as follows.
Definition 1 (VLEI Code). A bit string v = 1 · {0|1}∗is a VLEI code, if thefollowing condition is satisfied.
v · 0 · {0|1}∗ < v < v · 1 · {0|1}∗
For example, 10 < 1 < 11 and 100 < 10 < 101 < 1 < 110 < 11 < 111. A new
VLEI code can be unrestrictedly generated from two arbitrary adjacent VLEI
codes by an eﬀective algorithm [13]. The VLEI code can be used for both thepreorder–postorder and the DO methods. Here, we focus on the combination of
the DO method and the VLEI code. It is named DO-VLEI code and deﬁned asfollows.
Definition 2 (DO-VLEI Code).
1. The DO-VLEI code of the root node Croot = 1.
2. The DO-VLEI code of a non-root node C = Cparent . Cchild , where Cparent
denotes the DO-VLEI code of its parent and Cchild denotes the VLEI code satisfying the appropriate sibling order.
The DO-VLEI code of the nth ancestor node can be obtained by extracting
the character string between the leftmost character and the nth delimiter. An
example XML document tree labeled by DO-VLEI code is illustrated in Figure 3.
2.2

ORDPATHORDPATH [17] is an update-friendly XML labeling method implemented inr SQL ServerT M 2005, in which arbitrary node insertions require no
Microsoft

1

1

B OOK

IS B N

BOOK

1.10

1.1

S E C T ION

1.10.101.10.1T IT E L

All…

1 .1.100

1.1.10 1.1.101

C AP T ION

1.10 .11

1.3

SECTIONS E C T ION

T IT E L Nobody… F IG UR E

ISBN

1.1

B OLD

free…
1.1.1

SECTION

TITEL

Nobody…

FIGURE

1.1.1

1.1.3

1.1.5

CAPTION

TITEL

All…

BOLD

free…

1.3.1

1.3.3

1.3.5
All…
1.3.5.1

1.3.7

love
1.1.101.1

Fig. 3. Labeling by DO-VLEI code

Fig. 4. Labeling by ORDPATH
11

01

BOOK

BOOK

ISBN

0101

1110 001101

SECTION

TITEL

Nobody…

FIGURE

0101010101101

010111001

CAPTION

TITEL
0110101

All…

1110

SECTIONSECTION
BOLD

free…

01101101 0110111001 0110111011
All…
011011100101

Fig. 5. Labeling by C-ORDPATH

TT IIT L E

Nobody..

11100100 1110010

ISBN

FIGURE
111001011

SECTION

CAPTION

TITLE
All...
11101000 1110100

BODY
111010free...
11101011

11101010 love

Fig. 6. Labeling by C-DO-VLEI code

relabeling of the existing nodes. The ORDPATH labels are also based on the
DO method, in that a child label is made from a sibling code, a delimiter, andthe label of its parent node. Figure 4 shows an XML tree labeled by ORDPATH.
In ORDPATH, only positive, odd numbers are assigned for the initial labeling;
negative integers and even numbers are reserved for insertions. The end of asibling code must be an odd number. For example, when the ORDPATH labelof a node is newly inserted between nodes labeled “1.3.1” and “1.3.3”, the label“1.3.2.1”, which is made by adding “1” to “1.3.2”, is assigned to the node. The
sibling code of “1.3.2.1” is “2.1”.
ORDPATH is implemented by a compressed binary representation using bit
strings {0, 1}, and is called C-ORDPATH. A pair of bit strings Li and Oi areused to represent an integer by using a preﬁx schema (see reference [17] fordetails). An ORDPATH label is a string of delimited integers, and i is the orderof the integer within the string. Li is a bit string specifying the number ofbits of Oi . Li is speciﬁed by analysis of the tree using the preﬁx schema. Oi istreated as a binary number within a range set by Li . For example, ORDPATH“1.5” is represented in C-ORDPATH as (0111001). (0111001) is divided into
(01,110-01) by sequential analysis using the preﬁx schema in [17]. (01) and (11001) are converted into “1” and “5” based on the Oi value range.C-ORDPATH
represents delimiters by delimiting the bit string according to the preﬁx schemaand compresses the label size. An XML tree labeled by the C-ORDPATH isshown in Figure 5.

3

C-DO-VLEI CodeIn this section, we propose a compressed binary representation of the DO-VLEI
code, called C-DO-VLEI code, which aims to reduce the label size. In this paper,“” denotes a character string, and () denotes a bit string. For example, “01” represents a concatenation of character 0 and 1, and (01) represents a bit sequenceof bit 0 and 1.
3.1

Components of the DO-VLEI CodeA DO-VLEI label is a variable-length character string constructed from the threecharacters “.”, “1”, and “0”, which satisﬁes the following three conditions.
(1) Consecutive “.” characters do not appear.
(2) “.” does not exist at the tail end of a label.
(3) The VLEI code starts with “1”.
According to the above conditions, the “1” that is the beginning of a VLEI
code always appears after “.”. Therefore, “.” and “1” can be combined as “.1”,
meaning that a DO-VLEI code is composed of the three elements “.1”, “1”, and
“0”.
3.2

Definition of C-DO-VLEI Code

The C-DO-VLEI code is deﬁned as follows.
Definition 3 (C-DO-VLEI Code). The three elements of a DO-VLEI code:“.1”, “1”, and “0”, are represented by the bit strings: (10), (11), and (0), respectively. This compressed binary representation of DO-VLEI codes is called
C-DO-VLEI code.
Note that the shortest bit string (0) is assigned to the “0” that can be
adjusted to appear more frequently than the other two components, and thatthe set of bit strings: (0), (10), and (11) are preﬁx codes. A preﬁx code is a setof words such that no word of the set is a preﬁx of another word in the set. By
sequentially analyzing the bit string from the preﬁx code, C-DO-VLEI codes canbe uniquely decoded into the original DO-VLEI codes. Figure 6 shows an XML
tree labeled by C-DO-VLEI codes.

4

Structural Information Extraction

In this section, we propose an eﬃcient method, based on register-length bit operations combining with the properties of Dewey Order numbers, for extracting
structural information between nodes from the C-DO-VLEI code. The extracted
structural information, such as depth, parent information, are necessary andvaluable for determining XPath axes in XPath query and for detecting LCAs or
SLCAs in XML keyword search. However, due to the space limitation, here wetake XPath query as an example to show how the extracted structural information work to determine the XPath axes. The most important and frequently used
XPath axes are listed in Table 1, in which parent, preceding-sibling, child andTable 1. XPath axes
Axis
Description
ancestor
all the ancestors of the context node (parent, grandparent, etc.)
preceding
all the nodes that precede the context node in the document except any ancestor nodes
descendant
all the descendants of the context node (children, grandchildren, etc.)
following
all the nodes that appear after the context node except any descendant nodes
parentthe single node that is the parent of the context nodepreceding-sibling all the nodes that have the same parent as the context node and appear before the context nodechild
the children of the context nodefollowing-sibling all the nodes that have the same parent as the context node and appear after the context nodefollowing-sibling are subsets of ancestor, preceding, descendant, and following,
respectively.
Next, we explain how to obtain this information from the C-DO-VLEI codesby using the properties of DO and simple code comparisons.
4.1

Using Properties of DO

Since C-DO-VLEI codes use the DO method, information about 1) depth ofnode, 2) parent’s label and 3) ancestors’ labels can be obtained by the following
three operations that use the properties of DO, respectively.
DO-1 : Count the number of delimiters.
DO-2 : Extract the preﬁx code before the rightmost delimiter.
DO-3 : Repeat DO-2 until the last delimiter is reached.
It is important to ﬁnd the locations and count the number of the delimiters
in C-DO-VLEI to implement DO-1 –DO-3. The most straightforward method
is to decode the label from the beginning to the end to detect the bit string(10) that is assigned for the delimiter. However, this is expensive when handling
long codes. To reduce the processing cost, we propose an eﬃcient method for
detecting the delimiters by using register-length bit operations instead of bit-bybit comparison.
Since the delimiter in C-DO-VLEI codes is assigned to bit string (10), any
place where the bit changes from (1) to (0) is a delimiter candidate. However,when “10” appears in the DO-VLEI code, the corresponding C-DO-VLEI willbe (110). That is, the last two bits are also (10). In order to distinguish these twopatterns of (10), we focus on the number of consecutive (1s) before the (0). In
the fragment of C-DO-VLEI code shown in Figure 7, wherever an odd number ofconsecutive (1s) appears before (0), the last two bits (10) represent a delimiter,while (10) ending at an even number of consecutive (1s) represents the DOVLEI code “10”. Therefore, it is possible to detect the delimiters by counting
the number of consecutive (1s). Next, we describe algorithms for operations DO1 –DO-3 based on delimiter detection. Notations for the bit operations used in
the proposed algorithms are shown in Table 2.
Algorithm for DO-1 The operation DO-1, namely the operation for detecting
the node depth, can be implemented by the following steps.

C-DO-VLEI code fragment

odd number of continuous (1)0delimiter
7

8

15

0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0

Fig. 7. Example fragment of a C-DO-VLEI code
Table 2. Bit operation notation
notation
descriptionxyleft shiftuxyright shift (logical shift)
x
NOT
x&y
AND
x|y
OR

D-1 : Generate a bit string, endPointOfOne, in which the initial values of
all the bits are (0), and only the last bit at the place where an odd numberof consecutive (1s) appears is set to (1). For the C-DO-VLEI code v shown in
Figure 4.1, the bit string endPointOfOne can be generated by v&v  1.
D-2 : Generate a bit string endPointOfOne’, in which the initial values of all
the bits are (0), and only the bit at the place where (0) changes to (1) in the
C-DO-VLEI code is set to (1). For the C-DO-VLEI code v shown in Figure 4.1,uthe bit string endPointOfOne’ can be generated by endP ointOf One1.
D-3 : Assuming that each bit of the code is assigned an integer ID, as shownin Figure 4.1, then the bit (1) in endPointOfOne is a delimiter if the condition
ID(i) − ID(j) = oddnumber is satisﬁed, where ID(i) and ID(j) denote the
ID of (1) in endPointOfOne and its nearest leftmost (1) in endPointOfOne’,
respectively. For example, the 5th bit (ID=4) in endPointOfOne is a delimiterbecause the ID of its nearest leftmost (1) in endPointOfOne’ is 1. However, the9th bit (ID=8) in endPointOfOne is not a delimiter because the ID of its nearest
leftmost (1) endPointOfOne’ is 6. Algorithm 1 shows the details of delimiter
detection. Algorithm 1 outputs a bit string pointOfDelimiter, in which the initialvalues of all the bits are (0), and only the bit indicating the place of delimiters
is set to (1).
D-4 : After the delimiters are found by Algorithm 1, the node depth can be
determined by counting the number of (1s) in pointOfDelimiter. Algorithm 2shows the details for counting the number of (1s) in a bit string based on thedivide-and-conquer algorithm [11].

Algorithm for DO-2 and DO-3 DO-2 ﬁnds the last delimiter from pointOfDelimiter generated by Algorithm 1, which is implemented by the following steps.
P-1 : Generate pointOfDelimiter.
P-2 : Generate a mask by(pointOfDelimiter& − pointOfDelimiter) − 1|label, as shown in Figure 9.

Algorithm 1 Delimiter detection
Input: C-DO-VLEI code v
Output: pointOfDelimiter
1: endPointOfOne ← v&v  1
2: delimiterEven ← v&(v+(endPointOfOne&0x5555))&0xAAAAu
3: v ← v1u
4: endPointOfOne ← endPointOfOne1
5: delimiterOdd ← v &(v + (endPointOfOne ← 0x5555))&0xAAAA
6: pointOfDelimiter ← delimiterEven|delimiterOdd

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

label

0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1

label+ 0000100010001010

endPointOfOne

0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0

pointOfDelimiterdelimiter

1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1

mask

0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0

0 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0

Fig. 8. Example of delimiter detection

label length of the parent node + 1

Fig. 9. Example of mask for extracting parent label

P-3 : The length of the parent label Lp can be obtained by counting thenumber of consecutive (1s) from the head of the mask. Algorithm 3 shows thedetails of how to count the number of (1s) from the head of a C-DO-VLEI code.
Finally, the parent label can be generated by outputting the Lp bits from thehead of the original label.
In addition, DO-3, namely obtaining the ancestors’ labels, can be implemented by repeating the above operations.
4.2

Using Code Comparison

Theorem 1. Let the bit strings v0 , vd , and v1 represent the three elements of
the C-DO-VLEI code “0”, “.1” and “1”, respectively. According to Definition 3,v0 = (0), vd = (10) and v1 = (11). Using Algorithm 4, comparison of the CDO-VLEI codes for two nodes yields the proper document order if v0 , vd and v1
satisfy the following equation4 .

Algorithm 2 Depth detection
Input: v (16-bit unsigned integer)
Output: number of (1) in v (depth)u
1: v ← v − ((v1)&0x5555)
u
2: v ← (v&0x3333) + ((v2)&0x3333)
u
3: v ← ((v + (v4))&0x0F0F)
u
4: v ← v + (v8)u5: v ← v + (v16)
6: depth ← v&0x001F
7: return depth
4Here we do not give the proofs of this theorem and the other relevant ones due tothe space limitation.

Algorithm 3 Count number of consecutive (1s) from the head of code
Input: v (16-bit unsigned integer)
Output: length of parent node, Lp
1: v ← v
2: n ← 16
3: c ← 8
4: repeat u
5:x ← v c6:
if x = 0 then
7:
n←n−c
8:
v←x
9:
end if u
10:c ← c1
11: until c = 0
12: return Lp = n − x

a: C-DO-VLEI code of the context node
a
a 1

Ⅰ

Ⅱ

ancestor ∪ preceding

descendant・Ⅲfollowinga: C-DO-VLEI code of the context nodep: C-DO-VLEI code of the parent of the context node
a
p
p 1
a 1

・

Ⅳ

preceding-sibling

child

Ⅴ

・

following-sibling

Fig. 10. Code range for ancestor, preced- Fig. 11. Code range for parent, precedinging, descendant and following
sibling, child and following-sibling

1 · v0 < 1 < 1 · vd < 1 · v1

(1)

Moreover, according to Deﬁnition 3 and the conditions described in Section 3.1, the code b for a descendant node of the node with code a is b =a · 10 · {11|0}∗. Therefore, according to Deﬁnition 1, a · 10 · {0}∗ ≤ b < a · 11 · {0}∗ .
That is, the codes of a and b satisfy the following equation, where ≺CDV denotes
the comparison based on Algorithm 4.
a ≺CDV b ≺CDV a · 1(2)

Similarly, the ancestor, preceding, and following nodes can be also obtainedby the code comparison using Algorithm 4. Therefore, as shown in Figure 10,
using the code a of a context node and a · 1 can divide the nodes into threeranges I, II and III for ancestor and preceding nodes, descendant nodes, andfollowing nodes, respectively.
Algorithm 4 Code comparison
Input: two C-DO-VLEI codes, v,w(length(v)≤length(w))
Output: v  ≥ w is true or false
1: l ← length(w) − length(v)

2: v ← v · 1 · {0}l −1
3: if v ≥ w then4:
return true
5: else6:
return false
7: end if

Table 3. XPath axis extraction method
Axis
Extraction method
ancestor
DO-3
preceding(node-set extracted from range I) - ancestor
descendantnode-set extracted from range II
following
node-set extracted from range III
parentDO-2
preceding-sibling nodes ∈ range IV ∩ nodes with the same depth as the context node (DO-1 )childnodes ∈ range II ∩ nodes whose depth is one more than the context node (DO-1 )following-sibling nodes ∈ range V ∩ nodes with the same depth as the context node (DO-1 )Table 4. Experimental EnvironmentCPU:
Dual-Core Intel Xeon 5110 (1.60GHz)
Memory: DDR2 ECC FB-DIMM 9GB(2GB×4, 512MB×2)
Storage: D-RAID RAID 0+1
HDD:
SEAGATE ST3750640AS (750GB, 7200rpm, 3.5inch)
OS:Linux 2.6.18 CentOS 5(Final)
Compiler: gcc (Red Hat 4.1.1-52)
RDB:
PostgreSQL 8.2.4

4.3

XPath Axis Determination Using Structural Information

Combining the code comparison method described in Section 4.2 and the operations introduced in Section 4.1, all the XPath axes listed in Table 1 canbe determined. First, the descendant and following nodes can be obtained byextracting nodes from ranges II and III, respectively. Ancestor nodes can beobtained by using DO-3 , and then preceding nodes can be obtained by excluding ancestor nodes from range I. The parent node can be directly determinedby DO-2. Using the codes of the context node and its parent, the ranges IV
and V for preceding-sibling and following-sibling nodes can be determined byusing Algorithm 4, as shown in Figure 11. As the depth of preceding-sibling andfollowing-sibling nodes are the same as the context node, and the child nodes
are deeper by one than the context node, the preceding-sibling, following-sibling,
and child nodes can be extracted from the ranges IV, V and II by using DO1. The extraction methods for XPath axes listed in Table 1 are summarized inTable 3.

5

Experimental Evaluation

We performed experiments within the environment described in Table 4 to evaluate the storage consumption and performance of DO-1 –DO-3, comparing the
C-DO-VLEI code with C-ORDPATH. The XML documents used for the experiments were generated by xmlgen [3], using scale factors (SF) from 0.001 to 1,
and were sourced from the XML Data Repository [2]. Table 5 shows the detailsof these XML documents. For the evaluation of performance, the labels of all

Table 5. XML documents
XML document
size (byte) elements max. depth avg. depth max. fanout avg. fanout
SwissProt.xml
114820211 2977031
53.556711
50000
2.034511
dblp.xml
133862772 3332130
62.902279
3288581.943555
ebay.xml
35525
156
5
3.75641380
5.391305
item0.xml(xmlgen SF=1)118552713 1666315
125.547796
25500
2.10692
item1.xml(xmlgen SF=0.1)
11875066
16786512
5.5482442550
2.103751
item2.xml(xmlgen SF=0.01)
118254717132
125.506012
255
2.102092
item3.xml(xmlgen SF=0.001)
1182741729
12
5.717756
25
2.04965
lineitem.xml
32295475 1022976
3
2.941175
60175
1.941175
nasa.xml
25050288
4766468
5.5831412435
2.000728
orders.xml
5378845
1500013
2.899987
15000
1.899987
part.xml
61818120001
32.899905
2000
1.899905
partsupp.xml
224186848001
32.833295
8000
1.833295
psd7003.xml
716853012 21305818
7
5.15147
2625261.818513
reed.xml
28361910546
43.199791
703
1.809579
treebank e.xml
86082517 2437666
367.872788
56384
1.571223
uwm.xml
233752266729
53.952435
2112
1.952276
wsu.xml
164786474557
43.157866
3924
2.077534

the nodes for each document were stored in a document table, and the labels of
the nodes in all documents of the same depth were stored in a depth table.
We compared the C-DO-VLEI code with C-ORDPATH to evaluate the performance of DO-1 –DO-3 5 . Figure 12 shows the execution time ratio for extracting depth information, parent labels, and ancestor labels from the depthtables, using the C-DO-VLEI code and C-ORDPATH6 . From this ﬁgure, we
can see that the greater the node depth, the better is the performance by the
C-DO-VLEI code in extracting node depth and parent labels. This is becausedelimiter detection in ORDPATH requires traversal from the head through thewhole code and refers to the preﬁx schema for determining each delimiter. On
the other hand, there is no signiﬁcant diﬀerence in extracting the ancestor labels,
because, even for the C-DO-VLEI code, output of all the ancestors requires handling of all delimiters one by one. Figure 13 shows the execution time ratio using
the document tables. From these results, we deduce that the execution times for
extracting depth information and parent labels using the C-DO-VLEI code areabout 25% and 15% less than execution times using C-ORDPATH, respectively,
which indicates that the proposed method can achieve high performance in suchapplications as XPath query and keyword search.
We then measured and compared the total label size of each XML document
labeled by the C-DO-VLEI code and C-ORDPATH. Figure 14 shows the label
size ratio of the C-DO-VLEI code to C-ORDPATH for each XML document,from which we can learn that the average label size using the C-DO-VLEI code
is about 24% on the average smaller than that using the C-ORDPATH, whichmeans taht the proposed method also outperforms the ORDPATH method withrespect to storage consumption.

5

There is no signiﬁcant performance diﬀerence between C-DO-VLEI and CORDPATH in detecting other XPath axes, because they can determine such axes as
descendant or following by simple code comparison. Therefore, only the experimental
evaluation of DO-1 –DO-3 is discussed in this paper.
6
Note that the label size using C-ORDPATH is set to 1 (same in Figure 13 and 14).

1.2

depth
parent1.1

ancestor

1

1.2
1.1

depth
parentancestor

1
0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5
0.4

0.5
1

2

3

4

5

6

7

8

9

10

11

12

Fig. 12. Execution time ratio of C-DOVLEI to C-ORDPATH (horizontal axis:
depth of node)Fig. 13. Execution time ratio of C-DOVLEI to C-ORDPATH (horizontal axis:
XML document)

Fig. 14. Label size ratio of C-DO-VLEI to C-ORDPATH (horizontal axis: XML documents)

6

Conclusion

To achieve both eﬃcient structural information extraction and low storageconsumption for large XML documents with high update frequency, in this paper we have proposed the C-DO-VLEI code, an update-friendly XML labelingmethod. To achieve eﬃcient structural information extraction, we have proposeda novel and eﬃcient method based on register-length bit operations combining
with the properties of DO numbers, which are not able to be implemented inother bit-vector encoding schemes including ORDPATH. Meanwhile, the C-DOVLEI code also achieves lower storage consumption by using a compressed binary
representation using DO numbering schemes without any preﬁx schema.
We have performed experiments to evaluate and compare the storage consumption and performance of the proposed method with those of the C-ORDPATH
method. Experimental results indicate that: 1) the execution times for extracting
depth information and parent node labels using the C-DO-VLEI code are about
25% and 15% less, respectively, than for C-ORDPATH, which enables the proposed method to achieve high performance in such applications as XPath queryand keyword search; 2) the label size using the C-DO-VLEI code is about 24%

smaller than that using C-ORDPATH, which means taht the proposed method
also outperforms the ORDPATH method with respect to storage consumption.

References
1. MonetDB. http://monetdb.cwi.nl/.
2. XML Data Repository. http://www.cs.washington.edu/research/xmldatasets/.
3. Xmlgen. http://monetdb.cwi.nl/xml/downloads.html.
4. Toshiyuki Amagasa, Masatoshi Yoshikawa, and Shunsuke Uemura. QRS: A Robust
Numbering Scheme for XML Documents. In Proc. of ICDE, pages 705–707, 2003.
5. Peter A. Boncz, Jan Flokstra, Torsten Grust, Maurice van Keulen, Stefan Manegold, K. Sjoerd Mullender, Jan Rittinger, and Jens Teubner. MonetDB/XQueryConsistent and Eﬃcient Updates on the Pre/Post Plane. In Proc. of EDBT, pages
1190–1193, 2006.
6. Peter A. Boncz, Torsten Grust, Maurice van Keulen, Stefan Manegold, Jan Rittinger, and Jens Teubner. MonetDB/XQuery: A Fast XQuery Processor Poweredby a Relational Engine. In Proc. of SIGMOD Conference, pages 479–490, 2006.
7. Edith Cohen, Haim Kaplan, and Tova Milo. Labeling Dynamic XML Trees. In
Proc. of PODS, pages 271–281, 2002.
8. Maggie Duong and Yanchun Zhang. LSDX: A New Labeling Scheme for Dynamically Updating XML Data. In Proc. of ADC, pages 185–193, 2005.
9. Alban Gabillon and Majirus Fansi. A persistent labelling scheme for XML andtree databases. In Proc. of SITIS, pages 110–115, 2005.
10. Dale Gerdemann. Parsing As Tree Traversal. In Proc. of COLING, pages 396–400,
1994.
11. Jr. Guy L Steele. Hacker’s Delight. Addison-Wesley Professional, 2003.
12. Aye Khaing and Ni Lar Thein. A Persistent Labeling Scheme for Dynamic Ordered
XML Trees. In Proc. of Web Intelligence, pages 498–501, 2006.
13. Kazuhito Kobayashi, Wenxin Liang, Dai Kobayashi, Akitsugu Watanabe, andHaruo Yokota. VLEI code: An Eﬃcient Labeling Method for Handling XML Documents in an RDB. In Proc. of ICDE, pages 386–387, Tokyo, Japan, 2005(poster).
14. Changqing Li and Tok Wang Ling. Qed: a novel quaternary encoding to completely
avoid re-labeling in xml updates. In Proc. of CIKM, pages 501–508, 2005.
15. Changqing Li, Tok Wang Ling, and Min Hu. Eﬃcient Processing of Updates inDynamic XML Data. In Proc. of ICDE, page 13, 2006.
16. Wenxin Liang, Takeshi Miki, and Haruo Yokota. Superimposed Code-based Indexing Method for Extracting MCTs from XML Documents. In Proc. of DEXA,
pages 508–522, 2008.
17. Patrick E. O’Neil, Elizabeth J. O’Neil, Shankar Pal, Istvan Cseri, Gideon Schaller,
and Nigel Westbury. ORDPATHs: Insert-Friendly XML Node Labels. In Proc. of
ACM SIGMOD Conference, pages 903–908, 2004.
18. Virginie Sans and Dominique Laurent. Preﬁx Based Numbering Schemes for XML:
Techniques, Applications and Performances. In Proc. of VLDB, pages 1564–1573,
2008.
19. Igor Tatarinov, Stratis Viglas, Kevin S. Beyer, Jayavel Shanmugasundaram, Eugene J. Shekita, and Chun Zhang. Storing and Querying Ordered XML Using a
Relational Database System. In Proc. of ACM SIGMOD Conference, pages 204–
215, 2002.
20. Xiaodong Wu, Mong-Li Lee, and Wynne Hsu. A Prime Number Labeling Scheme
for Dynamic Ordered XML Trees. In proc. of ICDE, pages 66–78, 2004.