PaperlayerView exact revision on arXiv

Source-linked AI summary

MacroBase: Prioritizing Attention in Fast Data

Peter Bailis, Edward Gan, Samuel Madden, Deepak Narayanan, Kexin Rong, Sahaana Suri

arXiv:1603.00567v4cs.DB

TL;DR

Fast data streams exceed the capacity for manual inspection, motivating an analytics engine that prioritizes user attention. MacroBase combines streaming classification and explanation; the paper reports performance and result-quality benefits and deployments that identified previously unknown behaviors.

  • Problem

    Fast-growing data volumes exceed human capacity for manual inspection, while operators report accessing less than 6% of collected data.

    Source: §1 · p. 1

  • Method

    MacroBase combines streaming classification and explanation in extensible pipelines that classify data points and explain groups by highlighting commonalities.

    Source: §1 · p. 1

  • Results

    MacroBase’s default operators and new sampling and sketching procedures improve performance and result quality, and production deployments have identified previously unknown behaviors.

    Source: §8 · p. 12

  • Takeaways & Limitations

    MacroBase’s flexible architecture and default operators have proven useful in several production deployments.

    Source: §8 · p. 12

    The paper does not directly present results over production data from the datacenter telemetry scenarios.

    Source: §2 · p. 3

Abstract

from arXiv · show

As data volumes continue to rise, manual inspection is becoming increasingly untenable. In response, we present MacroBase, a data analytics engine that prioritizes end-user attention in high-volume fast data streams. MacroBase enables efficient, accurate, and modular analyses that highlight and aggregate important and unusual behavior, acting as a search engine for fast data. MacroBase is able to deliver order-of-magnitude speedups over alternatives by optimizing the combination of explanation and classification tasks and by leveraging a new reservoir sampler and heavy-hitters sketch specialized for fast data streams. As a result, MacroBase delivers accurate results at speeds of up to 2M events per second per query on a single core. The system has delivered meaningful results in production, including at a telematics company monitoring hundreds of thousands of vehicles.

1. INTRODUCTION

Fast data volumes outstrip human attention, while existing analytics engines leave the difficult work of prioritizing results to developers. MacroBase combines streaming classification and explanation in a modular analytics engine, with specialized operators and reported speed and accuracy gains.

1. INTRODUCTION

  • Data volumes are outpacing human capacity, and operators report accessing less than 6% of collected data; existing engines leave attention-prioritizing operators to developers.Industrial deployments often rely on static rules and thresholds, which analysts describe as brittle and error-prone.Source: §1 · p. 1
  • MacroBase has been used to find unusual, previously unknown behaviors across mobile devices, datacenter telemetry, automotive data, and manufacturing processes.One example identifies B264 devices running application version 2.26.3 as sixty times more likely to experience abnormally high power drain than the rest of the stream.Source: §1 · p. 2
  • The pipeline is extensible: users can add domain-specific transformations, supervised rules, and custom operators without modifying the rest of the pipeline.The mobile-app example adds a time-series transformation, a rule for readings above 100W, and a custom time-series explanation operator.Source: §1 · p. 2
  • MacroBase adapts analyses to changing streams with the Adaptable Damped Reservoir and exponentially weighted sketches that track attribute-value correlations.The reservoir samples over arbitrarily sized, exponentially damped windows and supports incremental training of unsupervised classifiers.Source: §1 · p. 2
  • For explanations, MacroBase uses relative risk and exploits class-size imbalance by examining the small outlier set before pruning the larger inlier search.A new Amortized Maintenance Counter reduces data-structure maintenance when repeated measurements share attributes.Source: §1 · p. 2
  • MacroBase’s optimized operators achieve order-of-magnitude performance improvements over existing operators, reaching up to 2M events per second per query while delivering accurate results in controlled studies.The evaluation includes production telematics data and publicly available real-world datasets.Source: §1 · p. 2
  • MacroBase combines streaming outlier detection and explanation, using classification to identify unusual points and explanations to highlight attribute commonalities.Its unsupervised density-based classifiers identify points far from the population, and sketch-based explanations highlight attributes that differentiate outliers.Source: §1 · pp. 1–2

2. TARGET ENVIRONMENT

Industrial monitoring, mobile telematics, and datacenter operations all generate data in which consequential behaviors can be difficult to surface through manual analysis. MacroBase is reported in production at CMT, while the paper does not directly present production-data results for the datacenter scenarios.

