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

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

作　　者：李晓光[1] 宋宝燕[1] 于戈[2] 王大玲[2] 

机构地区：[1]辽宁大学信息学院,沈阳110036 [2]东北大学信息科学与工程学院,沈阳110004

出　　处：《计算机学报》2014年第8期1732-1742,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60703068;60873068;61003003);辽宁省科学技术计划项目基金(2012216007)资助~~

摘　　要：针对基于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.

关 键 词：k双拟结构索引 XML索引 标签路径 XML查询 XML检索 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]