A Prime Number Approach to Matching an XML Twig Pattern including Parent-Child Edges

Shtwai Alsubai, Siobhán North

2017

Abstract

Twig pattern matching is a core operation in XML query processing because it is how all the occurrences of a twig pattern in an XML document are found. In the past decade, many algorithms have been proposed to perform twig pattern matching. They rely on labelling schemes to determine relationships between elements corresponding to query nodes in constant time, therefore the processing time is improved. In this paper, a new algorithm TwigStackPrime is proposed, which is an improvement to TwigStack (Bruno et al., 2002). To reduce the memory consumption and computation overhead of twig pattern matching algorithms when Parent-Child (P-C) edges are involved, TwigStackPrime efficiently filters out a tremendous amount of irrelevant elements and avoid unnecessary computations by introducing a new labelling scheme, called Child Prime Labels (CPL). Extensive performance studies on various real-world and artificial datasets were conducted to demonstrate the significant improvement of CPL over the previous indexing and querying techniques. The experimental results show that the new technique has a superior performance to the previous approaches.

Paper Citation

in Harvard Style

Alsubai S. and North S. (2017). A Prime Number Approach to Matching an XML Twig Pattern including Parent-Child Edges . In Proceedings of the 13th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST, ISBN 978-989-758-246-2, pages 204-211. DOI: 10.5220/0006225602040211

in Bibtex Style

@conference{webist17,
author={Shtwai Alsubai and Siobhán North},
title={A Prime Number Approach to Matching an XML Twig Pattern including Parent-Child Edges},
booktitle={Proceedings of the 13th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,},
year={2017},
pages={204-211},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0006225602040211},
isbn={978-989-758-246-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 13th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,
TI - A Prime Number Approach to Matching an XML Twig Pattern including Parent-Child Edges
SN - 978-989-758-246-2
AU - Alsubai S.
AU - North S.
PY - 2017
SP - 204
EP - 211
DO - 10.5220/0006225602040211