Approximate Order Dependency Discovery
Authors:
- 1 April 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-36
Abstract
Lexicographical order dependencies (ODs) specify orders between list of attributes, and are proven useful in optimizing SQL queries with order by clauses. To find hidden ODs from dirty data in practice, in this paper we make a first effort to study the approximate OD discovery problem, aiming at automatically discovering ODs that hold on the data with some exceptions. (1) We adapt two error measures to ODs, prove their desirable properties, and present efficient algorithms for computing the measures and related lower and upper bounds. (2) We present an efficient approximate OD discovery algorithm that is well suited to the two error measures, with a set of pruning rules and optimization techniques. (3) We conduct extensive experiments to verify the effectiveness and scalability of our methods, using real-life and synthetic data.Keywords
This publication has 22 references indexed in Scilit:
- Comparable dependencies over heterogeneous dataThe VLDB Journal, 2012
- Fundamentals of order dependenciesProceedings of the VLDB Endowment, 2012
- Sequential dependenciesProceedings of the VLDB Endowment, 2009
- Finding longest increasing and common subsequences in streaming dataJournal of Combinatorial Optimization, 2006
- Fundamental techniques for order optimizationACM SIGMOD Record, 1996
- Approximate dependency inference from relations1992
- Sort sets in the relational modelJournal of the ACM, 1986
- Order dependency in the relational modelTheoretical Computer Science, 1983
- Data Structures for Range SearchingACM Computing Surveys, 1979
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975