PaperlayerView exact revision on arXiv

Source-linked AI summary

RankShift: In-Database Detection and Explanation of Categorical Shifts

Omair Shafi Ahmed

arXiv:2608.28922v1cs.LG

TL;DR

Aggregate event rates can remain stable while categorical composition shifts sharply, motivating detection that identifies which categories changed. RankShift compares window shares with a benign reference using Pearson contributions, returning a calibrated alert and ranked drivers inside the analytical database. Across labeled logs and fixed-volume experiments, it is competitive with or better than the count-vector autoencoder while requiring no model training or inference service.

  • Problem

    Aggregate monitoring can miss sharp changes in categorical composition when total event volume remains stable.

  • Method

    RankShift computes Pearson category contributions against a benign reference, calibrates alerts with benign scores, and returns ranked increasing contributors inside the analytical database.

  • Results

    RankShift matches the autoencoder within 0.001 AUROC on HDFS, leads on Thunderbird, and reaches 0.787 versus 0.771 AUROC for rare-category fixed-volume shifts.

  • Takeaways & Limitations

    RankShift provides category-level drivers with low-latency in-database monitoring and no trained detector or separate explanation system.

Abstract

from arXiv · show

A login service can receive its usual number of failed sign-ins while one source grows from 2% to 30% of them. The same pattern appears in system logs when a rare event template becomes common while the message rate stays stable. These events change which categories are active without changing how many events occur. RankShift detects such changes inside the analytical database that stores the data. It compares each window's category shares with a benign reference using a Pearson score whose terms identify the categories responsible for the change. The same query returns the score, calibrated alert, and largest increasing contributions. We evaluate RankShift on HDFS, BGL, and Thunderbird. It matches the count-vector autoencoder within 0.001 AUROC on HDFS (0.999 versus 1.000) and leads on Thunderbird (0.983 versus 0.949). In a controlled fixed-volume experiment, RankShift detects rare-category shifts that are invisible to event-count monitoring, reaching 0.787 AUROC compared with 0.771 for the autoencoder. Across all three corpora, observed false-alarm rates track the requested operating levels. RankShift requires no model training or inference service, and the autoencoders deployed state is 137x larger.

I. INTRODUCTION

RankShift addresses categorical composition changes that aggregate monitoring can miss, providing detection and category-level explanations inside analytical databases. The paper evaluates its monitoring, calibration, database execution, and comparison with existing detectors.

  • Motivation: Stable request rates, error counts, or latency can conceal sharp changes in source, route, event-template, or error-code shares.Such composition changes may indicate an emerging source, failing component, or new workload pattern.
  • Related work: Distribution-change methods and log detectors use dedicated streaming, fitting, or sequence-prediction pipelines outside the analytical event table.Related approaches include count-vector, sequence, and distribution-monitoring detectors.
  • Approach: RankShift scores category-level Pearson contributions, calibrates alerts using benign score ranks, and identifies categories driving the change.Its contributions indicate which categories gained or lost share.
  • Evaluation: The evaluation covers three real log datasets and fixed-total shifts comparing RankShift with a count-vector autoencoder.The study also measures correctness, scaling, setup, online cost, and deployed state across equivalent implementations.
  • Positioning: Existing explainers generally attribute results after another detector produces an anomaly score, whereas RankShift computes category contributions within detection.In-database analytics motivates returning both the alert and decomposition where the data is stored.
  • Calibration: Conformal calibration converts benign score ranks into an alert operating level without assuming a parametric score distribution.The calibration compares new scores with held-out benign examples.

III. RANKSHIFT

RankShift maps categorical values into a fixed vocabulary and builds a smoothed benign reference distribution. Smoothing keeps every reference share positive, including categories absent from benign history.

  • Categories: RankShift monitors one categorical field in timestamped events grouped into fixed time windows.Each field value is mapped to one of C categories before monitoring begins.
  • Categories: Unstructured logs can use a frozen parser-template dictionary or fixed-size hash mapping, with unmapped values assigned to OTHER.The mapping controls how precisely drivers can be identified because merged values receive one combined contribution.
  • Reference shares: Benign history supplies reference counts ri and total R for the expected category mix.These counts are converted into reference shares for later window comparisons.
  • Reference shares: A pseudocount spread across all C categories prevents zero reference shares from invalidating the Pearson score.Zero shares cannot be used because the score divides by the reference share.
  • Reference shares: The smoothed shares qi are positive, sum to one, and use τ = 1 as total smoothing mass.Each category receives τ/C, so the total smoothing is independent of vocabulary size.

B. Window score and category contributions

