| <!DOCTYPE html> |
| <!-- Start _layouts/doc_page.html--> |
| <html lang="en"> |
| |
| <head> |
| <!-- Start _include/site_head.html --> |
| <meta charset="UTF-8" /> |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| <meta name="description" content=""> |
| <meta name="author" content="datasketches"> |
| |
| <title>DataSketches | </title> |
| |
| <link rel="shortcut icon" href="/img/favicon.png"> |
| |
| <!-- original source: https://maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css --> |
| <link rel="stylesheet" href="/css/font-awesome.min.css"> |
| <!-- original source: https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css --> |
| <link rel="stylesheet" href="/css/bootstrap.min.css"> |
| |
| <link rel="stylesheet" href="/css/fonts.css" type="text/css"> |
| |
| <link rel="stylesheet" href="/css/main.css"> |
| <link rel="stylesheet" href="/css/header.css"> |
| <link rel="stylesheet" href="/css/footer.css"> |
| <link rel="stylesheet" href="/css/syntax.css"> |
| <link rel="stylesheet" href="/css/docs.css"> |
| |
| <script type="text/x-mathjax-config"> |
| MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},showMathMenu:false,showMathMenuMSIE:false,showProcessingMessages:false}); |
| </script> |
| |
| <!-- original source: https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMX_HTML-full --> |
| <script type="text/javascript" src="/js/MathJax.js?config=TeX-AMS_HTML"></script> |
| |
| <!-- original source: https://code.jquery.com/jquery.min.js --> |
| <script src="/js/jquery.min.js"></script> |
| |
| <!-- original source: https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js --> |
| <script src="/js/bootstrap.min.js"></script> <!-- 3.2.0--> |
| <!-- End _include/site_head.html --> |
| |
| </head> |
| |
| <body> |
| <!-- Start _include/nav_bar.html --> |
| <div class="navbar navbar-inverse navbar-static-top ds-nav"> |
| <div class="container"> |
| <div class="navbar-header"> |
| <button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse"> |
| <span class="sr-only">Toggle navigation</span> |
| <span class="icon-bar"></span> |
| <span class="icon-bar"></span> |
| <span class="icon-bar"></span> |
| </button> |
| <a href="/" style="padding-top: 0px; padding-bottom: 0px;"> |
| <span class="ds-small-h-logo"></span></a> |
| </div> |
| <div class="navbar-collapse collapse"> |
| <ul class="nav navbar-nav navbar-right"> |
| <li> |
| <a href="/docs/Background/TheChallenge.html"> |
| <span class="fa fa-info-circle"></span> DOCUMENTATION</a> |
| </li> |
| <li> |
| <a href="/docs/Community/Downloads.html"> |
| <span class="fa fa-download"></span> DOWNLOAD</a> |
| </li> |
| <!-- |
| <li> |
| <a href="/docs/Architecture/Components.html"> |
| <span class="fa fa-github"></span> GITHUB</a> |
| </li> |
| --> |
| <li> |
| <a href="/docs/Community/Research.html"> |
| <span class="fa fa-paper-plane"></span> RESEARCH</a> |
| </li> |
| <li> |
| <a href="/docs/Community/index.html" style="padding-top: 0; padding-bottom: 0;"> |
| <img class="ds-small-man" src="/img/datasketches-ManWhite.svg"/>COMMUNITY</a> |
| </li> |
| <li> |
| <ul class="nav navbar-nav navbar-right ds-nav"> |
| <li class="dropdown ds-nav" > |
| <a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false" style="padding-top: 0; padding-bottom: 0;"><img class="apache-logo" src="/img/feather.svg"/>Apache <span class="caret"></span></a> |
| <ul class="dropdown-menu ds-nav"> |
| <li><a href="https://www.apache.org/" target="_blank">Foundation</a></li> |
| <li><a href="https://www.apache.org/events/current-event" target="_blank">Events</a></li> |
| <li><a href="https://www.apache.org/licenses/" target="_blank">License</a></li> |
| <li><a href="https://privacy.apache.org/policies/privacy-policy-public.html" target="_blank">Privacy Policy</a></li> |
| <li><a href="https://www.apache.org/foundation/thanks.html" target="_blank">Thanks</a></li> |
| <li><a href="https://www.apache.org/security/" target="_blank">Security</a></li> |
| <li><a href="https://www.apache.org/foundation/sponsorship.html" target="_blank">Sponsorship</a></li> |
| </ul> |
| </li> |
| </ul> |
| </li> |
| </ul> |
| </div> |
| </div> |
| </div> |
| <!-- End _include/nav_bar.html --> |
| |
| |
| <!-- Start _include/javadocs.html --> |
| <div class="ds-header"> |
| <div class="container"> |
| <h4>API Snapshots: |
| <a href="https://apache.github.io/datasketches-java/4.2.0/">Java Core</a>, |
| <a href="https://apache.github.io/datasketches-cpp/5.0.0/">C++ Core</a>, |
| <a href="https://apache.github.io/datasketches-python/main/">Python</a>, |
| <a href="https://apache.github.io/datasketches-memory/master/">Memory</a>, |
| <a href="/api/pig/snapshot/apidocs/index.html">Pig</a>, |
| <a href="/api/hive/snapshot/apidocs/index.html">Hive</a>, |
| </h4> |
| </div> |
| </div> |
| <!-- End _include/javadocs.html --> |
| |
| |
| <div class="container"> |
| <div class="row"> |
| <!-- Start ToC Block --> |
| <div class="col-md-3"> |
| <div class="searchbox" style="position:relative"> |
| <gcse:searchbox-only></gcse:searchbox-only> |
| </div> |
| <!-- Start _includes/toc.html --> |
| <!-- Computer Generated File, Do Not Edit! --> |
| <link rel="stylesheet" href="/css/toc.css"> |
| <div id="toc" class="nav toc hidden-print"> |
| |
| <p id="background"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_background">Background</a> |
| </p> |
| <div class="collapse" id="collapse_background"> |
| <li><a href="/docs/Background/TheChallenge.html">•The Challenge</a></li> |
| <li><a href="/docs/Background/SketchOrigins.html">•Sketch Origins</a></li> |
| <li><a href="/docs/Background/SketchElements.html">•Sketch Elements</a></li> |
| <li><a href="/docs/Background/Presentations.html">•Presentations</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches_deck.pdf">•Overview Slide Deck</a></li> |
| </div> |
| |
| <p id="architecture-and-design"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_architecture_and_design">Architecture And Design</a> |
| </p> |
| <div class="collapse" id="collapse_architecture_and_design"> |
| <li><a href="/docs/Architecture/MajorSketchFamilies.html">•The Major Sketch Families</a></li> |
| <li><a href="/docs/Architecture/LargeScale.html">•Large Scale Computing</a></li> |
| <li><a href="/docs/Architecture/KeyFeatures.html">•Key Features</a></li> |
| <li><a href="/docs/Architecture/SketchFeaturesMatrix.html">•Sketch Features Matrix</a></li> |
| <li><a href="/docs/Architecture/Components.html">•Components</a></li> |
| <li><a href="/docs/Architecture/SketchesByComponent.html">•Sketches by Component</a></li> |
| <li><a href="/docs/Architecture/SketchCriteria.html">•Sketch Criteria</a></li> |
| |
| <p id="memory-component"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_memory_component">Memory Component</a> |
| </p> |
| <div class="collapse" id="collapse_memory_component"> |
| <li><a href="/docs/Memory/MemoryComponent.html">•Memory Component</a></li> |
| <li><a href="/docs/Memory/MemoryPerformance.html">•Memory Component Performance</a></li> |
| </div> |
| <li><a href="/docs/Architecture/OrderSensitivity.html">•Notes on Order Sensitivity</a></li> |
| <li><a href="/docs/Architecture/Concurrency.html">•Notes on Concurrency</a></li> |
| </div> |
| |
| <p id="sketch-families"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sketch_families">Sketch Families</a> |
| </p> |
| <div class="collapse" id="collapse_sketch_families"> |
| |
| <p id="distinct-counting"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_distinct_counting">Distinct Counting</a> |
| </p> |
| <div class="collapse" id="collapse_distinct_counting"> |
| <li><a href="/docs/DistinctCountFeaturesMatrix.html">•Features Matrix</a></li> |
| <li><a href="/docs/DistinctCountMeritComparisons.html">•Figures-of-Merit Comparison</a></li> |
| |
| <p id="cpc-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_cpc_sketches">CPC Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_cpc_sketches"> |
| <li><a href="/docs/CPC/CPC.html">•CPC Sketch</a></li> |
| <li><a href="/docs/CPC/CpcPerformance.html">•CPC Sketch Performance</a></li> |
| |
| <p id="cpc-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_cpc_examples">CPC Examples</a> |
| </p> |
| <div class="collapse" id="collapse_cpc_examples"> |
| <li><a href="/docs/CPC/CpcJavaExample.html">•CPC Sketch Java Example</a></li> |
| <li><a href="/docs/CPC/CpcCppExample.html">•CPC Sketch C++ Example</a></li> |
| <li><a href="/docs/CPC/CpcPigExample.html">•CPC Sketch Pig UDFs</a></li> |
| <li><a href="/docs/CPC/CpcHiveExample.html">•CPC Sketch Hive UDFs</a></li> |
| </div> |
| </div> |
| |
| <p id="hyperloglog-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hyperloglog_sketches">HyperLogLog Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_hyperloglog_sketches"> |
| <li><a href="/docs/HLL/HLL.html">•HLL Sketch</a></li> |
| <li><a href="/docs/HLL/HllMap.html">•HLL Map Sketch</a></li> |
| |
| <p id="hll-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hll_examples">HLL Examples</a> |
| </p> |
| <div class="collapse" id="collapse_hll_examples"> |
| <li><a href="/docs/HLL/HllJavaExample.html">•HLL Sketch Java Example</a></li> |
| <li><a href="/docs/HLL/HllCppExample.html">•HLL Sketch C++ Example</a></li> |
| <li><a href="/docs/HLL/HllPigUDFs.html">•HLL Sketch Pig UDFs</a></li> |
| <li><a href="/docs/HLL/HllHiveUDFs.html">•HLL Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="hll-studies"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hll_studies">HLL Studies</a> |
| </p> |
| <div class="collapse" id="collapse_hll_studies"> |
| <li><a href="/docs/HLL/HllPerformance.html">•HLL Sketch Performance</a></li> |
| <li><a href="/docs/HLL/Hll_vs_CS_Hllpp.html">•HLL vs Clearspring HLL++</a></li> |
| <li><a href="/docs/HLL/HllSketchVsDruidHyperLogLogCollector.html">•HLL Sketch vs Druid HyperLogLogCollector</a></li> |
| </div> |
| </div> |
| |
| <p id="theta-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_sketches">Theta Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_theta_sketches"> |
| <li><a href="/docs/Theta/ThetaSketchFramework.html">•Theta Sketch Framework</a></li> |
| |
| <p id="theta-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_examples">Theta Examples</a> |
| </p> |
| <div class="collapse" id="collapse_theta_examples"> |
| <li><a href="/docs/Theta/ConcurrentThetaSketch.html">•Concurrent Theta Sketch</a></li> |
| <li><a href="/docs/Theta/ThetaJavaExample.html">•Theta Sketch Java Example</a></li> |
| <li><a href="/docs/Theta/ThetaSparkExample.html">•Theta Sketch Spark Example</a></li> |
| <li><a href="/docs/Theta/ThetaPigUDFs.html">•Theta Sketch Pig UDFs</a></li> |
| <li><a href="/docs/Theta/ThetaHiveUDFs.html">•Theta Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="kmv-tutorial"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_kmv_tutorial">KMV Tutorial</a> |
| </p> |
| <div class="collapse" id="collapse_kmv_tutorial"> |
| <li><a href="/docs/Theta/InverseEstimate.html">•The Inverse Estimate</a></li> |
| <li><a href="/docs/Theta/KMVempty.html">•Empty Sketch</a></li> |
| <li><a href="/docs/Theta/KMVfirstEst.html">•First Estimator</a></li> |
| <li><a href="/docs/Theta/KMVbetterEst.html">•Better Estimator</a></li> |
| <li><a href="/docs/Theta/KMVrejection.html">•Rejection Rules</a></li> |
| <li><a href="/docs/Theta/KMVupdateVkth.html">•Update V(kth) Rule</a></li> |
| </div> |
| |
| <p id="set-operations-and-p-sampling"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_set_operations_and_p-sampling">Set Operations and P-sampling</a> |
| </p> |
| <div class="collapse" id="collapse_set_operations_and_p-sampling"> |
| <li><a href="/docs/Theta/ThetaSketchSetOps.html">•Set Operations</a></li> |
| <li><a href="/docs/Theta/ThetaSetOpsCornerCases.html">•Model & Test Set Operations</a></li> |
| <li><a href="/docs/Theta/ThetaPSampling.html">•<i>p</i>-Sampling</a></li> |
| </div> |
| |
| <p id="accuracy"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_accuracy">Accuracy</a> |
| </p> |
| <div class="collapse" id="collapse_accuracy"> |
| <li><a href="/docs/Theta/ThetaAccuracy.html">•Basic Accuracy</a></li> |
| <li><a href="/docs/Theta/ThetaAccuracyPlots.html">•Accuracy Plots</a></li> |
| <li><a href="/docs/Theta/ThetaErrorTable.html">•Relative Error Table</a></li> |
| <li><a href="/docs/Theta/ThetaSketchSetOpsAccuracy.html">•SetOp Accuracy</a></li> |
| <li><a href="/docs/Theta/AccuracyOfDifferentKUnions.html">•Unions With Different k</a></li> |
| </div> |
| |
| <p id="size"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_size">Size</a> |
| </p> |
| <div class="collapse" id="collapse_size"> |
| <li><a href="/docs/Theta/ThetaSize.html">•Theta Sketch Size</a></li> |
| </div> |
| |
| <p id="speed"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_speed">Speed</a> |
| </p> |
| <div class="collapse" id="collapse_speed"> |
| <li><a href="/docs/Theta/ThetaUpdateSpeed.html">•Update Speed</a></li> |
| <li><a href="/docs/Theta/ThetaMergeSpeed.html">•Merge Speed</a></li> |
| </div> |
| |
| <p id="theta-sketch-theory"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_sketch_theory">Theta Sketch Theory</a> |
| </p> |
| <div class="collapse" id="collapse_theta_sketch_theory"> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchFramework.pdf">•Theta Sketch Framework (PDF)</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchEquations.pdf">•Theta Sketch Equations (PDF)</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches.pdf">•DataSketches (PDF)</a></li> |
| <li><a href="/docs/Theta/ThetaConfidenceIntervals.html">•Confidence Intervals Notes</a></li> |
| <li><a href="/docs/Theta/ThetaMergingAlgorithm.html">•Merging Algorithm Notes</a></li> |
| <li><a href="/docs/Theta/ThetaReferences.html">•Theta References</a></li> |
| </div> |
| </div> |
| |
| <p id="tuple-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_tuple_sketches">Tuple Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_tuple_sketches"> |
| <li><a href="/docs/Tuple/TupleOverview.html">•Tuple Overview</a></li> |
| |
| <p id="tuple-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_tuple_examples">Tuple Examples</a> |
| </p> |
| <div class="collapse" id="collapse_tuple_examples"> |
| <li><a href="/docs/Tuple/TupleJavaExample.html">•Tuple Java Example</a></li> |
| <li><a href="/docs/Tuple/TupleEngagementExample.html">•Tuple Engagement Example</a></li> |
| <li><a href="/docs/Tuple/TuplePigUDFs.html">•Tuple Pig UDFs</a></li> |
| <li><a href="/docs/Tuple/TupleHiveUDFs.html">•Tuple Hive UDFs</a></li> |
| </div> |
| </div> |
| </div> |
| |
| <p id="most-frequent"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_most_frequent">Most Frequent</a> |
| </p> |
| <div class="collapse" id="collapse_most_frequent"> |
| <li><a href="/docs/Frequency/FrequencySketchesOverview.html">•Frequency Sketches Overview</a></li> |
| |
| <p id="frequent-item-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_item_sketches">Frequent Item Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_frequent_item_sketches"> |
| <li><a href="/docs/Frequency/FrequentItemsOverview.html">•Frequent Items Overview</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsErrorTable.html">•Frequent Items Error Table</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsReferences.html">•Frequent Items References</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsPerformance.html">•Frequent Items Performance</a></li> |
| |
| <p id="most-frequent-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_most_frequent_examples">Most Frequent Examples</a> |
| </p> |
| <div class="collapse" id="collapse_most_frequent_examples"> |
| <li><a href="/docs/Frequency/FrequentItemsJavaExample.html">•Frequent Items Java Example</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsCppExample.html">•Frequent Items C++ Example</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsPigUDFs.html">•Frequent Items Pig UDFs</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsHiveUDFs.html">•Frequent Items Hive UDFs</a></li> |
| </div> |
| </div> |
| |
| <p id="frequent-distinct-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_distinct_sketches">Frequent Distinct Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_frequent_distinct_sketches"> |
| <li><a href="/docs/Frequency/FrequentDistinctTuplesSketch.html">•Frequent Distinct Tuples Sketch</a></li> |
| </div> |
| </div> |
| |
| <p id="quantiles-and-histograms"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_and_histograms">Quantiles And Histograms</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_and_histograms"> |
| <li><a href="/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">•Quantiles and Ranks Tutorial</a></li> |
| <li><a href="/docs/Quantiles/QuantilesOverview.html">•Quantiles Overview</a></li> |
| <li><a href="/docs/KLL/KLLSketch.html">•KLL Floats sketch</a></li> |
| <li><a href="/docs/KLL/KLLAccuracyAndSize.html">•KLL Sketch Accuracy and Size</a></li> |
| <li><a href="/docs/REQ/ReqSketch.html">•REQ Floats sketch</a></li> |
| <li><a href="/docs/Quantiles/OrigQuantilesSketch.html">•Original QuantilesSketch</a></li> |
| |
| <p id="quantiles-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_examples">Quantiles Examples</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_examples"> |
| <li><a href="/docs/Quantiles/QuantilesJavaExample.html">•Quantiles Sketch Java Example</a></li> |
| <li><a href="/docs/KLL/KLLCppExample.html">•KLL Quantiles Sketch C++ Example</a></li> |
| <li><a href="/docs/Quantiles/QuantilesPigUDFs.html">•Quantiles Sketch Pig UDFs</a></li> |
| <li><a href="/docs/Quantiles/QuantilesHiveUDFs.html">•Quantiles Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="quantiles-studies"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_studies">Quantiles Studies</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_studies"> |
| <li><a href="/docs/QuantilesStudies/DruidApproxHistogramStudy.html">•Druid Approximate Histogram</a></li> |
| <li><a href="/docs/QuantilesStudies/MomentsSketchStudy.html">•Moments Sketch Study</a></li> |
| <li><a href="/docs/QuantilesStudies/QuantilesStreamAStudy.html">•Quantiles StreamA Study</a></li> |
| <li><a href="/docs/QuantilesStudies/ExactQuantiles.html">•Exact Quantiles for Studies</a></li> |
| </div> |
| |
| <p id="quantiles-sketch-theory"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_sketch_theory">Quantiles Sketch Theory</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_sketch_theory"> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/Quantiles_KLL.pdf">•Optimal Quantile Approximation in Streams</a></li> |
| <li><a href="/docs/Quantiles/QuantilesReferences.html">•Quantiles References</a></li> |
| </div> |
| </div> |
| |
| <p id="sampling"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sampling">Sampling</a> |
| </p> |
| <div class="collapse" id="collapse_sampling"> |
| <li><a href="/docs/Sampling/ReservoirSampling.html">•Reservoir Sampling</a></li> |
| <li><a href="/docs/Sampling/ReservoirSamplingPerformance.html">•Reservoir Sampling Performance</a></li> |
| <li><a href="/docs/Sampling/VarOptSampling.html">•VarOpt Sampling</a></li> |
| |
| <p id="sampling-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sampling_examples">Sampling Examples</a> |
| </p> |
| <div class="collapse" id="collapse_sampling_examples"> |
| <li><a href="/docs/Sampling/ReservoirSamplingJava.html">•Reservoir Sampling Java Example</a></li> |
| <li><a href="/docs/Sampling/ReservoirSamplingPigUDFs.html">•Reservoir Sampling Pig UDFs</a></li> |
| <li><a href="/docs/Sampling/VarOptSamplingJava.html">•VarOpt Sampling Java Example</a></li> |
| <li><a href="/docs/Sampling/VarOptPigUDFs.html">•VarOpt Sampling Pig UDFs</a></li> |
| </div> |
| </div> |
| </div> |
| |
| <p id="system-integrations"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_system_integrations">System Integrations</a> |
| </p> |
| <div class="collapse" id="collapse_system_integrations"> |
| <li><a href="/docs/SystemIntegrations/ApacheDruidIntegration.html">•Using Sketches in ApacheDruid</a></li> |
| <li><a href="/docs/SystemIntegrations/ApacheHiveIntegration.html">•Using Sketches in Apache Hive</a></li> |
| <li><a href="/docs/SystemIntegrations/ApachePigIntegration.html">•Using Sketches in Apache Pig</a></li> |
| <li><a href="/docs/SystemIntegrations/PostgreSQLIntegration.html">•Using Sketches in PostgreSQL</a></li> |
| </div> |
| |
| <p id="community"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_community">Community</a> |
| </p> |
| <div class="collapse" id="collapse_community"> |
| <li><a href="/docs/Community/index.html">•Community</a></li> |
| <li><a href="/docs/Community/Downloads.html">•Downloads</a></li> |
| <li><a href="/docs/Community/NewCommitterProcess.html">•Committer Process</a></li> |
| <li><a href="/docs/Community/ReleaseProcessForCppComponents.html">•Release Process For CPP Components</a></li> |
| <li><a href="/docs/Community/ReleaseProcessForJavaComponents.html">•Release Process For Java Components</a></li> |
| <li><a href="/docs/Community/Transitioning.html">•Transitioning from prior GitHub Site</a></li> |
| </div> |
| |
| <p id="research"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_research">Research</a> |
| </p> |
| <div class="collapse" id="collapse_research"> |
| <li><a href="/docs/Community/Research.html">•Research</a></li> |
| </div> |
| </div> |
| <!-- End _includes/toc.html --> |
| |
| |
| <!-- Start _includes/tocScript.html --> |
| <script> |
| (function () { |
| |
| var findLineItem = function (path) { |
| return document.querySelector(`#toc [href="${path}"]`); |
| }; |
| |
| function findNavItem(path) { |
| return document.querySelector(`.nav [href="${path}"]`); |
| } |
| |
| var highlighLineItem = function (element) { |
| element.classList.add('highlight'); |
| }; |
| |
| var checkHasClass = function (element, className) { |
| return element.className.split(' ').find(function (item) { return item === className || '' }) |
| } |
| |
| var findAllCollapseParents = function (element) { |
| var collapseMenus = []; |
| var elementPointer = element; |
| while (elementPointer !== document.body) { |
| if (checkHasClass(elementPointer, 'collapse')) { |
| collapseMenus.push(elementPointer); |
| } |
| elementPointer = elementPointer.parentElement |
| } |
| return collapseMenus |
| }; |
| |
| var openMenuItem = function (element) { |
| // $(element).collapse('show') would start a transition, adding `in` class instead. |
| element.classList.add('in'); |
| }; |
| |
| var openAllFromList = function (elementList) { |
| elementList.forEach(openMenuItem); |
| }; |
| |
| var highlightAndOpenMenu = function () { |
| // Highlight & expand nav item in the TOC |
| var currentLineItem = findLineItem(document.location.pathname); |
| highlighLineItem(currentLineItem); |
| openAllFromList(findAllCollapseParents(currentLineItem)); |
| |
| // Highlight nav item in top navigation |
| highlighLineItem(findNavItem(document.location.pathname)); |
| }; |
| |
| $(highlightAndOpenMenu); |
| |
| }()); |
| </script> |
| <!-- End _includes/tocScript.html --> |
| |
| </div> |
| <!-- End ToC Block --> |
| <div class="col-md-9 doc-content"> |
| <!-- |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, |
| software distributed under the License is distributed on an |
| "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| KIND, either express or implied. See the License for the |
| specific language governing permissions and limitations |
| under the License. |
| --> |
| |
| <h1 id="major-sketch-families">Major Sketch Families</h1> |
| <p>Please see the <a href="/docs/Architecture/SketchFeaturesMatrix.html">Sketch Features Matrix</a> for a detailed comparison of the features of the different sketches in the library.</p> |
| |
| <h2 id="cardinality-sketches">Cardinality Sketches</h2> |
| |
| <h3 id="cpc-sketch-estimating-stream-cardinalities-more-efficiently-than-the-famous-hll-sketch"><a href="/docs/CPC/CPC.html">CPC Sketch</a>: Estimating Stream Cardinalities more efficiently than the famous HLL sketch!</h3> |
| <p>This sketch was developed by the late Keven J. Lang, our chief scientist at the time. It is an amazing <em>tour de force</em> of scientific design and engineering and has substantially better accuracy / per stored size than the famous HLL sketch. The theory and demonstration of its performance is detailed in Lang’s paper <a href="https://arxiv.org/abs/1708.06839">Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm</a>.</p> |
| |
| <h3 id="theta-sketches-estimating-stream-expression-cardinalities"><a href="/docs/Theta/ThetaSketchFramework.html">Theta Sketches</a>: Estimating Stream Expression Cardinalities</h3> |
| <p>Internet content, search and media companies like Yahoo, Google, Facebook, etc., collect many tens of billions of event records from the many millions of users to their web sites each day. These events can be classified by many different dimensions, such as the page visited and user location and profile information. Each event also contains some unique identifiers associated with the user, specific device (cell phone, tablet, or computer) and the web browser used.</p> |
| |
| <p><img class="doc-img-full" src="/docs/img/PeopleCloud.png" alt="PeopleCloud" /></p> |
| |
| <p>These same unique identifiers will appear on every page that the user visits. In order to measure the number of unique identifiers on a page or across a number of different pages, it is necessary to discount the identifier duplicates. Obtaining an exact answer to a <em>COUNT DISTINCT</em> query with massive data is a difficult computational challenge. It is even more challenging if it is necessary to compute arbitrary expressions across sets of unique identifiers. For example, if set <em>S</em> is the set of user identifiers visiting the Sports page and set <em>F</em> is the set of user identifiers visiting the Finance page, the intersection expression <em>S ∩ F</em> represents the user identifiers that visited both Sports and Finance.</p> |
| |
| <p>Computing cardinalities with massive data requires lots of computer resources and time. |
| However, if an approximate answer to these problems is acceptable, <a href="/docs/Theta/ThetaSketchFramework.html">Theta Sketches</a> can provide reasonable estimates, in a single pass, orders of magnitude faster, even fast enough for analysis in near-real time.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/theta/Sketch.java">theta/Sketch</a> can operate both on-heap and off-heap, has powerful Union, Intersection, AnotB and Jaccard operators, has a high-performance concurrent form for multi-threaded environments, has both immutable compact, and updatable representations, and is quite fast. Because of its flexibility, it is one of the most popular sketches in our library.</p> |
| |
| <h3 id="tuple-sketches-extending-theta-sketches-to-perform-associative-analysis"><a href="/docs/Tuple/TupleOverview.html">Tuple Sketches</a>: Extending Theta Sketches to Perform Associative Analysis</h3> |
| <p>It is often not enough to perform stream expressions on sets of unique identifiers, it is very valuable to be able to associate additive data with these identifiers, such as impression counts, clicks or timestamps. Tuple Sketches are a natural extension of the Theta sketch and have Java Genric forms that enable the user to define the sketch with arbitrary “summary” data. The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/tuple/Sketch.java">tuple/Sketch</a> can operate both on-heap and off-heap, includes both Union and Intersection operators, and has both immutable compact and updatable representations.</p> |
| |
| <p>The Tuple sketch is effectively infinitely extendable and there are several common variants of the Tuple Sketch, which also serve as examples on how to extend the base classes that are also in the library, including:</p> |
| |
| <ul> |
| <li><a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/tuple/adouble/DoubleSketch.java">tuple/adouble/DoubleSketch</a> with a single column of <em>double</em> values as the <em>summary</em>.</li> |
| <li><a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerSketch.java">tuple/aninteger/IntegerSketch</a> with a single column of <em>int</em> values as the <em>summary</em>.</li> |
| <li><a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/tuple/strings/ArrayOfStringsSketch.java">tuple/strings/ArrayOfStringsSketch</a>, which is effectively a variable number of columns of strings as the <em>summary</em>.</li> |
| <li><a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/tuple/ArrayOfDoublesSketch.java">tuple/ArrayOfDoublesSketch</a>, which enables the user to specify the number of columns of double values as the <em>summary</em>. This variant also provides both on-heap and off-heap operation.</li> |
| </ul> |
| |
| <h3 id="hyperloglog-sketches-estimating-stream-cardinalities"><a href="/docs/HLL/HLL.html">HyperLogLog Sketches</a>: Estimating Stream Cardinalities</h3> |
| <p>The HyperLogLog (HLL) is a cardinality sketch similar to the above Theta sketches except they are anywhere from 2 to 16 times smaller in size. The HLL sketches can be merged via the Union operator, but set intersection and difference operations are not provided intrinsically, because the resulting error would be quite poor. If your application only requires cardinality estimation and merging and space is at a premium, the HLL or CPC sketches would be your best choice.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/hll/HllSketch.java">hll/HllSketch</a> can operate both on-heap and off-heap, provides the Union operators, and has both immutable compact and updatable representations.</p> |
| |
| <h3 id="hyperloglog-map-sketch-estimating-stream-cardinalities-of-key-value-pairs"><a href="/docs/HLL/HllMap.html">HyperLogLog Map Sketch</a>: Estimating Stream Cardinalities of Key-Value Pairs</h3> |
| <p>This is a specially designed sketch that addresses the problem of individually tracking value cardinalities of Key-Value (K,V) pairs in real-time, where the number of keys can be very large, such as IP addresses, or Geo identifiers, etc. Assigning individual sketches to each key would create unnecessary overhead. This sketch streamlines the process with much better space management. This <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/hllmap/UniqueCountMap.java">hllmap/UniqueCountMap</a> only operates on heap and does not provide Union capabilites. This sketch is effectively a optimized hash-map of HLL sketches. Like other hash-maps, the overall size is a direct function of the number of keys that it has seen. This sketch was designed to operate as a stand-alone sketch.</p> |
| |
| <h2 id="quantiles-sketches">Quantiles Sketches</h2> |
| |
| <h3 id="quantiles-sketches-estimating-distributions-from-a-stream-of-values"><a href="/docs/Quantiles/QuantilesOverview.html">Quantiles Sketches</a>: Estimating Distributions from a Stream of Values</h3> |
| <p>There are many situations where is valuable to understand the distribution of values in a stream. For example, from a stream of web-page time-spent values, it would be useful to know arbitrary quantiles of the distribution, such as the 25th percentile value, the median value and the 75th percentile value. The <a href="/docs/Quantiles/QuantilesOverview.html">Quantiles Sketches</a> solve this problem and enable the inverse functions such as the Probability Mass Function (PMF) and the Cumulative Distribution Function (CDF) as well. It is relatively easy to produce frequency histograms such as the following diagram, which was produced from a stream of over 230 million time spent events. The space consumed by the sketch was about 43KB.</p> |
| |
| <p><img class="doc-img-full" src="/docs/img/quantiles/TimeSpentHistogram.png" alt="TimeSpentHistogram" /></p> |
| |
| <p>There are two different families of quantiles sketches, the original <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java">quantiles/DoublesSketch</a>, which can be operated either on-heap or off-heap, and is also available in a Java Generic form for arbitrary comparable objects.</p> |
| |
| <p>Later we developed the <a href="https://datasketches.apache.org/docs/KLL/KLLSketch.html">kll/KllSketch</a> (Named after its authors), which is also a quantiles sketch, that achieves near optimal small size for a given accuracy.</p> |
| |
| <p>The most recent sketch in this group is called the Relative Error Quantiles <a href="https://datasketches.apache.org/docs/REQ/ReqSketch.html">ReqSketch</a>, which is a cousin of the KLL sketch except that it provides very high accuracy at one of the ends of the rank domain. If your application requires high accuracy primarily for the very high ranks, e.g., the 99.999%ile, or the very low ranks, e.g. the .00001%ile, and you can give up some accuracy at the other end of the rank scale, this sketch is designed for you.</p> |
| |
| <h2 id="frequent-items--heavy-hitters-sketches">Frequent Items / Heavy Hitters Sketches</h2> |
| |
| <h3 id="frequent-items-sketches-finding-the-heavy-hitter-objects-from-a-stream"><a href="/docs/Frequency/FrequentItemsOverview.html">Frequent Items Sketches</a>: Finding the Heavy Hitter Objects from a Stream</h3> |
| <p>It is very useful to be able to scan a stream of objects, such as song titles, and be able to quickly identify those titles that occur most frequently. The term <i>Heavy Hitter</i> is defined to be an item that occurs more frequently than its fair share of occurrences. This “fair share” is simply the total count of all occurrences of all items divided by the number of distinct items. Suppose you have a stream of 1M song titles, but in that stream there are only 100K song titles that are unique. If any single title consumes more than 10% of the stream elements it is a Heavy Hitter. The 10% is a threshold parameter we call epsilon.</p> |
| |
| <p>The accuracy of a Frequent Items Sketch is proportional to the configured size of the sketch, the larger the sketch, the smaller is the epsilon threshold that can detect Heavy Hitters. This sketch is available in two forms, as the <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/frequencies/LongsSketch.java">frequencies/LongsSketch</a> used for processing a stream of tuples {<em>long</em>, weight}, and the <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/frequencies/ItemsSketch.java">frequencies/ItemsSketch</a> used for processing tuples of {<em>T</em>, weight}, where <em>T</em> is arbitrary, uniquely identifyable object. These sketches are aggregating sketches in that the frequency of occurances of an item (or <em>long</em> key), is accumulated as the stream is processed.</p> |
| |
| <h3 id="frequent-distinct-tuples-sketch-finding-the-heavy-hitter-tuples-from-a-stream"><a href="/docs/Frequency/FrequentDistinctTuplesSketch.html">Frequent Distinct Tuples Sketch</a>: Finding the Heavy Hitter tuples from a Stream.</h3> |
| <p>Suppose our data is a stream of pairs {IP address, User ID} and we want to identify the IP addresses that have the most distinct User IDs. Or conversely, we would like to identify the User IDs that have the most distinct IP addresses. This is a common challenge in the analysis of big data and the FDT sketch helps solve this problem using probabilistic techniques.</p> |
| |
| <p>More generally, given a multiset of tuples with <em>N</em> dimensions <em>{d1,d2, d3, …, dN}</em>, and a primary subset of dimensions <em>M < N</em>, our task is to identify the combinations of <em>M</em> subset dimensions that have the most frequent number of distinct combinations of the <em>N - M</em> non-primary dimensions.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/fdt/FdtSketch.java">fdt/FdtSketch</a> is currently only available in Java, but because it is an extension of the Tuple Sketch family, it inherits many of the same properties: it can operate both on-heap and off-heap, it includes both Union and Intersection operators, and it has both immutable compact and updatable representations.</p> |
| |
| <h3 id="frequent-directions-distributed-mergeable-singular-value-decomposition">Frequent Directions: Distributed, mergeable Singular Value Decomposition</h3> |
| <p>Part of a new separate datasketches-vector component, Frequent Directions is in many ways a generalization of the Frequent Items sketch in order to handle vector data. This sketch computes an approximate singular value decomposition (SVD) of a matrix, providing a projection matrix that can be used for dimensionality reduction. SVD is a key technique in many recommender systems, such as providing shopping suggestions based on a customer’s past purchases compared with other similar customers. This sketch is still experimental and feedback from interested users would be welcome. This sketch can be found in the <a href="https://github.com/apache/datasketches-vector">Vector</a> repository dedicated to vector and matrix sketches.</p> |
| |
| <h2 id="sampling-sketches">Sampling Sketches</h2> |
| |
| <h3 id="sampling-sketches-uniform-and-weighted-sampling-of-a-stream-into-a-fixed-size-space"><a href="/docs/Sampling/ReservoirSampling.html">Sampling Sketches</a>: Uniform and Weighted Sampling of a Stream into a fixed size space</h3> |
| <p>This family of sketches implements an enhanced version of the famous Reservoir sampling algorithm and extends it with the capabilities that large-scale distributed systems really need: mergability (even with different sized sketches). The Java implementaion uses Java Generics so that the base classes can be trivially extended for any input type (even polymorphic types), and also enables an extensible means of performing serialization and deserialization.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/sampling/ReservoirLongsSketch.java">sampling/ReservoirLongsSketch</a> accepts a stream of <em>long</em> values as identifiers with a weight of one, and produces a result Reservoir of a pre-determined size that represents a uniform random sample of the stream.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/sampling/ReservoirItemsSketch.java">sampling/ReservoirItemsSketch</a> accepts a stream of type <em>T</em> as identifiers with a weight of one, and produces a result Reservoir of a pre-determined size that represents a uniform random sample of the stream.</p> |
| |
| <p>The <a href="https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/sampling/VarOptItemsSketch.java">sampling/VarOptItemsSketch</a> extends the Reservoir family to weighted sampling, additionally providing subset sum estimates from the sample with provably optimal variance.</p> |
| |
| |
| </div> <!-- End content --> |
| </div> <!-- End row --> |
| </div> <!-- End Container --> |
| |
| <!-- Start _include/page_footer.html --> |
| <footer class="ds-footer"> |
| <div class="container"> |
| <div class="text-center"> |
| <p> |
| <div>Copyright © 2024 <a href="https://www.apache.org">Apache Software Foundation</a>, |
| Licensed under the Apache License, Version 2.0. All Rights Reserved. |
| | <a href="https://privacy.apache.org/policies/privacy-policy-public.html">Privacy Policy</a><br/> |
| Apache DataSketches, Apache, the Apache feather logo, and the Apache DataSketches project logos are trademarks of The Apache Software Foundation.<br/> |
| All other marks mentioned may be trademarks or registered trademarks of their respective owners. |
| </div> |
| </p> |
| </div> |
| </div> |
| </footer> |
| <!-- End _include/page_footer.html --> |
| |
| </body> |
| |
| </html> |
| <!-- End _layouts/doc_page.html--> |
