L-Tree: A dynamic labeling structure for ordered XML data

Yi Chen, George Mihaila, Rajesh Bordawekar, Sriram Padmanabhan

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


With the ever growing use of XML as a data representation format, we see an increasing need for robust, high performance XML database systems. While most of the recent work focuses on efficient XML query processing, XML databases also need to support efficient updates. To speed up query processing, various labeling schemes have been proposed. However, the vast majority of these schemes have poor update performance. In this paper, we introduce a dynamic labeling structure for XML data: L-Tree and its order-preserving labeling scheme with O(log n) amortized update cost and O(log n) bits per label. L-Tree has good performance on updates without compromising the performance of query processing. We present the update algorithm for L-Tree and analyze its complexity.

Original languageEnglish (US)
Pages (from-to)209-218
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'L-Tree: A dynamic labeling structure for ordered XML data'. Together they form a unique fingerprint.

Cite this