面向概率RDF数据库查询的数据清洗

doi:10.3969/j.issn.1000-5641.2018.01.008

华东师范大学学报(自然科学版) ›› 2018, Vol. 2018 ›› Issue (1): 76-90.doi: 10.3969/j.issn.1000-5641.2018.01.008

面向概率RDF数据库查询的数据清洗

王桢, 林欣

华东师范大学上海市多维度信息处理重点实验室, 上海 200062

收稿日期:2016-12-03 出版日期:2018-01-25 发布日期:2018-01-11
通讯作者: 林欣,男,副教授,研究方向为时空数据库和数据清洗.E-mail:xlin@cs.ecnu.edu.cn. E-mail:xlin@cs.ecnu.edu.cn
作者简介:王桢,男,硕士研究生,研究方向为数据清洗.E-mail:zhenwangemail@163.com.
基金资助:
国家自然科学基金（61572193）

Data cleaning on probabilistic RDF database

WANG Zhen, LIN Xin

Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200062, China

Received:2016-12-03 Online:2018-01-25 Published:2018-01-11

摘要/Abstract

摘要： 由于在获取、解析数据的过程中存在误差、干扰等因素，很多领域的数据中存在着不确定性，这已成为影响数据性能的重要因素.概率数据库可以存储不确定数据并且返回带有置信度的查询结果.然而，不确定性的累积和传播会降低查询结果的可用性.因此，有必要降低概率数据库中数据的不确定性.致力于解决在概率RDF （Resource Description Framework）数据库图查询中如何由众包来提升查询结果的确定性，基本思想是让众包工作者决定由边表示的关系是否正确，以降低整个查询的不确定性.提出了3种不同的算法来选择使查询结果不确定性下降最大的边.最后，通过实验验证了提出的算法，表明不稳定剪枝算法和稳定剪枝算法具有更好的效果.

关键词: 概率RDF图, 众包, 数据清洗

Abstract: Due to the factors such as errors and noises in the process of obtaining and analyzing data, uncertain data arises in many domains, which has emerged as an important issue affecting the performance of data. Uncertain data can be stored in probabilistic databases and query facilities always yield answers with confidence. However, the accumulation and propagation of uncertainty may reduce the usability of the query results. As such, it is desirable to reduce the uncertainty of uncertain data. This paper aims at solving the problem how to promote the answers' certainty in RDF(resource description framework) graph query via crowdsourcing. The basic idea is to ask the crowd to decide whether the relationships represented by some edges are correct. In this paper, we introduce three different algorithms to select the edge which maximizes the uncertainty reduction. Finally, we verify these algorithms by experiments and show that unstable pruning algorithm and stable pruning algorithm perform better in term of efficiency.

Key words: probabilistic RDF graph, crowdsourcing, data cleaning

中图分类号:

TP392