Mobile applications

  • CMT engineers struggled to monitor application behavior and identify less frequent problems obscured by low overall failure rates and a heterogeneous device base.The cited example involved an iOS beta Bluetooth bug that prevented connections to CMT sensors.Source: §2 · pp. 2–3
  • CMT deployed MacroBase in production, where it highlighted interesting behaviors in data collected from many hundreds of thousands of vehicles.The company collects mobile-sensor data at tens of Hz.Source: §2 · pp. 2–3

Datacenter operation

  • Datacenter operators reported difficulty identifying transient slowdowns across heterogeneous workloads, with failure postmortems taking hours to days.The DynamoDB postmortem describes customers experiencing disproportionately high error rates despite a low overall rate.Source: §2 · p. 3
  • The paper does not directly present production-data results for the datacenter scenarios, which it describes as ongoing MacroBase activity.Source: §2 · p. 3

Industrial monitoring

  • Industrial operators wanted analytics and alerting that could adapt to new sensors and changing conditions, and the paper illustrates drawing attention to unusual behaviors in electrical utilities.The cited plant postmortem described a dangerous temperature trend that preceded an alarm by hours.Source: §2 · p. 3

3. MacroBase ARCHITECTURE AND APIS

MacroBase uses composable streaming operators to classify individual points and explain groups of points, with typed interfaces supporting domain-specific pipelines. Its architecture carries data from ingestion and optional feature transformations through classification and explanation to ranked presentation.

3.1 Core Concepts

  • Classification labels individual points, while explanation groups and aggregates them so each result can represent many classification outputs.The paired operators support the goal of returning more information with less output.Source: §3.1 · p. 3
  • MacroBase’s streaming operators are designed to be reusable and composable across changing data, unlike the one-off classification and explanation analyses described as common practice.Combining core operators with domain-specific feature extraction supports reuse beyond ad-hoc analyses.Source: §3.1 · p. 3

3.2 System Architecture

  • A query pipeline ingests data, optionally transforms features, classifies points, aggregates labeled points into explanations, and ranks results for presentation.Ingestion currently handles any required ordering and joins; explanation results can be emitted on demand or periodically.Source: §3.2 · p. 4
  • Typed, stream-oriented operator interfaces enforce pipeline interoperability while allowing users to substitute operators and combine MacroBase stages with conventional dataflow operators.Supported conventional operators include selection, projection, join, windowing, aggregation, and group-by.Source: §3.2 · p. 4
  • The default presentation ranks explanations and exposes them through a static report via REST API or GUI, where interactive exploration can help formulate standing queries.Source: §3.2 · p. 4
  • Users can add domain-specific transformations or supervised rules, or implement custom operators and pipelines; these extension paths require varying expertise.Two graduate students implemented and tested new outlier detectors in under a week of part-time work, while core maintainers needed less than an afternoon for a new pipeline.Source: §3.2 · p. 4

2. TRANSFORM

MacroBase’s default pipeline connects streaming classification and explanation operators, while its interfaces allow users to extend pipelines with custom operators and features. The paper also reports that robust estimators outperform the Z-score approach under outlier contamination.

2. TRANSFORM

  • The default analytics pipeline ingests streaming points, scores and classifies them, aggregates them with an explanation operator, then ranks and presents results to users.Source: Figure 1 · p. 5
  • MacroBase’s interfaces let users write and test custom feature-transformation, classification, and explanation operators, as well as new pipelines.Two graduate students completed new outlier detector operators in less than a week of part-time work; maintainers completed a new pipeline in less than an afternoon.Source: §2 · p. 5
  • The object-oriented interface is compatible with stream-to-relation semantics in principle, while realizing that mapping and higher-level declarative interfaces remain future work.Source: §2 · p. 5
  • Robust methods MAD and MCD outperform the Z-score-based approach in discriminative power under outlier contamination.Source: Figure 3 · p. 5

4. MDP CLASSIFICATION

MDP uses robust statistical estimators to identify unusual points, then uses an adaptable damped reservoir to keep models and score thresholds current as streams change. Its classification approach is resilient to substantial outlier contamination, but assumes normally distributed data and does not consider multimodal behavior.

4.1 Robust Distribution Estimation

  • 50% contamination: MAD and MCD remain resilient, while the Z-Score cannot distinguish inliers and outliers under even modest contamination.Figure 3 reports this comparison for identifying points in outlier clusters.Source: §4.1 · p. 6
  • For univariate queries MDP uses MAD, and for multivariate queries it uses FastMCD; percentile cutoffs on model scores identify outliers without user-provided labels or rules.MAD and MCD are parametric estimators that assume normally distributed data; multimodal behavior is not considered here.Source: §4.1 · pp. 5–6

