Systematic partitioning and labeling XML subtrees for efficient processing of XML queries in IoT environments

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


With the advent of IoT, storing, indexing and querying XML data efficiently is critical. To minimize the cost of querying XML data, researchers have proposed many indexing techniques. Nearly all the techniques, partition the XML data into a number of data-streams. To evaluate a query, existing twig pattern matching algorithms process a subset of the data-streams simultaneously. Processing many data-streams simultaneously results in some or all of the following four problems, namely, the accessing of many data nodes which don't appear in the final solution of a given query, the generation of duplicate results, the generation of huge number of intermediate results, and the cost of merging the generated intermediate results. To the best of our knowledge, all the existing twig pattern matching algorithms suffer from some or all of the above mentioned problems. This paper proposes a new twig pattern matching algorithm called MatchQTP which processes one data-stream at a time and avoids all the above mentioned four problems. It also proposes a new indexing technique called RLP-Index and a new XML node labeling scheme called RLP-Scheme, both of which are used by MatchQTP. Unlike the existing indexing techniques, RLP-Index stores a subset of the data nodes. The rest of the data nodes can be generated efficiently. This minimizes storage space utilization and query processing time and makes RLP-Index the first of its kind. Many experiments were conducted to study the performance of MatchQTP. The results show that MatchQTP is very efficient and highly scalable. It was also compared with four algorithms, three of which are used frequently in the literature to compare the performance of new algorithms and the fourth algorithm is the state-of-the-art algorithm.

Original languageEnglish
Article number9051692
Pages (from-to)61817-61833
Number of pages17
JournalIEEE Access
StatePublished - 2020

Bibliographical note

Funding Information:
This work was supported by the King Abdulaziz City for Science and Technology (KACST) through the Science and Technology Unit at King Fahd University of Petroleum and Minerals (KFUPM), as part of the National Science, Technology and Innovation Plan, under Grant 11-INF1657-04.

Publisher Copyright:
© 2013 IEEE.


  • IoT
  • XML indexing
  • XML query processing
  • node labeling
  • tree-pattern matching
  • twig queries

ASJC Scopus subject areas

  • Computer Science (all)
  • Materials Science (all)
  • Engineering (all)


Dive into the research topics of 'Systematic partitioning and labeling XML subtrees for efficient processing of XML queries in IoT environments'. Together they form a unique fingerprint.

Cite this