A new structure for accelerating xpath location steps

Yaokai Feng, Akifumi Makinouchi

Research output: Contribution to journalArticlepeer-review


Indexing technology is one of the kernel technologies in database management systems, especially for large datasets. XML (eXtensible Markup Language) has been successfully adopted as a universal data exchange format, particularly in the WWW environment. It is an important and basic task to efficiently implement XPath axes on XML documents. Using R*-tree, T. Grust proposed an interesting method to support all XPath axes. In this method, all of the nodes of an XML document are mapped to a point set in a five-dimensional space. T. Grust clarified the fact that each of the XPath axes can be implemented by a range query in the abovementioned five-dimensional space. Thus, R*-tree (one of the popular multidimensional indices) was used to improve the query performance for XPath axes. However, according to our investigations, most of the range queries for the XPath axes are partially-dimensional range queries. If the existing multidimensional indices are used for such range queries, a great deal of information that is irrelevant to the queries must also be read from disk. Based on this observation, a new multidimensional index structure, called Adaptive R*-tree (AR*-tree), is proposed herein to support the XPath axes more efficiently.

Original languageEnglish
Pages (from-to)113-121
Number of pages9
JournalIAENG International Journal of Computer Science
Issue number2
Publication statusPublished - May 25 2011

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


Dive into the research topics of 'A new structure for accelerating xpath location steps'. Together they form a unique fingerprint.

Cite this