4.2 MDP Streaming Execution

  • MDP’s ADR-based model maintenance addresses the need to update MAD and MCD estimators as stream distributions change.The paper notes that it was not aware of a streaming algorithm for training MAD or MCD.Source: §4.2 · p. 6
  • The Adaptable Damped Reservoir (ADR) keeps a sample weighted toward recent points and supports arbitrary decay intervals, unlike samplers that decay per tuple.Separating insertion from decay permits time-based or tuple-based policies; tuple-at-a-time decay can skew samples toward high-volume periods when arrival rates vary.Source: §4.2 · p. 6
  • MDP uses ADR samples to periodically retrain robust estimators and recompute score quantiles, with time- or tuple-based retraining intervals.A sample of size 20K provides a 1% approximation of an arbitrary quantile with 99% probability.Source: §4.2 · pp. 6–7

5. MDP EXPLANATION

MDP explains unusual behavior by finding attribute combinations that are common among outliers but uncommon among inliers, using risk ratio and support thresholds. Its explanation pipeline prunes the search using outlier cardinality and single-attribute scores, then supports streaming counts with the Amortized Maintenance Counter and a prefix tree.

5.1 Semantics: Support and Risk Ratio

  • Risk ratio measures how much more likely an attribute combination is among outliers than in the general population, while support thresholds exclude rare, non-systemic combinations.MDP reports combinations whose risk ratio and support exceed configured thresholds.Source: §5.1 · p. 7

5.2 Basic Explanation Strategy

  • MDP first finds supported outlier attributes, then searches inliers only for those attributes, pruning work because outliers are fewer than inliers.It also computes single-attribute risk ratios before mining combinations, since single-attribute counts are inexpensive and combinations can be costly to enumerate.Source: §5.2 · p. 7
  • MDP uses FP-growth prefix-tree approaches to mine combinations, and reports correlated attributes together when their subsets are supported and meet the minimum risk ratio.The paper notes that grouped explanations can help avoid overwhelming users with separate explanations.Source: §5.2 · p. 7

5.3 Streaming Explanation

  • The Amortized Maintenance Counter (AMC) speeds heavy-hitter updates with constant-time insertion, trading higher space use for periodic maintenance.AMC’s sketch can grow between maintenance calls and, in the limit, must hold all items seen during an interval.Source: §5.3 · p. 8
  • Streaming explanations combine AMC attribute counts with a frequency-descending prefix tree, which is decayed and pruned at window boundaries before FP-growth generates explanations.AMC separates insertion from maintenance, allowing constant-time updates and maintenance policies based on size or time and tuple windows.Source: §5.3 · p. 8

6. EVALUATION

The evaluation tests MacroBase’s accuracy, throughput, operator efficiency, and extensibility on synthetic, real-world, and production data. Results show high throughput and useful explanations, with adaptive sampling and modular pipelines handling changing streams and varied domains.

6.1 Result Quality

  • Without noise, MDP identified 100% of outlying devices; it remained robust until approximately 25% label noise, while measurement-noise accuracy degraded linearly.Measurement-noise accuracy suffered more when there were more devices, since each device type was exposed to more noisy readings.Source: §6.1 · p. 9, Figure 4 · p. 9
  • In MDP experiments, QS achieved 86.1% top-1 (88.8% top-3) accuracy across all anomaly forms on holdout clusters, using one hostname-attribute query and 15 feature-selected metrics; QE achieved perfect top-3 accuracy with anomaly-specific metrics.With proper feature selection, MacroBase accurately recovers systemic causes even in unsupervised settings.Source: §6.1 · p. 9
  • ADR adapted to distribution shifts and avoided falsely flagging D0 during a tenfold arrival-rate spike, whereas tuple-at-a-time sampling absorbed the noise and flagged it.Both adaptive reservoirs tracked the distribution change by 170 seconds; the uniform reservoir adapted more slowly.Source: §6.1 · p. 10, Figure 5 · p. 10
  • During production use at CMT, MacroBase surfaced previously unknown trip-detection, application, and device-battery issues that investigation confirmed and that were subsequently addressed.The paper also reports production use across other domains, including mobile devices, datacenter telemetry, automotives, and manufacturing.Source: §6.1 · p. 10

6.2 End-to-End Performance

  • Table 2 reports throughput up to 2.5M points per second; average throughput was 1.39M for one-shot execution and 599K for EWS, up to three orders faster than related techniques.Generating explanations at query end added approximately 22% overhead, and throughput varied by dataset and query.Source: §6.2 · p. 10, Table 2 · p. 11

