最近公共祖先算法在管道运输的应用

介绍最近公共祖先算法的原理和应用,并总结四种最近公共祖先算法:欧拉序结合ST表法、倍增法、并查集结合Tar⁃jan算法和树链剖分法,重点剖析欧拉序结合ST表法具体的算法过程。提出数列区间操作问题的解决方案,并将此推广在树中,讨论两种树链操作方式:树上差分和相对于根结点的树上标记法。将最近公共祖先算法与树上标记结合,并运用在管道运输问题上,能在O(n log2n)的算法复杂度下,监控管道运输网络的最大压力值。

基于Hole-Filler模型的XML数据流上的SLCA算法

与传统数据库对XML数据的处理不同,对XML数据流的处理不仅受实时性的约束,还受存储空间的限制.在XML片段无序传送的广播模型中,考虑在XML数据流上进行高效的关键字查询,进而首次提出近似SLCA算法.SLCA算法利用结构Hash表和LCA表对关键字进行匹配并计算SLCA,从而避免冗余操作.同时,SLCA算法可以对匹配结果立即输出而不必等到数据流传输结束.实验结果表明,基于Hole-Filler模型的XML数据流上的SLCA算法在节省时间和空间开销方面均表现出较好的性能.

LCA关系序对导引小枝查询

让关系数据库支持XML数据存储和查询,是XML领域重要的研究分支.DM XML系统以关系数据库为平台,融合结构映射和模型映射,根据路径统计实现了路径分区的编码方案.提出了DM XML查询模式集的解析、验证和生成方法.集合中的模式对应唯一的约束节点LCA关系序对,该序对并能严格地转化为等价的SQL查询.从实验数据分析,表明了DM XML编码方案的合理性和路径查询的高效性.

基于LCA分块算法的大学科研人员信息抽取

现有的半结构化网页信息抽取方法主要假设有效数据间具有较强结构相似性,将网页分割为具有类似特征的数据记录与数据区域然后进行抽取。但是存有大学科研人员信息的网页大多是人工编写填入内容,结构特征并不严谨。针对这类网页的弱结构性,提出了一种基于最近公共祖先(lowest common ancestor,LCA)分块算法的人员信息抽取方法,将LCA和语义相关度强弱的联系引入网页分块中,并提出了基本语义块与有效语义块的概念。在将网页转换成文档对象模型(document object model,DOM)树并进行预处理后,首先通过向上寻找LCA节点的方法将页面划分为基本语义块,接着结合人员信息的特征将基本语义块合并为存有完整人员信息的有效语义块,最后根据有效语义块的对齐获取当前页面所有关系映射的人员信息。实验结果表明,该方法在大量真实的大学人员网页的分块与抽取中,与MDR(mining data records)算法相比仍能保持较高的准确率与召回率。

SWALLOW:一个稳定的WLAN区域定位系统

介绍WLAN定位系统SWALLOW的设计与实现.本系统对WLAN中携带定位卡的人员或设备实施定位,考虑到定位卡的成本与能耗,本系统采用接入点而非定位卡收集RSSI值.而各接入点对定位卡同一信号的RSSI测值往往存在缺失和不同步,因此传统的基于点的RSSI特征比对算法稳定性不好.本系统使用了一个新的基于区域的定位算法,该算法在最小信号距离比对的初步结果上,通过在生成树上寻找最近公共祖先的方法实现平滑.分析和实验表明,该算法能将静止定位稳定度从50%提高到95%,并保持90%以上的移动定位准确度和10s以下的延时.目前,SWALLOW系统已应用到资产管理系统中.

综合文档语义与用户查询语义的XML关键字检索

为了解决XML关键字查询中语义信息丢失的问题,提出了一种语义相关的关键字检索方法。利用文档的半结构化特点提取文档隐含的语义,利用查询语法捕获用户查询意图,然后根据用户意图查询满足条件的元素,并结合文档语义,由最小最近公共祖先改进为语义相关实体子树集来表达查询结果。实验结果表明,该方法能够有效提高关键字检索结果的查准率。

适用于稀疏图的基于关键点标记的可达性算法

有向图中任意两点间的可达性查询是研究各种网络问题时的一个基础操作,如在社交网络中查询两个人是否相互关注等。但随着网络规模的日益扩大,传统算法因巨大的时间或空间复杂度而变得难以被应用。因此需要根据网络结构特点针对性地使用合适的可达性算法。稀疏图可以看作由若干有向生成树与少量非树边组成,GRKPL算法将稀疏图中的可达性问题拆分成两部分:树上可达性问题与加入非树边后带来的影响。前一部分使用区间标记法解决;后一部分通过构造关键点集,将原图中所有的可达性查询转化为关键点集中的查询后得以解决。关键点集包括所有被非树边覆盖的节点,以及这些节点按照前序遍历的顺序排序后相邻节点之间的最近公共祖先。证明了关键点集的大小与原图中非树边的规模具有相同的数量级。最后在10个中小规模与4个大规模现实数据集上进行了测试,GRKPL在中小规模数据集上表现优异,查询处理时间相较于其他算法平均减少49.8%,空间占用平均减少65.1%。