DeweyTP：一种面向概率XML数据的编码方案

doi:10.3969/j.issn.1000-436x.2013.11.004

通信学报 ›› 2013, Vol. 34 ›› Issue (11): 26-32.doi: 10.3969/j.issn.1000-436x.2013.11.004

DeweyTP：一种面向概率XML数据的编码方案

陈子阳¹,刘佳^1,²,张刘辉¹,周军锋¹

¹ 燕山大学信息科学与工程学院，河北秦皇岛 066004
² 中国环境管理干部学院，河北秦皇岛 066004

出版日期:2013-11-25 发布日期:2017-06-23
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目

DeweyTP: a labeling scheme for probabilistic XML data

Zi-yang CHEN¹,Jia LIU^1,²,Liu-hui ZHANG¹,Jun-feng ZHOU¹

¹ School of Information Science and Engineering, Yanshan Univers ty, Qinhuangdao 066004, China
² Environmental Management College of China, Qinhuangdao 066004, China

Online:2013-11-25 Published:2017-06-23
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

与普通XML文档相比，概率XML数据中节点的类型不唯一且节点的出现具有相应的概率。提出一种高效的编码策略DeweyTP，该编码策略为每个XML数据节点分配唯一的能够体现节点类型和路径概率的编码，来支持节点类型检测和路径概率提取，因而提升系统性能。最后通过实验从时间和空间两方面验证了 DeweyTP编码的高效性。

关键词: 概率XML文档, DeweyTP编码, 编码方案, Dewey编码

Abstract:

Compared with ordinary XML documents, nodes in the probabilistic XML documents have two characteristics, the type of nodes was non-unique and the nodes exist with a corresponding probability. As an efficient labeling scheme, DeweyTP was proposed to assign each node a unique label, which contains the type and path probability of nodes, supporting the detection of node type and the extraction of path probability, and thus improves the system performance. Finally, experimentally evaluated DeweyTP encoding scheme were experimentally evaluated in aspects of time and space efficiency.

Key words: probabilistic XML document, DeweyTP encode, labeling scheme, Dewey encode

陈子阳,刘佳,张刘辉,周军锋. DeweyTP：一种面向概率XML数据的编码方案[J]. 通信学报, 2013, 34(11): 26-32.

Zi-yang CHEN,Jia LIU,Liu-hui ZHANG,Jun-feng ZHOU. DeweyTP: a labeling scheme for probabilistic XML data[J]. Journal on Communications, 2013, 34(11): 26-32.

图/表 4

参考文献 13

[1]	SENELLART P , ABITEBOUL S . On the complexity of managin probabilistic XML data[A]. The 28th ACM SIGACT-SIGMOD- SI-GART Symposium on Principles of Database Systems[C]. 2007.283-292.
[2]	NIERMAN A , JAGADISH H V . ProTDB: probabilistic data in XML[A]. The 28th International Conference on Very Large Data Bases[C]. 2002.646-657.
[3]	HUNG E , GETOOR L , SUBRAHMANIAN V S . Pxml: a probabilistic semistructured data model and algebra[A]. The 19th International Conference on Data Engineering[C]. 2003.467-478.
[4]	KEULEN M V , KEIJZER A D , ALINK W . A probabilistic XML approach to data integration[A]. The 21st International Conference on Data Engineering[C]. 2005.459-470.
[5]	ABITEBOUL S , KIMELFELD B , SAGIV Y , et al. On the expres-siveness of probabilistic XML models[J]. The International Journal on Very Large Data Bases, 2009,18 (5): 1041-1064.
[6]	KIMELFELD B , KOSHAROVSKY Y , SAGIV Y . Query efficiency n probabilistic XML models[A]. The ACM SIGMOD International Conference on Management of Data[C]. 2008.701-714.
[7]	ABITEBOUL S , ALSTRUP S , KAPLAN H , et al. Compact labeling scheme for ancestor queries[J]. SIAM J Comput 2006,35 (6): 1295-1309.
[8]	COHEN E , KAPLAN H , MILO T . Labeling dynamic XML trees[A]. The Symposium on Principles of Database Systems[C]. 2002.271-281.
[9]	TATARINOV I , VIGLAS S , BEYER K S , et al. Storing and querying ordered XML using a relational database system[A]. The ACM SIG-MOD International Conference on Management of data[C]. 2002.204-215.
[10]	LI J X , LIU C F , ZHOU R , et al. Top-k keyword search over probabil-istic XML data[A]. The 27th International Conference on Data Engi-neering[C]. 2011.673-684.
[11]	XU Y , PAPAKONSTANTINOU Y . Efficient keyword search for smallest LCAs in XML databases[A]. The ACM SIGMOD Interna-tional Conference on Management of Data[C]. 2005.537-538.
[12]	SUN C , CHAN C Y , GOENKA A K . Multiway slca-based keyword search in xml data[A]. The 16th International Conference on World Wide Web[C]. 2007.1043-1052.
[13]	ZHOU J F , BAO Z F , WANG W , et al. Fast SLCA and ELCA com-putation for XML keyword queries based on set intersection[A]. The 28th International Conference on Data Engineering[C]. 2012.905-916.

大小	独立节点个数	互斥节点个数	普通节点个数
10 MB	25 192	25 197	167 865
20 MB	50 419	50 373	336 244
40 MB	90 173	90 070	601 550

编码策略	文件	文件存储的内容
DeweyTP	TypePro	压缩后的DeweyTP编码
DeweyTP	TextType-Pro	文本的ID和其DeweyTP编码的对应关系
DeweyTypePro	Type	改进的Dewey编码
DeweyTypePro	Pro	路径概率

DeweyTP：一种面向概率XML数据的编码方案

DeweyTP: a labeling scheme for probabilistic XML data

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 13

相关文章 1

Metrics

推荐阅读 0