{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T14:21:02Z","timestamp":1776090062984,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>Data accuracy is a central dimension of data quality, especially when dealing with Knowledge Graphs (KGs). Auditing the accuracy of KGs is essential to make informed decisions in entity-oriented services or applications. However, manually evaluating the accuracy of large-scale KGs is prohibitively expensive, and research is focused on developing efficient sampling techniques for estimating KG accuracy. This work addresses the limitations of current KG accuracy estimation methods, which rely on the Wald method to build confidence intervals, addressing reliability issues such as zero-width and overshooting intervals. Our solution, rooted in the Wilson method and tailored for complex sampling designs, overcomes these limitations and ensures applicability across various evaluation scenarios. We show that the presented methods increase the reliability of accuracy estimates by up to two times when compared to the state-of-the-art while preserving or enhancing efficiency. Additionally, this consistency holds regardless of the KG size or topology.<\/jats:p>","DOI":"10.14778\/3665844.3665865","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:07Z","timestamp":1722982747000},"page":"2392-2403","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Efficient and Reliable Estimation of Knowledge Graph Accuracy"],"prefix":"10.14778","volume":"17","author":[{"given":"Stefano","family":"Marchesin","sequence":"first","affiliation":[{"name":"University of Padua, Padua, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianmaria","family":"Silvello","sequence":"additional","affiliation":[{"name":"University of Padua, Padua, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.1998.10480550"},{"key":"e_1_2_1_2_1","volume-title":"6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007","volume":"4825","author":"Auer S.","year":"2007","unstructured":"S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, and Z. G. Ives. 2007. DBpedia: A Nucleus for a Web of Open Data. In The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007, Busan, Korea, November 11--15, 2007 (LNCS), Vol. 4825. Springer, 722--735. 10.1007\/978-3-540-76298-0_52"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"A. Bonifati G. H. L. Fletcher H. Voigt and N. Yakovets. 2018. Querying Graphs. Morgan & Claypool Publishers. 10.2200\/S00873ED1V01Y201808DTM051","DOI":"10.2200\/S00873ED1V01Y201808DTM051"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1214\/ss\/1009213286","article-title":"Interval Estimation for a Binomial Proportion","volume":"16","author":"Brown L. D.","year":"2001","unstructured":"L. D. Brown, T. T. Cai, and A. DasGupta. 2001. Interval Estimation for a Binomial Proportion. Statist. Sci. 16, 2 (2001), 101--117. http:\/\/www.jstor.org\/stable\/2676784","journal-title":"Statist. Sci."},{"key":"e_1_2_1_5_1","unstructured":"G. Casella and R. L. Berger. 2002. Statistical Inference. Thomson Learning. https:\/\/books.google.it\/books?id=0x_vAAAAMAAJ"},{"key":"e_1_2_1_6_1","volume-title":"Proc. of the 2016 International Conference on Management of Data, SIGMOD Conference 2016","author":"Chu X.","year":"2016","unstructured":"X. Chu, I. F. Ilyas, S. Krishnan, and J. Wang. 2016. Data Cleaning: Overview and Emerging Challenges. In Proc. of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016. ACM, 2201--2206. 10.1145\/2882903.2912574"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091500025724"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1959.10501501"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/jssam\/smv024"},{"key":"e_1_2_1_10_1","volume-title":"Proc. of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013","author":"Deshpande O.","year":"2013","unstructured":"O. Deshpande, D. S. Lamba, M. Tourn, S. Das, S. Subramaniam, A. Rajaraman, V. Harinarayan, and A. Doan. 2013. Building, maintaining, and using knowledge bases: a report from the trenches. In Proc. of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22--27, 2013. ACM, 1209--1220. 10.1145\/2463676.2465297"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177873"},{"key":"e_1_2_1_12_1","volume-title":"Statistical Methods for Research Workers","author":"Fisher R. A.","unstructured":"R. A. Fisher. 1954. Statistical Methods for Research Workers, 12th Edition. Edinburgh Oliver & Boyd.","edition":"12"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342642"},{"key":"e_1_2_1_14_1","volume-title":"Efficiently Answering Durability Prediction Queries. In SIGMOD '21: International Conference on Management of Data","author":"Gao J.","year":"2021","unstructured":"J. Gao, Y. Xu, P. K. Agarwal, and J. Yang. 2021. Efficiently Answering Durability Prediction Queries. In SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20--25, 2021. ACM, 591--604. 10.1145\/3448016.3457305"},{"key":"e_1_2_1_15_1","volume-title":"Proc. of the 1st Conference on Automated Knowledge Base Construction, AKBC 2019","author":"Gashteovski K.","year":"2019","unstructured":"K. Gashteovski, S. Wanner, S. Hertling, S. Broscheit, and R. Gemulla. 2019. OPIEC: An Open Information Extraction Corpus. In Proc. of the 1st Conference on Automated Knowledge Base Construction, AKBC 2019, Amherst, MA, USA, May 20--22, 2019. 10.24432\/C53W2J"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"e_1_2_1_17_1","unstructured":"R. V. Hogg E. A. Tanis and D. L. Zimmerman. 2013. Probability and Statistical Inference. Pearson. https:\/\/books.google.it\/books?id=I_7tnQEACAAJ"},{"key":"e_1_2_1_18_1","volume-title":"Growing and Serving Large Open-domain Knowledge Graphs. In Companion of the 2023 International Conference on Management of Data, SIGMOD\/PODS 2023","author":"Ilyas I. F.","year":"2023","unstructured":"I. F. Ilyas, J. Lacerda, Y. Li, U. F. Minhas, A. Mousavi, J. Pound, T. Rekatsinas, and C. Sumanth. 2023. Growing and Serving Large Open-domain Knowledge Graphs. In Companion of the 2023 International Conference on Management of Data, SIGMOD\/PODS 2023, Seattle, WA, USA, June 18--23, 2023. ACM, 253--259. 10.1145\/3555041.3589672"},{"key":"e_1_2_1_19_1","volume-title":"SIGMOD '22: International Conference on Management of Data","author":"Ilyas I. F.","year":"2022","unstructured":"I. F. Ilyas, T. Rekatsinas, V. Konda, J. Pound, X. Qi, and M. A. Soliman. 2022. Saga: A Platform for Continuous Construction and Serving of Knowledge at Scale. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022. ACM, 2259--2272. 10.1145\/3514221.3526049"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"210","DOI":"10.2307\/2345081","article-title":"Ultimate Cluster Sampling. Journal of the Royal Statistical Society","volume":"142","author":"Kalton G.","year":"1979","unstructured":"G. Kalton. 1979. Ultimate Cluster Sampling. Journal of the Royal Statistical Society. Series A (General) 142, 2 (1979), 210--222. http:\/\/www.jstor.org\/stable\/2345081","journal-title":"Series A (General)"},{"key":"e_1_2_1_21_1","unstructured":"L. Kish. 1965. Survey Sampling. Wiley. https:\/\/books.google.it\/books?id=xiZmAAAAIAAJ"},{"key":"e_1_2_1_22_1","first-page":"55","article-title":"Methods for Design Effects","volume":"11","author":"Kish L.","year":"1995","unstructured":"L. Kish. 1995. Methods for Design Effects. J. Off. Stat. 11, 1 (1995), 55. https:\/\/www.scb.se\/contentassets\/ca21efb41fee47d293bbee5bf7be7fb3\/methods-for-design-effects.pdf","journal-title":"J. Off. Stat."},{"key":"e_1_2_1_23_1","first-page":"193","article-title":"Confidence Intervals for Proportions with Small Expected Number of Positive Counts Estimated from Survey Data","volume":"24","author":"Korn E. L.","year":"1998","unstructured":"E. L. Korn and B. I. Graubard. 1998. Confidence Intervals for Proportions with Small Expected Number of Positive Counts Estimated from Survey Data. Survey Methodology 24 (1998), 193--201. https:\/\/www150.statcan.gc.ca\/n1\/pub\/12-001-x\/1998002\/article\/4356-eng.pdf","journal-title":"Survey Methodology"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137646"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897350.2897352"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137642"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3191513"},{"key":"e_1_2_1_28_1","first-page":"2","volume-title":"Proc. ACM Manag. Data 1","author":"Mohoney J.","year":"2023","unstructured":"J. Mohoney, A. Pacaci, S. R. Chowdhury, A. Mousavi, I. F. Ilyas, U. F.q Minhas, J. Pound, and T. Rekatsinas. 2023. High-Throughput Vector Similarity Search in Knowledge Graphs. Proc. ACM Manag. Data 1, 2 (2023), 197:1--197:25. 10.1145\/3589777"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0258(19980430)17:8"},{"key":"e_1_2_1_30_1","first-page":"17","volume-title":"Proc. of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017","author":"Ojha P.","year":"2017","unstructured":"P. Ojha and P. P. Talukdar. 2017. KGEval: Accuracy Estimation of Automatically Constructed Knowledge Graphs. In Proc. of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9--11, 2017. ACL, 1741--1750. 10.18653\/v1\/d17-1183"},{"key":"e_1_2_1_31_1","first-page":"17","volume-title":"Proc. of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017","author":"Pujara J.","year":"2017","unstructured":"J. Pujara, E. Augustine, and L. Getoor. 2017. Sparsity and Noise: Where Knowledge Graph Embeddings Fall Short. In Proc. of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9--11, 2017. ACL, 1751--1756. 10.18653\/v1\/d17-1184"},{"key":"e_1_2_1_32_1","volume-title":"KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Qi Y.","year":"2022","unstructured":"Y. Qi, W. Zheng, L. Hong, and L. Zou. 2022. Evaluating Knowledge Graph Accuracy Powered by Optimized Human-Machine Collaboration. In KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022. ACM, 1368--1378. 10.1145\/3534678.3539233"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"N. Queralt-Rosinach J. Pi\u00f1ero Gonz\u00e1lez \u00c0. Bravo F. Sanz and L. I. Furlong. 2016. DisGeNET-RDF: harnessing the innovative power of the Semantic Web to explore the genetic basis of diseases. Bioinformatics 32 14 (03 2016) 2236--2238. 10.1093\/bioinformatics\/btw214","DOI":"10.1093\/bioinformatics\/btw214"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000063"},{"key":"e_1_2_1_35_1","volume-title":"Proc. of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015","author":"Samadi M.","year":"2015","unstructured":"M. Samadi, P. P. Talukdar, M. M. Veloso, and T. M. Mitchell. 2015. AskWorld: Budget-Sensitive Query Evaluation for Knowledge-on-Demand. In Proc. of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25--31, 2015. AAAI Press, 837--843. http:\/\/ijcai.org\/Abstract\/15\/123"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/sim.4780120902"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/09296174.2013.799918"},{"key":"e_1_2_1_39_1","volume-title":"International Conference on Management of Data, SIGMOD 2014","author":"Wang J.","year":"2014","unstructured":"J. Wang, S. Krishnan, M. J. Franklin, K. Goldberg, T. Kraska, and T. Milo. 2014. A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data. In International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22--27, 2014. ACM, 469--480. 10.1145\/2588555.2610505"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.fmre.2021.09.003"},{"key":"e_1_2_1_41_1","volume-title":"Aggregate Queries on Knowledge Graphs: Fast Approximation with Semantic-aware Sampling. In 38th IEEE International Conference on Data Engineering, ICDE 2022","author":"Wang Y.","year":"2022","unstructured":"Y. Wang, A. Khan, X. Xu, J. Jin, Q. Hong, and T. Fu. 2022. Aggregate Queries on Knowledge Graphs: Fast Approximation with Semantic-aware Sampling. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9--12, 2022. IEEE, 2914--2927. 10.1109\/ICDE53745.2022.00263"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1927.10502953"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-150175"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3665844.3665865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:22:30Z","timestamp":1722982950000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3665844.3665865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":43,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["10.14778\/3665844.3665865"],"URL":"https:\/\/doi.org\/10.14778\/3665844.3665865","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,5]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}