王桢, 林欣. 面向概率RDF数据库查询的数据清洗[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 76-90.

WANG Zhen, LIN Xin. Data cleaning on probabilistic RDF database[J]. Journal of East China Normal University(Natural Sc, 2018, 2018(1): 76-90.

参考文献

[1] DALVI N, SUCIU D. Efficient query evaluation on probabilistic databases[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2007, 16(4):523-544.
[2] ABITEBOUL S, SENELLART P. Querying and updating probabilistic information in XML[C]//Advances in Database Technology-EDBT 2006, International Conference on Extending Database Technology. DBLP, 2006:1059-1068.
[3] DONG X, GABRILOVICH E, HEITZ G, et al. Knowledge vault:A web-scale approach to probabilistic knowledge fusion[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:601-610.
[4] ANGLES R, GUTIERREZ C. Querying RDF data from a graph database perspective[C]//European Semantic Web Conference. Berlin:Springer, 2005:346-360.
[5] FANG H, ZHANG X W. pSPARQL:A querying language for probabilistic RDF[C/OL]//Proceedings of the ISWC 2016 Posters & Demonstrations Track Co-Located with 15th International Semantic Web Conference, ISWC 2016.[2016-08-01]. http://ceur-ws.org/Vol-1690/paper18.pdf.
[6] FUKUSHIGE Y. Representing probabilistic relations in RDF[C/OL]//Proceedings of the International Semantic Web Conference, ISWC 2005.[2016-08-01]. http://ceur-ws.org/Vol-173/pospaper5.pdf.
[7] LIAN X, CHEN L. Efficient query answering in probabilistic rdf graphs[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, 2011:157-168.
[8] HUANG H, LIU C F. Query evaluation on probabilistic RDF databases[C]//International Conference on Web Information Systems Engineering. Berlin:Springer, 2009:307-320.
[9] UDREA O, SUBRAHMANIAN V S, MAJKIC Z. Probabilistic RDF[C]//Information Reuse and Integration, 2006 IEEE International Conference on. IEEE, 2006:172-177.
[10] ZHANG C J, CHEN L, JAGADISH H V, et al. Reducing uncertainty of schema matching via crowdsourcing[J]. Proceedings of the VLDB Endowment, 2013, 6(9):757-768.
[11] CHENG R, CHEN J C, XIE X K. Cleaning uncertain data with quality guarantees[J]. Proceedings of the VLDB Endowment, 2008(1):722-735.
[12] LEE J, LEE D, HWANG S. CrowdK:Answering top-k queries with crowdsourcing[J]. Information Sciences, 2017, 399:98-120.
[13] CICERI E, FRATERNALI P, MARTINENGHI D, et al. Crowdsourcing for top-k query processing over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1):41-53.
[14] VERROIOS V, GARCIA-MOLINA H. Entity resolution with crowd errors[C]//2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015:219-230.
[15] ZHANG C J, CHEN L, TONG Y, et al. Cleaning uncertain data with a noisy crowd[C]//2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015:6-17.
[16] MARCUS A, WU E, KARGER D, et al. Human-powered sorts and joins[J]. Proceedings of the VLDB Endowment, 2011, 5(1):13-24.
[17] MARCUS A, WU E, KARGER D R, et al. Crowdsourced databases:Query processing with people[C/OL]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research, CIDR 2011.[1016-08-01]. http://www-db.cs.wisc.edu/cidr/cidr2011/Papers/CIDR11Paper29.pdf.
[18] SUCHANEK F M, KASNECI G, WEIKUM G. Yago:a core of semantic knowledge[C]//Proceedings of the 16th International Conference on World Wide Web. ACM, 2007:697-706.

面向概率RDF数据库查询的数据清洗

Data cleaning on probabilistic RDF database

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	孙家博, 蔡鹏. 日志结构合并树的查询优化技术[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 94-103.
[2]	刘文欣, 蔡鹏. 多主数据库中基于分区的并发控制[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 84-93.
[3]	项兆坤, 陈婷, 苏仟, 张蓉. 面向OLAP数据库查询处理功能的模糊测试工具[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 74-83.
[4]	余阳, 胡卉芪, 周煊. 基于非易失性内存的LSM-tree存储系统优化[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 37-47.
[5]	方创新, 宋浩, 林煜明, 周娅. CPU-GPU异构环境下的大规模商品知识查询处理[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 157-168.
[6]	丁国浩, 徐辰, 钱卫宁. 面向日志结构化数据存储的高效数据加载[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 143-158.
[7]	祝朝凡, 郭进伟, 蔡鹏. 基于Paxos的分布式一致性算法的实现与优化[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 168-177.
[8]	涂云山, 储佳佳, 张耀, 翁楚良. 面向新硬件的数据处理软件技术[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 30-40,78.
[9]	徐石磊, 魏星, 江红, 钱卫宁, 周傲英. 分布式数据库系统中的并行分组聚合实现[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 56-66.
[10]	俞文谦, 胡爽, 胡卉芪. 面向Cedar的列存储设计与实现[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 67-78.
[11]	黄建伟, 张召, 钱卫宁. 分布式日志结构数据库系统的主键维护方法研究[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 79-90,119.
[12]	赵春扬, 肖冰, 郭进伟, 钱卫宁. 一致性协议在分布式数据库系统中的应用[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 91-106.
[13]	贺小龙, 马海欣, 何毓锟, 庞天泽, 赵琼. 新型OLTP系统的技术与实践[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 107-119.
[14]	徐石磊, 王雷, 胡卉芪, 钱卫宁, 周傲英. 基于分布式系统OceanBase的并行连接[J]. 华东师范大学学报(自然科学版), 2017, 2017(5): 1-10.
[15]	许建秋，黄火荣. 移动对象运动方式隐私保护[J]. 华东师范大学学报(自然科学版), 2015, 2015(5): 77-87.