一种面向XML数据的SLCA求解算法
An SLCA computation for keyword queries on XML data作者机构:燕山大学信息科学与工程学院河北秦皇岛066004
出 版 物:《燕山大学学报》 (Journal of Yanshan University)
年 卷 期:2013年第37卷第4期
页 面:339-346页
学科分类:08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家自然科学基金资助项目(61272124 61103139) 河北省重点基础研究资助项目(10963527D)
摘 要:针对现有方法计算SLCA语义时存在冗余计算问题,提出了一种基于列存储的倒排索引,并结合哈希查找,以自顶向下的方式查询处理的算法TDCOL-HS,来避免现有算法公共祖先重复处理的问题。算法以最短倒排表作为处理对象,将检测给定结点是否包含其他关键字的操作转化为哈希查找操作,其时间复杂度为×1,最后通过比较各种指标,从不同角度对算法的性能进行了验证.