基于hamming范数的xml流相关性估测算法

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