%0 Journal Article
%T Correlation Estimating Algorithm of XML Stream Based on Hamming Norms<br>基于Hamming范数的XML流相关性估测算法
%A SUN He
%A ZHU Hong
%A <br>孙贺
%A 朱洪
%J 软件学报
%D 2010
%I 
%X It is of great importance to compare the correlation of different XML (extensible markup language) streams in the limited space in the Database Theory. In the study of these problems, several measures are proposed, e.g. the tree-edit distance, to show the difference of XML trees. This paper proposes a natural measure l0 employing Hamming norms, i.e. the number of distinct sub-trees between two XML trees, to estimate the correlation. Furthermore, a probabilistic estimating algorithm involving space-bounded pseudorandom generators, stable distributions and hash functions has been presented in the data stream model. Theoretical time/space complexity analysis, correctness proof and experimental simulation show that this algorithm can give a desired approximation.
%K algorithm design
%K data stream
%K Hamming norm
%K stable distribution
%K XML (extensible markup language)<br>算法设计
%K 数据流
%K Hamming范数
%K 稳态分布
%K XML(extensible
%K markup
%K language)
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=FDE78613FBCEE0C046653AF2373F6726&yid=140ECF96957D60B2&vid=659D3B06EBF534A7&iid=E158A972A605785F&sid=B7DE0F3CA34DA149&eid=DC06EBDBAF4E06D3&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=13