6.3 Microbenchmarks and Comparison

  • AMC outperformed both SpaceSaving implementations by up to 500×, while cardinality-aware explanation was 3.2× faster on average than separate FPGrowth runs.AMC sustained over 10M updates per second with a 10K-point update period, but retained more items than SpaceSaving; MacroBase and FPGrowth both require a linear pass over inliers.Source: §6.3 · pp. 10–11, Figure 6 · p. 11

6.4 Case Studies and Extensibility

  • A hybrid CMT pipeline combined unsupervised detection with a rule-based diagnostic-score classifier, identifying additional behaviors without affecting runtime.The pipeline logically ORed the two classification results, and the authors note it can be extended to more complex supervised models.Source: §6.4 · p. 11
  • Time-series transforms surfaced a refrigerator’s abnormal 12–1 PM behavior, while optical-flow features exposed a three-second fight; in both cases, feature transformation dominated runtime.The STFT transformed 16M points in 516 seconds; the video transform took 22 seconds versus 34ms for MDP.Source: §6.4 · pp. 11–12

7. RELATED WORK

MacroBase builds on streaming dataflow and specialized analytics systems but focuses on high-level operators for classifying and explaining fast data. The authors position streaming explanations as a gap among prior explanation techniques and use sketching to support high-volume execution.

Streaming and Specialized Analytics

  • Prior streaming engines provide execution infrastructure, while MacroBase uses dataflow as a substrate for specialized classification and explanation operators.The authors connect this approach to specialized systems such as Gigascope, WaveScope, MCDB, and Bismarck.Source: §7 · p. 12

Classification

  • Although many outlier-detection methods operate on streams, high-volume outlier detection must be coupled with streaming explanation to make its output useful.MacroBase’s modular architecture is compatible with detectors from Elki, Weka, RapidMiner, and OpenGamma.Source: §7 · p. 12

Data explanation

  • The authors say prior explanation techniques do not operate at their target streaming scale, so MacroBase adapts sketches and streaming data structures for explanations.They frame existing explanation techniques as a possible second analysis step after MacroBase’s streaming summaries.Source: §7 · p. 12

8. CONCLUSIONS AND FUTURE WORK

MacroBase combines streaming classification and explanation in a flexible analytics engine for fast data. Its default sampling and sketching operators target performance and result quality, and production deployments have identified previously unknown behaviors.

8. CONCLUSIONS AND FUTURE WORK

  • MacroBase combines streaming classification and data explanation to produce interpretable summaries of important behavior in fast data streams.Its default operators use new sampling and sketching procedures, optimized for high-volume, time-sensitive, heterogeneous streams.Source: §8 · p. 12
  • The system remains under active development, with ongoing work on temporal explanation, heterogeneous sensor fusion, online density estimation, and contextual outlier detection.The authors say ongoing production use cases continue to stimulate functionality for additional domains.Source: §8 · p. 12

A. CLASSIFICATION

This appendix describes classification-related techniques and choices, including an approximation for robust covariance estimation and policies for sampling under variable arrival rates.

A. CLASSIFICATION

  • Exact MCD is computationally intractable even for modest datasets, so MacroBase uses iterative FastMCD C-steps until the covariance determinant change converges.The system uses corr-max to determine which dimensions are most anomalous in MCD.Source: A. CLASSIFICATION · p. 14
  • For variable ADR arrival rates, one policy takes a uniform sample per decay period; another samples uniformly over time and applies decay by time.The per-period policy combines an ADR for prior periods with a uniform reservoir for the current period, then inserts the period sample at its end.Source: A. CLASSIFICATION · p. 14
  • The contamination experiment varies the inlier and outlier proportions in a 10M-point dataset to test Z-Score, MAD, and MCD.The data comprise uniform inliers centered at the origin and uniform outliers centered at (1000, 1000); Z-Score and MAD use univariate points.Source: A. CLASSIFICATION · p. 14

B. EXPLANATION

MacroBase’s explanation pipeline uses a modified prefix tree to track frequent attribute combinations and provides confidence intervals for risk-ratio explanations. It addresses repeated-testing false positives and examines how large streams affect interval quality.

Streaming combinations: CPS-tree adaptation

  • M-CPS-tree retains only items frequent in the previous window, removing stale items at window boundaries instead of accumulating every item ever observed.Counts are updated using the AMC sketch, then decayed and the tree reordered.Source: B. EXPLANATION · p. 14