RankShift compares each window’s category shares with benign reference shares using a Pearson divergence whose nonnegative terms both form the score and identify responsible categories. Normalization isolates composition changes from uniform traffic changes, while conformal ranks calibrate alerts.

  • Window score: For a window with N events, RankShift computes observed shares pi = si/N and compares them with reference shares qi.The comparison uses category counts within each fixed window.
  • Window score: Each category contribution ci = (pi − qi)^2/qi is nonnegative, and the complete set sums exactly to the Pearson score X.Rare reference categories receive larger contributions for the same share change because qi is in the denominator.
  • Category contributions: The squared score loses direction, so RankShift separately records whether pi − qi is positive for gained share or negative for lost share.This preserves directional interpretation without changing the nonnegative score.
  • Category contributions: RankShift reports the k largest contributions among categories whose shares increased, while retaining other categories in the full table.The ranked view excludes lost-share categories and contributions below rank k.
  • Operational scope: Uniform growth or shrinkage leaves category shares, contributions, and score unchanged, so RankShift detects redistribution rather than total-volume change.A separate volume monitor is required for traffic surges or drops that preserve category shares.
  • Alert calibration: Conformal calibration compares a new score X with benign calibration scores and raises an alert when bp ≤ α.The finite-sample rank includes the new score and counts calibration ties against the alert.

IV. DATABASE EXECUTION

RankShift executes scoring, calibration, alerting, and driver ranking through database operations without model training or inference. Its sparse implementation reuses grouped counts, preserves exact score semantics, and matches the NumPy reference across query engines.

  • Execution: RankShift’s deployed state contains reference shares and calibration scores or a fixed alert cutoff, with no model training, learned weights, inference runtime, or GPU requirement.Each event increments one category count, and sparse scoring uses O(a) work for a windows with a active categories.
  • Execution: The database materializes grouped counts once so reference construction, scoring, calibration, and driver ranking reuse the same aggregation.This avoids rescanning raw events across pipeline stages.
  • Execution: Sparse evaluation computes the exact score using only categories present in the window, assigning absent-reference categories the smoothed floor.This avoids dense C-row expansion while preserving the score.
  • Outputs: The query returns the window score, conformal p-value, alert, and largest increasing category contributions.It filters increased shares, orders by contribution and category identifier, and returns the largest k.
  • Reproducibility: RankShift separates the unrounded reported score from a six-decimal rounded copy used for cross-engine alert decisions.The rule addresses floating-point differences near ties and alert boundaries.
  • Reproducibility: DuckDB and ADX matched NumPy p-values, alerts, contribution values, and category ordering, with maximum score differences of 3 × 10^-8 and 8 × 10^-9.The comparison used a 30-window BGL fixture and exact-boundary tests.

V. EVALUATION

The evaluation uses fixed category vocabularies and disjoint benign cohorts to test detection, alert calibration, execution, and information preservation across several datasets. HDFS, BGL, and Thunderbird provide the main labeled-log evaluation settings.

  • Evaluation scope: The evaluation covers anomaly detection and false-alarm calibration on HDFS, BGL, and Thunderbird, plus native query execution and bounded category mapping on CTU-13.The fixed-total experiment isolates composition changes from volume changes.
  • Datasets: HDFS contains 575,061 block samples over 29 event identifiers, while BGL and Thunderbird are grouped into 3,619 hourly and 30,120 one-minute windows.HDFS labels blocks; BGL and Thunderbird label windows containing at least one anomalous message.
  • Datasets: Category vocabularies are fixed before testing: BGL uses 644 categories, and Thunderbird retains 1,024 frequent benign templates plus OTHER.Mappings are learned from pre-test data and then applied unchanged throughout second-half tests.
  • Protocol: Detection comparisons use shared fitting data and test samples, with time-ordered first-half setup for BGL and Thunderbird and paired random splits for HDFS.The autoencoder receives the same category-count vectors as RankShift.
  • Protocol: Alert calibration separately uses disjoint benign reference, calibration, and test cohorts to measure false alarms under later operating distributions.No test label influences the reference or calibration scores.

B. Detection and alert calibration on labeled logs

On labeled logs, RankShift is competitive with the autoencoder overall, while controlled redistribution shows that its sensitivity depends on whether shifted activity enters rare or common categories. Calibrated alert rates and detection rates vary by dataset and operating level.

  • Labeled-log results: 0.999 versus 1.000 AUROC on HDFS, 0.699 versus 0.864 on BGL, and 0.983 versus 0.949 on Thunderbird compare RankShift with the autoencoder.The opposing BGL and Thunderbird results motivate the fixed-total experiment.
  • Alert calibration: 0.041, 0.038, and 0.046 observed false-alarm rates on HDFS, BGL, and Thunderbird occur at the requested 0.05 level.Detection rates on BGL rise from 0.490 to 0.760 between α = 0.01 and α = 0.05, while Thunderbird rises from 0.024 to 0.213.
  • Controlled redistribution: 0.787 versus 0.771 AUROC favors RankShift over the autoencoder when all transferred events enter rare recipients in the fixed-total experiment.Every synthetic anomaly has the same event count as its original benign window.
  • Controlled redistribution: 0.500 AUROC is the volume-only baseline because fixed-total synthetic anomalies and their benign originals have identical event counts.The controlled setup therefore isolates composition from volume.
  • Controlled redistribution: RankShift responds most strongly when activity moves into categories rare in benign history and loses sensitivity when redistribution is confined to common categories.Its Pearson contributions divide changes by benign reference shares, giving larger contributions to equally sized changes in rarer categories.

