%0 Journal Article
%T 基于hamming范数的xml流相关性估测算法
%A 孙贺？
%A 朱洪？
%J 软件学报
%P 672-679
%D 2010
%X 在数据库理论中,如何在较小的空间条件下快速地比较不同的xml(extensiblemarkuplanguage)流的差异性是一个基本问题.在这一问题的研究中,人们提出了树编辑距离等测度来描述xml文本的差异性.提出了一种基于hamming范数的l0测度——即xml树的不同子树的个数,并以此来刻画xml文本的相关性.在数据流模型下,给出了基于空间有界伪随机数发生器、稳态分布于哈希函数的l0测度的概率算法.理论上的时空复杂性分析、正确性证明与实验模拟结果表明,这一概率算法对问题的输入提供了一个理想的近似.
%K 算法设计
%K 数据流
%K hamming范数
%K 稳态分布
%K xml(extensible
%K markup
%K language)
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3430&flag=1