---

---

Overview

• The Challenge
• The Major Sketch Families
• Sketch Origins
• Sketch Elements
• Key Features
  • Large Scale
  • Adaptors
• Architecture
• Overview Slide Deck

Section Links

• Frequent Items Sketches

• HLL Sketches

• Memory Package

• Quantiles Sketches

• Sampling Sketches

• Theta Sketches

• Tuple Sketches

• Other Information

Frequent Items Sketches

• Frequent Items Overview
• Frequent Items Java Example
• Frequent Items Pig UDFs
• Frequent Items Hive UDFs
• Frequent Items Error Table
• Frequent Items References

HLL Sketches

• HLL Sketch
• HLL Map Sketch

Memory Package

• Memory Package

Quantiles Sketches

• Quantiles Overview
• Quantiles Accuracy and Size
• Quantiles Sketch Java Example
• Quantiles Sketch Pig UDFs
• Quantiles Sketch Hive UDFs

Quantiles Sketch Theory

• Optimal Quantile Approximation in Streams
• Quantiles References

Sampling Sketches

• Reservoir Sampling
• Reservoir Sampling Performance
• Reservoir Sampling Java Example

Theta Sketches

• Theta Sketch Framework
• Theta Sketch Java Example

KMV Tutorial

• The Inverse Estimate
• Empty Sketch
• First Estimator
• Better Estimator
• Rejection Rules
• Update V(kth) Rule

Set Operations

• Set Operations

Accuracy

• Basic Accuracy
• Accuracy Plots
• Relative Error Table
• SetOp Accuracy

Size

• Theta Sketch Size

Speed

• Update Speed
• Merge Speed

Large Scale Computing

• Theta Sketch Pig UDFs
• Theta Sketch Hive UDFs
• Integration with Druid
• Memory Package
• p-Sampling

Theta Sketch Theory

• Theta Sketch Framework (PDF)
• Sketch Equations (PDF)
• DataSketches (PDF)
• Confidence Intervals Notes
• Merging Algorithm Notes
• Theta References

Tuple Sketches

• Tuple Sketch Overview
• Tuple Sketch Java Example
• Tuple Sketch Pig UDFs
• Tuple Sketch Hive UDFs

Other Information

• Creating Command Line Executables
• Who Uses
• License