Confidence

  • A risk ratio of 5 at 1% support among 10M points has a 95th-percentile confidence interval of (3.93,6.07), supporting a threshold of 3.The passage also reports a 99th-percentile interval of (3.91,6.09).Source: B. EXPLANATION · p. 14
  • MDP can count support computations to estimate k and adjust confidence intervals because repeated tests can produce false positives.The Bonferroni correction adjusts the confidence level according to the number of combinations tested.Source: B. EXPLANATION · p. 14
  • With k = 10M, a 10M-point dataset yields a 95th-percentile interval of (3.80,6.20), while 1,000 points yield (0,106M).The paper says large fast-data streams can mitigate many problems associated with multiple testing.Source: B. EXPLANATION · p. 14

C. IMPLEMENTATION

The MacroBase prototype uses a custom single-core dataflow engine and is implemented primarily in Java. The prototype lacks fault tolerance, while hand-optimized C++ outperforms its Java implementation on simple queries.

Implementation

  • As of February 2017, MacroBase’s core comprised approximately 9,400 lines of Java, alongside 1,000 lines of front-end code and 7,600 lines for diagnostics and prototype pipelines.The prototype and evaluated code were released under a permissive open-source license.Source: C. IMPLEMENTATION · pp. 14–15

Implementation performance

  • Hand-optimized C++ has an average throughput gap of 12.76× over Java MacroBase for simple queries.Table 3 reports speedups of hand-optimized C++ over the Java prototype for Section 6 queries.Source: Table 3 · p. 15, C. IMPLEMENTATION · p. 15

Dataflow execution

  • MacroBase runs operator pipelines through a custom single-core dataflow engine that pushes tuples between producers and consumers and amortizes calls across several thousand points.Its API supports sequential or batched scheduling, stream multiplexing, and compatibility with engines including Storm, Heron, and Amazon Streams.Source: C. IMPLEMENTATION · p. 15

Limitations

  • The prototype has no fault tolerance and currently runs one query per core.The paper notes that state-based checkpointing techniques are applicable and reports preliminary multi-core scale-out results in an appendix.Source: C. IMPLEMENTATION · p. 15

D. EXPERIMENTAL RESULTS

Experiments evaluate MacroBase on public and production datasets, including accuracy, explanation runtime, and sampled model training. Results show fast explanation and sampling, while also documenting sensitivity to data dimensionality and the limits of available ground truth.

Dataset descriptions

  • The evaluation includes public datasets without ground-truth labels, and the authors verified several query explanations on the CMT production dataset.The public datasets are described as representative of scale and behaviors encountered in production data beyond CMT.Source: D. EXPERIMENTAL RESULTS · p. 15

Score distribution

  • At the 99th percentile and above, a very small fraction of points have outlier scores over 150, which MDP highlights as extreme behavior.Figure 7 presents the score CDFs across the real-world dataset queries.Source: D. EXPERIMENTAL RESULTS · p. 15, Figure 7 · p. 15

Varying support and risk ratio

  • Changing support beyond 0.01% had limited runtime impact, while changing risk ratio affected runtime by less than 40% and changed summary counts by an order of magnitude.The default support and risk-ratio settings are described as a sensible trade-off between summary count and runtime; Figure 8 plots these outcomes.Source: D. EXPERIMENTAL RESULTS · p. 15, Figure 8 · p. 15

Operating on samples

  • MAD precision and recall were largely unaffected by sampling, enabling a two-order-of-magnitude speedup, while MCD accuracy was somewhat more sensitive to sample variance.The paper says regular retraining partially offsets MCD’s sampling variance; Figure 9 plots accuracy against sample size.Source: D. EXPERIMENTAL RESULTS · p. 15, Figure 9 · p. 16

Metric scalability

  • MCD training and scoring throughput is linearly affected by data dimensionality, encouraging dimensionality reduction for complex data.Figure 10 shows MCD throughput versus metric size on Gaussian data.Source: D. EXPERIMENTAL RESULTS · p. 15, Figure 10 · p. 16

Explanation algorithms

  • MacroBase’s cardinality-aware explanation completes fastest for all queries compared with the evaluated explanation algorithms.Table 5 reports running times for complex queries across the compared algorithms.Source: D. EXPERIMENTAL RESULTS · p. 16, Table 5 · p. 16

Compatibility with existing frameworks

  • Alternative kNN operators were over 100× slower than MDP’s, and SPMF’s summarizer was 2.8× slower than MacroBase.The evaluated packages lacked streaming operation; the passage attributes SPMF’s gap to MDP’s cardinality-aware optimizations.Source: D. EXPERIMENTAL RESULTS · p. 16
Loading 1603.00567v4…