Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Conference or Workshop Paper |
| Scope | Discipline-based scholarship |
| Published in Proceedings | Yes |
| Title | Discovery of Band Order Dependencies |
| Organization Unit | |
| Authors |
|
| Presentation Type | paper |
| Item Subtype | Original Work |
| Refereed | Yes |
| Status | Published in final form |
| Language |
|
| Event Title | ICDE 2020 |
| Event Type | conference |
| Event Location | Dallas |
| Event Start Date | April 1 - 2020 |
| Event End Date | April 3 - 2020 |
| Publisher | arXiv |
| Abstract Text | We introduce band ODs to model the semantics ofattributes that are monotonically related with small variationswithout there being an intrinsic violation of semantics. Tomake band ODs relevant to real-world applications, we makethem less strict to holdapproximatelywith some exceptions andconditionallyon subsets of the data with a mix of ascendingand descending directions. Formulating integrity constraintsmanually requires domain expertise, is prone to human errors,and time consuming. Thus, we study the problem of automaticabcOD discovery. We propose an algorithm that utilizes thenotion of a longest monotonic band (LMB) to identify longestsubsequences of tuples that satisfy a band OD. We formulate theabcOD discovery problem as a constraint optimization problem,and devise a dynamic programming algorithm that determinesthe optimal solution in polynomial time (super-cubic complexity).To further optimize the performance over large datasets, weadapt the algorithm to consider pieces (contiguous sequencesof tuples) in a greedy fashion. This improves the performanceby orders-of-magnitude without sacrificing precision in practice.We show that for unidirectional abcODs, with only ascending ordescending orderings, our pieces-based algorithm is guaranteedto find the optimal solution. Finally, we perform a thoroughexperimental evaluation of our techniques over real-world andsynthetic datasets. |
| Official URL | https://arxiv.org/abs/1905.11948 |
| PubMed ID | https://arxiv.org/abs/1905.11948 |
| Other Identification Number | merlin-id:18932 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|