Efficient Construction for Path Expression in XML data

Abstract

XML and semi-structured data have been widely and significantly used as a standard for representing and exchanging data. Generally, they are modeled as a labeled directed graph. With a given path expression, it is desirable to choose nodes or node-sets fast and efficiently. To serve this purpose, the A(k)-index created a graph index based on the concept of bisimilarity. The naive approach of the A(k)-index that requires an exhaustive scan method for all partitions takes an expensive index construction cost. In this paper, we propose the New ImpIndexa new approach of index construction to reduce time by marking method. This technique marks the significant couple of partitions in scan work, then traverses only on these partitions and ignores the others for the next iterations. A salient property of the New ImpIndex is still stable with the big database and the large value of k. Moreover, we associate this approach with our previously proposed one: the Old ImpIndex to create the Asso ImpIndex for achieving higher performance. We experimentally demonstrate that our proposed algorithms: New ImpIndex and Asso ImpIndex show more advantages than the existing approach.