摘要
针对基于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.
出处
《计算机学报》
EI
CSCD
北大核心
2014年第8期1732-1742,共11页
Chinese Journal of Computers
基金
国家自然科学基金(60703068
60873068
61003003)
辽宁省科学技术计划项目基金(2012216007)资助~~