Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins
Kyoungmin Kim, Jaehyun Ha, George Fletcher, Wook-Shin Han
Abstract
We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements.
Topics & Concepts
JoinsComputer scienceSampling (signal processing)Join (topology)DatabaseTheoretical computer scienceData miningProgramming languageMathematicsCombinatoricsTelecommunicationsDetectorAlgorithms and Data CompressionData Management and AlgorithmsAdvanced Database Systems and Queries