Possibilistic Data Cleaning.
Saved in:
| Title: | Possibilistic Data Cleaning. |
|---|---|
| Authors: | Koehler, Henning1 H.Koehler@massey.ac.nz, Link, Sebastian2 s.link@auckland.ac.nz |
| Source: | IEEE Transactions on Knowledge & Data Engineering. Dec2022, Vol. 34 Issue 12, p5939-5950. 12p. |
| Subjects: | Data scrubbing, Relational databases |
| Abstract: | Classical data cleaning performs a minimal set of operations on the data to satisfy the given integrity constraints. Often, this minimization is equivalent to vertex cover, for example when tuples can be removed due to the violation of functional dependencies. Classically, the uncertainty of tuples and constraints is ignored. We propose not to view data as dirty but the uncertainty information about data. Since probabilities are often unavailable and their treatment is limited due to correlations in the data, we investigate a qualitative approach to uncertainty. Tuples are assigned degrees of possibility with which they occur, and constraints are assigned degrees of certainty that say to which tuples they apply. Our approach is non-invasive to the data as we lower the possibility degree of tuples as little as possible. The new resulting qualitative version of vertex cover remains NP-hard. We establish an algorithm that is fixed-parameter tractable in the size of the qualitative vertex cover. Experiments with synthetic and real-world data show that our algorithm outperforms the classical algorithm proportionally to the available number of uncertainty degrees. By mining the certainty degrees with which constraints hold, our framework becomes applicable even when uncertainty information is unavailable. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Knowledge & Data Engineering is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 160692086 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Possibilistic Data Cleaning. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Koehler%2C+Henning%22">Koehler, Henning</searchLink><relatesTo>1</relatesTo><i> H.Koehler@massey.ac.nz</i><br /><searchLink fieldCode="AR" term="%22Link%2C+Sebastian%22">Link, Sebastian</searchLink><relatesTo>2</relatesTo><i> s.link@auckland.ac.nz</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Knowledge+%26+Data+Engineering%22">IEEE Transactions on Knowledge & Data Engineering</searchLink>. Dec2022, Vol. 34 Issue 12, p5939-5950. 12p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Data+scrubbing%22">Data scrubbing</searchLink><br /><searchLink fieldCode="DE" term="%22Relational+databases%22">Relational databases</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Classical data cleaning performs a minimal set of operations on the data to satisfy the given integrity constraints. Often, this minimization is equivalent to vertex cover, for example when tuples can be removed due to the violation of functional dependencies. Classically, the uncertainty of tuples and constraints is ignored. We propose not to view data as dirty but the uncertainty information about data. Since probabilities are often unavailable and their treatment is limited due to correlations in the data, we investigate a qualitative approach to uncertainty. Tuples are assigned degrees of possibility with which they occur, and constraints are assigned degrees of certainty that say to which tuples they apply. Our approach is non-invasive to the data as we lower the possibility degree of tuples as little as possible. The new resulting qualitative version of vertex cover remains NP-hard. We establish an algorithm that is fixed-parameter tractable in the size of the qualitative vertex cover. Experiments with synthetic and real-world data show that our algorithm outperforms the classical algorithm proportionally to the available number of uncertainty degrees. By mining the certainty degrees with which constraints hold, our framework becomes applicable even when uncertainty information is unavailable. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Knowledge & Data Engineering is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=160692086 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TKDE.2021.3062318 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 12 StartPage: 5939 Subjects: – SubjectFull: Data scrubbing Type: general – SubjectFull: Relational databases Type: general Titles: – TitleFull: Possibilistic Data Cleaning. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Koehler, Henning – PersonEntity: Name: NameFull: Link, Sebastian IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2022 Type: published Y: 2022 Identifiers: – Type: issn-print Value: 10414347 Numbering: – Type: volume Value: 34 – Type: issue Value: 12 Titles: – TitleFull: IEEE Transactions on Knowledge & Data Engineering Type: main |
| ResultId | 1 |
