Edinburgh Research Explorer

Catching Numeric Inconsistencies in Graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://dl.acm.org/citation.cfm?id=3183753
Original languageEnglish
Title of host publicationProceedings of the 2018 International Conference on Management of Data (SIGMOD'18)
Place of PublicationTexas, USA
PublisherACM
Pages381-393
Number of pages13
ISBN (Electronic)978-1-4503-4703-7
DOIs
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Conference

Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Abstract

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.

    Research areas

  • numeric errors, graph dependencies, incremental validation

Event

2018 ACM SIGMOD/PODS International Conference on Management of Data

10/06/1815/06/18

Houston, United States

Event: Conference

Download statistics

No data available

ID: 64279860