基于Hamming范数的XML流相关性估测算法

• 作者: 孙贺 朱洪
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 算法设计 数据流 Hamming范数 稳态分布 XML(extensible markup language)
• 年，卷（期）: 2010,（4）
• 所属期刊栏目: 数据库技术
• 页码范围: 672-679
• 页数: 8页
• 分类号: TP311
• 字数: 6465字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03430

摘要

在数据库理论中,如何在较小的空间条件下快速地比较不同的XML(extensible markup language)流的差异性是一个基本问题.在这一问题的研究中,人们提出了树编辑距离等测度来描述XML文本的差异性.提出了一种基于Hamming范数的l0测度--即XML树的不同子树的个数,并以此来刻画XML文本的相关性.在数据流模型下,给出了基于空间有界伪随机数发生器、稳态分布于哈希函数的l0测度的概率算法.理论上的时空复杂性分析、正确性证明与实验模拟结果表明,这一概率算法对问题的输入提供了一个理想的近似.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙贺	复旦大学上海市智能信息处理重点实验室	1	1	1.0	1.0
2	朱洪	华东师范大学上海市高可信计算重点实验室	2	5	1.0	2.0