D. Execution and cost

RankShift’s complete query scales to tens of millions of events in DuckDB and ADX, while matched same-process measurements show lower scoring, setup, and deployed-state costs than the autoencoder.

  • 12.2 seconds is the DuckDB median query time at 64 million events, up from 0.428 seconds at 0.64 million events.The complete query includes scoring, conformal p-value calculation, alerting, and five largest increasing contributions.
  • 11.000 seconds is the ADX median query time at 64 million events, up from 0.900 seconds at 0.64 million events.The largest ADX run processes approximately 5.8 million events per second.
  • 5.09 GiB and 9.00 GiB are the peak memory measurements for DuckDB and ADX, respectively, at 64 million events.ADX memory is measured per node.
  • 19.5 microseconds versus 43.5 microseconds is the median scoring time for RankShift and the autoencoder in the matched same-process benchmark.Both methods return a score, conformal p-value, alert, and five ranked categories.
  • 0.009 seconds versus 2.279 seconds is the median setup time for RankShift and the autoencoder, while RankShift retains 137× less deployed state.RankShift retains 5,160 bytes versus 706,264 bytes for the autoencoder.

VI. OPERATIONAL SCOPE

RankShift targets categorical-composition changes rather than uniform traffic changes, with operating behavior bounded by window consistency, reference drift, and vocabulary resolution.

  • Uniform growth or shrinkage across all categories leaves RankShift’s score unchanged, so total-traffic changes require a separate volume monitor.The method normalizes windows by total event count and scores category shares.
  • Reference, calibration, and monitored windows should use the same duration and similar event-volume ranges so calibration reflects normal sampling variation.Window size controls how much category shares vary under normal conditions.
  • 0.923 AUROC under a random held-out split fell to 0.699 when an older BGL half defined the reference and the later half was tested.Reference shares and calibration scores should be refreshed when sustained benign changes alter the operating distribution.
  • 0.228 versus 0.644 is RankShift’s recovery of true attack sources among its first five candidates compared with current-count ranking across CTU-13 attack windows.All labeled attack sources were absent from the 2,048-address reference vocabulary and mapped to OTHER, which RankShift cannot resolve to individual addresses.
  • RankShift provides exact category-level drivers at the deployed vocabulary’s resolution, while values merged into OTHER require a finer or hierarchical representation.Its complete calculation runs inside the analytical database without a trained detector or separate explanation system.

APPENDIX A SUPPORTING IDENTITIES

The query evaluates RankShift’s exact Pearson score using only categories present in each window. Vocabulary aggregation preserves exactness for the deployed categories but can conceal finer raw-value changes through cancellation.

  • Terms with p_i = 0 disappear, so the query evaluates the exact score using only categories present in the current window.
  • For a merged category, its contribution cannot exceed the sum of the original category contributions.
  • Increases and decreases among values merged into OTHER can cancel before scoring, motivating hierarchical refinement of anomalous groups.

APPENDIX B DUCKDB IMPLEMENTATION

The DuckDB implementation builds reference and observed category shares, computes exact sparse scores, and returns calibrated alerts with ranked increasing drivers.

  • The query constructs reference shares, calculates exact sparse scores, assigns conformal p-values, produces alerts, and ranks increasing category contributions.
  • Counts are grouped by role, window, and category before window totals and reference-category totals are computed.
  • Reference shares apply smoothing mass τ across the configured vocabulary before observed category shares are joined to them.
  • The score is computed as the nonnegative sum of p²/q terms minus one, then rounded to a configured precision for ranking and calibration.
  • Increasing drivers are ranked by (p−q)²/q, with only test categories having p > q eligible for the top-driver output.

ROW_NUMBER() OVER (PARTITION BY w

The implementation ranks increasing category contributions, calibrates test scores against calibration scores, and emits alerts when conformal p-values meet the configured threshold.

  • Increasing drivers are ordered by their normalized squared deviations, and only categories with p > q are retained.
  • The top-driver result keeps categories whose driver rank is at most the configured top_k value.
  • Calibration scores are taken from calibration windows, while test scores receive p-values by counting calibration scores at least as large as each test score.
  • A test window is marked as an alert when its p-value is less than or equal to the configured α threshold.
Loading 2608.28922v1…