L(k)-index:一种支持标签路径的高效k双拟结构索引

L(k)-index:An Efficient k-bisimilarity Based Structural Summary Supporting Label Path

针对基于k双拟的结构索引创建和更新低效问题、查询结果重复验证问题以及标签路径不可获得性问题,提出了一种新的结构索引L(k)-index.L(k)-index通过引入标签路径,在创建时无须k次遍历原数据,并采取批量更新策略,大大提高索引创建和更新的效率,而在空间上仅有很小增加.对于长度大于k+1的路径查询,L(k)-index无须访问原数据进行验证,并支持批量节点的标签路径获得.通过大量实验表明,同A(k)-index相比,L(k)-index创建时间平均提高66.7%,查询处理时间效率平均提高68.9%,批量更新效率平均每节点提高58.8%,而空间仅增加22.5%.

L（k）-index,as a novel structural summary,is proposed to address the issues of the low efficiency of summary constructing and updating,the re-validation of query results and the absence of label path for the k-bisimilarity summaries.With the label path introduced,L（k）-index doesn＇t require scanning the original XML data k times for the summary constructing,and applies a batch policy to summary updating.As a result,the runtime of summary constructing and updating is improved greatly with the small increase of space overhead.For L（k）-index,there＇s no re validation of original data for greater than k＋1 length query,and the label path of nodes can be retrieved on batch.With the extensive experiments,L （k）-index compared with A（k）-index averagely achieves 66.7％ improvement of construction,68.9％ improvement of query processing,58.8％ improvement of updating per node,while suffering from 22.5％ space increase.