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