Sun J, Li J, Gao H, et al. Truth Discovery on Inconsistent Relational Data. Tsinghua Science and Technology, 2018, 23(3): 288-302. https://doi.org/10.26599/TST.2018.9010004
In this era of big data, data are often collected from multiple sources that have different reliabilities, and there is inevitable conflict with respect to the various information obtained when it relates to the the same object. One important task is to identify the most trustworthy value out of all the conflicting claims, and this is known as truth discovery. Existing truth discovery methods simultaneously identify the most trustworthy information and source reliability degrees and are based on the idea that more reliable sources often provide more trustworthy information, and vice versa. However, there are often semantic constrains defined upon relational database, which can be violated by a single data source. To remove violations, an important task is to repair data to satisfy the constrains, and this is known as data cleaning. The two problems above may coexist, but considering them together can provide some benefits, and to the authors knowledge, this has not yet been the focus of any research. In this paper, therefore, a schema-decomposing based method is proposed to simultaneously discover the truth and to clean the data, with the aim of improving accuracy. Experimental results using real world data sets of notebooks and mobile phones, as well as simulated data sets, demonstrate the effectiveness and efficiency of our proposed method.
School of Computer Science and Technology, Harbin Institute of Technology, Harbin150001, China.
Abstract
In this era of big data, data are often collected from multiple sources that have different reliabilities, and there is inevitable conflict with respect to the various information obtained when it relates to the the same object. One important task is to identify the most trustworthy value out of all the conflicting claims, and this is known as truth discovery. Existing truth discovery methods simultaneously identify the most trustworthy information and source reliability degrees and are based on the idea that more reliable sources often provide more trustworthy information, and vice versa. However, there are often semantic constrains defined upon relational database, which can be violated by a single data source. To remove violations, an important task is to repair data to satisfy the constrains, and this is known as data cleaning. The two problems above may coexist, but considering them together can provide some benefits, and to the authors knowledge, this has not yet been the focus of any research. In this paper, therefore, a schema-decomposing based method is proposed to simultaneously discover the truth and to clean the data, with the aim of improving accuracy. Experimental results using real world data sets of notebooks and mobile phones, as well as simulated data sets, demonstrate the effectiveness and efficiency of our proposed method.
Keywords:truth discovery, inconsistent data, data cleaning
References(52)
[1]
FanW. and GeertsF., Cleaning data with conditional dependencies, in Foundations of Data Quality Management, ÖzsuM. T., ed. San Rafael, CA, USA: Morgan & Claypool Publishers, 2012, pp. 39–86.
[2]
Li X., Dong X. L., Lyons K., Meng W., and Srivastava D., Truth finding on the deep web: Is the problem solved? in Proc. 39th Int. Conf. Very Large Data Bases, Riva del Garda, Italy, 2013, pp. 97–108.
Dong X. L., Equille L. B., and Srivastava D., Data fusion: Resolving conflicts from multiple sources, in Handbook of Data Quality, Sadiq S., ed. Springer, 2013, pp. 293–318.
Yin X., Han J., and Yu P. S., Truth discovery with multiple conflicting information providers on the web, in Proc. 13th Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 1048–1052.
Dong X. L., Equille L. B., and Srivastava D., Integrating conflicting data: The role of source dependence, in Proc. 35th Int. Conf. Very Large Data Bases, Lyon, France, 2009, pp. 550–561.
Galland A., Abiteboul S., Marian A., and Senellart P., Corroborating information from disagreeing views, in Proc. 3rd Int. Conf. Web Search and Web Data Mining, New York, NY, USA, 2010, pp. 131–140.
Pasternack J. and Roth D., Knowing what to believe (when you already know something), in Proc. 23rd Int. Conf. Computational Linguistics, Beijing, China, 2010, pp. 877–885.
[8]
Yin X. and Tan W., Semi-supervised truth discovery, in Proc. 20th Int. World Wide Web Conf., Hyderabad, India, 2011, pp. 217–226.
Zhao B., Rubinstein B. I. P., Gemmell J., and Han J., A Bayesian approach to discovering truth from conflicting sources for data integration, in Proc. 38th Int. Conf. Very Large Data Bases, Istanbul, Turkey, 2012, pp. 550–561.
Zhao B. and Han J., A probabilistic model for estimating real-valued truth from conflicting sources, presented at the 10th Int. Workshop on Quality in Databases, Istanbul, Turkey, 2012.
[11]
Wang D., Kaplan L., Le H., and Abdelzaher T., On truth discovery in social sensing: A maximum likelihood estimation approach, in Proc. 11th Int. Conf. Information Processing in Sensor Networks, Beijing, China, 2012, pp. 233–244.
Li Q., Li Y., Gao J., Zhao B., Fan W., and Han J., Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation, in Proc. Int. Conf. Management of Data, Snowbird, UT, USA, 2014, pp. 1187–1198.
Li Q., Li Y., Gao J., Su L., Zhao B., Demirbas M., Fan W., and Han J., A confidence-aware approach for truth discovery on long-tail data, in Proc. 41st Int. Conf. Very Large Data Bases, Kohala Coast, HI, USA, 2015, pp. 425–436.
Code E. F., Relational completeness of data base sublanguages, in Data Base Systems, Courant Computer Science Symposia 6, Rustin R., ed. Upper Saddle River, NJ, USA: Prentice Hall, 1972, pp. 65–98.
[16]
Bohannon P., Fan W., Geerts F., Jia X., and Kementsietsidis A., Conditional functional dependencies for data cleaning, in Proc. 23rd Int. Conf. Data Engineering, Istanbul, Turkey, 2007, pp. 746–755.
Fan W., Geerts F., Jia X., and Kementsietsidis A., Conditional functional dependencies for capturing data inconsistencies, ACM Trans. Database Syst., vol. 33, no. 6, pp. 1–48, 2008.
Fan W., Li J., Tang N., and Yu W., Incremental detection of inconsistencies in distributed data, IEEE Trans. Knowl. Data Eng., vol. 26, no. 6, pp. 1367–1383, 2014.
Bohannon P., Fan W., Flaster M., and Rastogi R., A cost-based model and effective heuristic for repairing constraints by value modification, in Proc. Int. Conf. Management of Data, Baltimore, MD, USA, 2005, pp. 143–154.
Kolahi S. and Lakshmanan L. V. S., On approximating optimum repairs for functional dependency violations, in Proc. 12th Int. Conf. Database Theory, St. Petersburg, Russia, 2009, pp. 53–62.
Beskales G., Ilyas I. F., and Golab L., Sampling the repairs of functional dependency violations under hard constraints, in Proc. 36th Int. Conf. Very Large Data Bases, Singapore, 2010, pp. 197–207.
Beskales G., Ilyas I. F., Golab L., and Galiullin A., Sampling from repairs of conditional functional dependency violations, VLDB J., vol. 23, no. 1, pp. 103–128, 2014.
Bravo L., Fan W., Geerts F., and Ma S., Increasing the expressivity of conditional functional dependencies without extra complexity, in Proc. 24th Int. Conf. Data Engineering, Cancún, México, 2008, pp. 516–525.
Chen W., Fan W., and Ma S., Analyses and validation of conditional dependencies with built-in predicates, in Proc. 20th Int. Conf. Database and Expert Systems Applications, Linz, Austria, 2009, pp. 576–591.
Wang J. and Tang N., Towards dependable data repairing with fixing rules, in Proc. Int. Conf. Management of Data, Snowbird, UT, USA, 2014, pp. 457–468.
Qiu D., Barbosa L., Dong X. L., Shen Y., and Srivastava D., DEXTER: Large-scale discovery and extraction of product specifications on the web, in Proc. 41st Int. Conf. Very Large Data Bases, Kohala Coast, HI, USA, 2015, pp. 2194–2205.
Yakout M., Elmagarmid A. K., Neville J., and Ouzzani M., GDR: A system for guided data repair, in Proc. Int. Conf. Management of Data, Indianapolis, IN, USA, 2010, pp. 1223–1226.
Yakout M., Elmagarmid A. K., Neville J., Ouzzani M., and Ilyas I. F., Guided data repair, in Proc. 37th Int. Conf. Very Large Data Bases, 2011, pp. 279–289.
Xie H., Wang H., Li J., and Gao H., A data cleaning framework based on user feedback, in Proc. 14th Int. Conf. Web-Age Information Management, Beidaihe, China, 2013, pp. 514–520.
He J., Veltri E., Santoro D., Li G., Mecca G., Papotti P., and Tang N., Interactive and deterministic data cleaning, in Proc. Int. Conf. Management of Data, San Francisco, CA, USA, 2016, pp. 893–907.
Cai Z., He Z., Guan X., and Li Y., Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Trans. Depend. Secure., .
He Z., Cai Z., Sun Y., Li Y., and Cheng X., Customized privacy preserving for inherent-data and latent-data, Pers. Ubiquit. Comput., vol. 21, no. 1, pp. 43–54, 2017.
Miao D., Cai Z., Liu X., and Li J., On the complexity of insertion propagation with functional dependency constraints, in Proc. 22nd Int. Conf. Computing and Combinatorics, Ho Chi Minh City, Vietnam, 2016, pp. 623–632.
Cai Z., Heydari M., and Lin G., Iterated local least squares microarray missing value imputation, J. Bioinf. Comput. Biol., vol. 4, no. 4, pp. 935–958, 2006.
Chu X., Ilyas I. F., Krishnan S., and Wang J., Data cleaning: Overview and emerging challenges, in Proc. Int. Conf. Management of Data, San Francisco, CA, USA, 2016, pp. 2201–2206.
Pasternack J. and Roth D., Making better informed trust decisions with generalized fact-finding, in Proc. 22nd Int. Joint Conf. Artificial Intelligence, Barcelona, Spain, 2011, pp. 2324–2329.
Wang D., Abdelzaher T. F., Ahmadi H., Pasternack J., Roth D., Gupta M., Han J., Fatemieh O., Le H. K., and Aggarwal C. C., On bayesian interpretation of fact-finding in information networks, in Proc. 14th Int. Conf. Information Fusion, Chicago, IL, USA, 2011, pp. 1–8.
[47]
Wang X., Sheng Q. Z., Fang X. S., Yao L., Xu X., and Li X., An integrated bayesian approach for effective multi-truth discovery, in Proc. 24th Int. Conf. Information and Knowledge Management, Melbourne, Australia, 2015, pp. 493–502.
Blanco L., Crescenzi V., Merialdo P., and Papotti P., Probabilistic models to reconcile complex data from inaccurate data sources, in Proc. 22nd Int. Conf. Advanced Information Systems Engineering, Hammamet, Tunisia, 2010, pp. 83–97.
Qi G., Aggarwal C. C., Han J., and Huang T. S., Mining collective intelligence in diverse groups, in Proc. 22nd Int. World Wide Web Conf., Rio de Janeiro, Brazil, 2013, pp. 1041–1052.
Dong X. L., Saha B., and Srivastava D., Less is more: Selecting sources wisely for integration, in Proc. 38th Int. Conf. Very Large Data Bases, Istanbul, Turkey, 2012, pp. 37–48.
Rekatsinas T., Dong X. L., and Srivastava D., Characterizing and selecting fresh data sources, in Proc. Int. Conf. Management of Data, Snowbird, UT, USA, 2014, pp. 919–930.
Silberschatz A., Korth H. F., Sudarshan S., Functional-dependency theory, in Database System Concepts Six Edition, Bilecki M. D., ed. New York, NY, USA: McGraw-Hill, 1997, pp. 338–348.
This paper was partially supported by the Key Research and Development Plan of National Ministry of Science and Technology (No. 2016YFB1000703), the Key Program of the National Natural Science Foundation of China (Nos. 61190115, 61472099, 61632010, and U1509216), National Sci-Tech Support Plan (No. 2015BAH10F01), the Scientific Research Foundation for the Returned Overseas Chinese Scholars of Heilongjiang Province (No. LC2016026), and MOE-Microsoft Key Laboratory of Natural Language Processing and Speech, Harbin Institute of Technology.
Open Access
Issue
Published:
02 July 2018
),
Download citation
FEEDBACK 
TOP