Projects per year
Abstract / Description of output
Numeric inconsistencies are common in real-life knowledge bases and social networks. To catch such errors, we propose to extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. We study fundamental problems for NGDs. We show that their satisfiability, implication and validation problems are Σp2 -complete, Πp2 -complete and coNP-complete, respectively. However, if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. In other words, NGDs strike a balance between expressivity and complexity.
To make practical use of NGDs, we develop an incremental algorithm IncDect to detect errors in a graph G using NGDs, in response to updates ∆G to G. We show that the incremental validation problem is coNP-complete. Nonetheless, algorithm IncDect is localizable, i.e., its cost is determined by small neighbors of nodes in ∆G instead of the entire G. Moreover, we parallelize IncDect such that it guarantees to reduce running time with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the algorithms.
To make practical use of NGDs, we develop an incremental algorithm IncDect to detect errors in a graph G using NGDs, in response to updates ∆G to G. We show that the incremental validation problem is coNP-complete. Nonetheless, algorithm IncDect is localizable, i.e., its cost is determined by small neighbors of nodes in ∆G instead of the entire G. Moreover, we parallelize IncDect such that it guarantees to reduce running time with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the algorithms.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2018 International Conference on Management of Data (SIGMOD'18) |
Place of Publication | Texas, USA |
Publisher | ACM |
Pages | 381-393 |
Number of pages | 13 |
ISBN (Electronic) | 978-1-4503-4703-7 |
DOIs | |
Publication status | Published - 27 May 2018 |
Event | 2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States Duration: 10 Jun 2018 → 15 Jun 2018 https://sigmod2018.org/ |
Conference
Conference | 2018 ACM SIGMOD/PODS International Conference on Management of Data |
---|---|
Abbreviated title | SIGMOD'18 |
Country/Territory | United States |
City | Houston |
Period | 10/06/18 → 15/06/18 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- numeric errors
- graph dependencies
- incremental validation
Fingerprint
Dive into the research topics of 'Catching Numeric Inconsistencies in Graphs'. Together they form a unique fingerprint.Projects
- 2 Finished
-
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research