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

作     者：孙贺 朱洪 SUN He;ZHU Hong

作者机构：复旦大学上海市智能信息处理重点实验室上海200433 华东师范大学上海市高可信计算重点实验室上海200062 

基　　金：国家高技术研究发展计划(863)No.2007AA01Z189 上海重点学科建设项目资助No.B412~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2010年第21卷第4期

页      码：672-679页

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

主 题 词：算法设计 数据流 Hamming范数 稳态分布 XML(extensible markup language) 

学科分类：08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3724/SP.J.1001.2010.03430

馆 藏 号：203487395...