ConeForest

An isolation-style anomaly detector that is one table lookup per tree

Summary

ConeForest is a random-partition anomaly detector built to run as a few array operations on a GPU. On 48 tabular datasets it is as accurate as Isolation Forest, xStream and Half-Space Trees: no test separates the five. It is much faster than all of them.

Model ROC-AUC AUC-PR Speed against ConeForest
iForest (sklearn)0.7670.401157× slower
iForestGPU (cuML)0.7650.41112.5× slower
ConeForest0.7640.3980.7 ms on small sets
xStreamGPU (our JAX port)0.7620.39717× slower
HSTreesGPU (our JAX port)0.7610.3972.8× slower

What the study found beyond the headline:

  • It is not more accurate. The claim is “same accuracy, far less time”.
  • The score matters more than the partition. In a step-by-step ablation from xStream to ConeForest, only one step is significant: replacing xStream’s score with ConeForest’s (+0.018 ROC-AUC). The speed comes from a different step, which gives most of that gain back.
  • The score splits into a density part and a geometry part. The geometry part is a built-in “distance from the centre of the range” penalty. Synthetic checks confirm it to a rank correlation of 0.992.
  • Where the cuts are drawn decides what kind of anomaly is found. Cuts uniform in the range find far-out magnitudes. Cuts at sample quantiles ignore the marginals and find broken dependence. Each fails at the other’s task.
  • One approximation in our theory sketch failed its check, and we say where.

The implementation is available as a Python package: coneforest 0.1.0 on PyPI; the source is at git.sr.ht/~divanov/coneforest.

The design

ConeForest is an ensemble of b = 256 random oblivious trees. Oblivious means every node at a given level uses the same feature and the same threshold. A tree of depth K is then just K (feature, threshold) pairs, and a row’s leaf is a K-bit code.

Fit, per tree:

  1. Draw psi training rows (tuned over {128, 256, 512}; all rows if there are fewer).
  2. Set the depth to K = ceil(log2(m)), with m the sample size. That is 7 to 9.
  3. For each of the K levels, draw a feature with replacement, and a threshold uniform in that feature’s [min, max] over the tree’s sample. Cuts are in raw feature space, with no scaling or rank transform.
  4. Give every sample row its K-bit code: bit j is 1 when the row is above threshold j. Count rows per code. The low j bits of a code are the row’s cell at depth j, so summing the count table over the high bits gives the counts at every depth.
  5. For each cell at each depth, take the smoothed log mass log((count + 1) / (m + 2)).
  6. For each of the 2^K full codes, store one number: minus the mean of the log masses of its K prefix cells.

Score a row: compute its K-bit code in each tree, look up the stored number, and average over trees.

score(x) = mean over trees and depths l = 1..K of −log((countl(x) + 1) / (m + 2))

count_l(x) is the number of the tree’s sample rows in x’s cell after l cuts. High score means few rows share x’s cells, at every scale.

The core is short. This is the build, in JAX, lightly trimmed:

feats = random.randint(k_feat, (b, K), 0, d)
S = X[sub[:, :, None], feats[:, None, :]]                      # (b, m, K)
lo, hi = S.min(axis=1), S.max(axis=1)
thr = lo + random.uniform(k_thr, (b, K)) * (hi - lo)

weights = (1 << jnp.arange(K)).astype(jnp.int32)
codes = jnp.sum((S > thr[:, None, :]) * weights, axis=2)       # (b, m)
table = jnp.zeros((b, 1 << K), jnp.int32).at[jnp.arange(b)[:, None], codes].add(1)
flat = jnp.concatenate(
    [table.reshape(b, 1 << (K - j), 1 << j).sum(axis=1) for j in range(1, K + 1)], axis=1
)
log_mass = jnp.log((flat + 1.0) / (m + 2.0))

and this is all of scoring:

codes = jnp.sum((X[:, feats] > thr[None]) * weights, axis=2)   # (n, b)
return jnp.mean(cell_score[jnp.arange(b)[None, :], codes], axis=1)

Why it is fast.

  • Fitting touches b × psi rows, whatever the size of the training set.
  • Scoring a row costs b × K comparisons and b table lookups. There is no tree traversal and no branching, so it batches as one gather.
  • The model is small: b × K features and thresholds, and a b × 2^K score table (at most 256 × 512 numbers).

How it differs from its relatives.

Tree shape Cut Rows counted Score
iForestper-node feature and cutuniform in the node’s rangesubsamplepath length to isolation
HS-Treesper-node featuremidpoint of the node’s workspacereference rowsmass × 2^depth at the terminal node
xStreamoblivious, on random projectionsequal-width grid, halved on each reuse of a featureall training rowsmin over depths of log2(1 + count) + depth
ConeForestoblivious, raw featuresone uniform cut per level in the sample’s rangesubsample of psimean over depths of −log mass

xStream’s half-space chains are the closest prior work: they are also oblivious and also draw features with replacement. ConeForest’s differences are the binary random-threshold cut, the per-tree subsample, the mean-of-log-mass score, and the lookup table.

How we evaluated

  • Data. 48 datasets: the 47 “classical” tabular datasets of ADBench, plus arrhythmia.
  • Splits. 10 runs per dataset. Each run splits 60 / 20 / 20 into train, validation and holdout within each class, so every part has anomalies. Models fit on the training part without labels; it contains anomalies.
  • Tuning. 10 Optuna trials per model per run, choosing the setting with the best ROC-AUC on the validation part. The search spaces are small: ConeForest psi in {128, 256, 512}; iForest 100 to 200 trees and 256 or “auto” samples; xStream depth in {10, 15, 25}; HS-Trees ψ in {125, 250, 500}. COPOD has nothing to tune.
  • Metrics. ROC-AUC and AUC-PR (average precision) on the holdout part, averaged over runs, then over datasets.
  • Statistics. Models are ranked per dataset on their mean score. We report the Friedman test, the Nemenyi critical difference, and pairwise Wilcoxon signed-rank tests over datasets with Holm correction.
  • Timing. Fit plus scoring of the holdout part with the tuned setting, median of 10 runs. JAX compile time is not included. All models run on the GPU, except sklearn’s iForest.

Baselines. sklearn’s IsolationForest is the reference. cuML’s GPU IsolationForest is the fair speed comparison. COPOD, xStream and HS-Trees are our own JAX ports, so that every method gets the same GPU treatment:

  • COPOD follows pyod’s implementation; scores match pyod’s to 3e-7.
  • xStream follows the authors’ python/Chains.py: exact counts, 100 chains, projection to 100 features. It runs in static mode and counts every training row.
  • HS-Trees follows the IJCAI 2011 paper’s terminal-node score, with 100 trees, each of depth 15. The reference counts come from ψ training rows, not a stream window.

Both tree ports were checked in float64 against the reference code (all 16 checks pass). On the http dataset, the float32 GPU path gave 0 count mismatches in 900,000 cells.

Results

Accuracy

Model ROC-AUC AUC-PR
iForest0.7670.401
iForestGPU0.7650.411
ConeForest0.7640.398
xStreamGPU0.7620.397
HSTreesGPU0.7610.397
COPODGPU0.7460.357
Critical difference diagram for ROC-AUC over the 48 datasets, Nemenyi CD = 0.88. Mean ranks: iForestGPU 2.76, iForest 2.77, ConeForest 2.78, HSTreesGPU 3.26, xStreamGPU 3.43; a single thick bar joins the first three.
Critical difference diagram, ROC-AUC.
Critical difference diagram for AUC-PR over the 48 datasets, Nemenyi CD = 0.88. Mean ranks: ConeForest 2.82, iForestGPU 2.86, HSTreesGPU 2.92, iForest 3.08, xStreamGPU 3.31; one group joins ConeForest, iForestGPU and HSTreesGPU.
Critical difference diagram, AUC-PR.

There is no detectable difference among the five tree methods.

ConeForest iForest iForestGPU xStreamGPU HSTreesGPU Friedman p
Mean rank, ROC-AUC2.782.772.763.433.260.095
Mean rank, AUC-PR2.823.082.873.312.920.54

The Nemenyi critical difference is 0.88, larger than any gap in mean rank. No pairwise Wilcoxon-Holm test is significant.

Speed

  • Against iForest. ConeForest is faster on all 48 datasets: 157× faster than sklearn’s iForest (21 to 350×), and 12.5× faster than cuML’s (2.9 to 19×).
  • Absolute times. About 0.7 ms on small datasets, 2.3 ms on those over 100,000 rows, and 35 ms on census (500 columns).
  • Against the GPU ports. Taking the per-dataset ratio of median times and the geometric mean over datasets, xStreamGPU is 17× slower (4.3 to 6400×) and HSTreesGPU 2.8× slower (0.95 to 4.6×; slower on 47 of 48). xStream counts every training row, so it takes 0.6 to 14.6 s on the seven datasets over 200,000 rows.

Where ConeForest loses

  • http, AUC-PR. 0.425 against 0.95 to 0.995 for the others, at the same ROC-AUC of 0.995. The anomalies are 22 distinct rows with src_bytes at the top of its range. ConeForest’s top ranks fill with normal rows from the tail of dst_bytes instead. Ties do not explain it, and neither does contamination of the training data. An open hypothesis: one global threshold per level is coarser than iForest’s cuts, which adapt to each node’s range.
  • Wilt. 0.362 ROC-AUC against 0.467.
  • optdigits and landsat. 0.05 to 0.07 below.

Ablation: which part of ConeForest matters?

We walked from xStream to ConeForest one change at a time, on the same 48 datasets and protocol. Steps A1 to A3 keep xStream’s 100 chains, count every training row, and tune depth over {10, 15, 25}. The p-values are two-sided Wilcoxon tests of ROC-AUC against the previous step.

Step ROC-AUC AUC-PR Median time Against the previous step
A0 xStreamGPU0.7620.3974.7 ms
A1 no projection (raw features)0.7630.3973.8 ms31/48 wins, p = 0.13
A2 + ConeForest’s score0.7810.4043.8 ms30/48, p = 0.007 (Holm 0.037)
A3 + one uniform binary cut per level0.7740.4093.3 ms19/48, p = 0.12
A4 + psi rows per tree, depth ceil(log2 psi), 100 trees0.7620.3960.6 ms18/48, p = 0.047 (Holm 0.19)
A5 ConeForest, 256 trees0.7640.3970.6 ms26/48, p = 0.14
ConeForest with mirrored cuts0.7700.3990.55 msagainst ConeForest: 21/48, p = 0.35
  • The score is the one significant step. Swapping xStream’s min-over-depths for the mean of −log mass adds 0.018 ROC-AUC and survives Holm correction. landsat, skin and fault gain about 0.11 each. No step changes AUC-PR significantly.
  • The subsample gives the speed and costs accuracy. A4 takes the median from 3.3 ms to 0.6 ms (A2 needs 14 s on donors) and loses 0.012 ROC-AUC.
  • A4 is not one change. Besides the subsample it changes the depth, the range the cuts are drawn from, and the scoring path (table lookup instead of a search over all rows). These effects are not yet separated.
  • A2 is not a clear winner over ConeForest. It beats ConeForest on only 23 of 48 datasets (p = 0.24). A few large gains drive its mean.
  • Removing xStream’s projection makes no significant difference (p = 0.13).

The open engineering question follows directly: a variant that keeps A2’s score gain at A4’s speed.

Uniform, quantile and mirrored cuts

We tried two other ways to place thresholds, on the same splits.

  • Quantile cuts. The threshold is the midpoint of two neighbouring sorted sample values, at a uniformly random rank.
  • Mirrored cuts. Half the trees use uniform cuts and half use quantile cuts. Each pair shares its sample, features and random draws.
Cuts ROC-AUC AUC-PR
Uniform (ConeForest)0.7640.398
Quantile0.7630.361
Mirrored0.7700.399

None of these differences is significant (quantile against uniform: p = 0.52 on ROC-AUC, p = 0.11 on AUC-PR; mirrored against uniform: p = 0.35). The means hide large moves on single datasets:

  • Quantile cuts help Wilt (0.36 → 0.57 ROC-AUC), donors, PageBlocks, backdoor, skin and vowels.
  • They hurt http (AUC-PR 0.425 → 0.131), WDBC, musk, shuttle, thyroid and Stamps.
  • Mirrored cuts land between the two on 36 of 48 datasets, at the same run time.

The two schemes look complementary. The theory sketch below says why.

Theory sketch: the score through Sklar’s theorem

This is a sketch, not a proof. Each step is marked exact or heuristic, and the checks in the next section test it.

Setup. X in ℝd has density f, marginal CDFs Fj with densities fj, and copula density c. Sklar’s theorem: f(x) = c(F1(x1), …, Fd(xd)) · Πj fj(xj). A tree draws features j1…jK with replacement and thresholds t1…tK. Al(x) is the cell of x after l cuts, an axis-aligned box. The population score is

S(x) = Etree[(1/K) Σl −log P(Al(x))]

The code’s (count + 1) / (m + 2) is the posterior mean of P(Al) under a uniform prior.

1. Mass = average density × volume (exact). For any box A, P(A) = f̄A · vol(A), with f̄A the mean of f over A. So −log P(Al(x)) = −log f̄Al(x) − log vol(Al(x)). The volume is a product of interval lengths, so its log is a sum over features:

S(x) = [−log of the cell-averaged f, over scales] + Σj h(position of xj)

  • h(t) = E[−log length of the interval around t]. It depends only on how cuts are drawn, not on the data.
  • With one uniform cut on [0, 1], h(t) = 1 − H(t), with H the binary entropy in nats. It is U-shaped: 0.31 at the centre, 1 at the edges.
  • With many cuts per feature, h flattens to a constant in the interior. ConeForest has about 8 cuts spread over d features, so it sits in the few-cuts regime and the U-shape matters.

So the score has a data-free geometry term: a bounded penalty for sitting near the edge of the range.

2. Quantile cuts see only the copula (exact at population level). Take thresholds at Fj−1(v), with v uniform. In rank coordinates u = F(x) the cuts are uniform on [0, 1]d, and a cell’s mass is the copula’s mass of a box:

SQ(x) = [−log of the cell-averaged c at u, over scales] + Σj h(uj)

The score depends on the copula and the ranks only. The marginals drop out. The geometry term stays, as a bounded, distribution-free penalty on extreme ranks.

3. Uniform cuts see the full density (heuristic: small cells). Rescale each feature to z in [0, 1] by its range. The same identity holds with f in place of c:

SU(x) ≈ −log c(u) − Σj log fj(xj) + Σj h(zj)

4. Mixing gives tempered marginals (heuristic). With a fraction λ of uniform-cut trees and 1 − λ of quantile-cut trees:

Sλ(x) ≈ −log c(u) − λ Σj log fj(xj) + geometry

This is −log of c · Πj fjλ: the joint density with its marginals tempered. λ = 1 is ConeForest, λ = 0 is quantile cuts, λ = ½ is mirrored cuts. Mixing tree types only reaches λ in [0, 1].

5. Why the mean of logs should beat xStream’s min (a claim to prove).

  • Telescoping: −log P(Al) = Σi≤l −log P(Ai | Ai−1). The mean over depths is then Σi wi · (surprisal of cut i), with wi = (K − i + 1) / K. The score is a weighted code length for locating x, with early cuts weighted most.
  • xStream’s score is the min over depths of log2(1 + count) + depth. Once a cell is empty, this is roughly the depth at which x is isolated. It uses one extreme value, so it takes few distinct values and ties often.
  • The claim: the mean uses all K levels with bounded terms, so it has lower variance and finer resolution than the min. This is the ablation’s A1 → A2 step, and it is not yet proven.

Caveats.

  • With d much larger than K, a tree cuts at most K features. The rest integrate out, so each tree scores a random low-dimensional marginal. Only dependence among up to K features is ever seen.
  • This is not a consistent density estimator: K = log2 m leaves about one row per deepest cell. The honest theorem is concentration of the score around S(x) as trees grow, not convergence to −log f.
  • Empirical quantile cuts are midpoints of sample values, so invariance to monotone maps may be only approximate in finite samples.

Testing the sketch on synthetic data

Each check uses 256 trees of 256 rows and 20,000 training rows. Correlations are Spearman on 4,000 test rows. AUC-PR checks score 20,000 test rows and average 3 seeds.

The geometry term is real. With independent features and five different marginals (normal, lognormal, uniform, exponential, t3):

Comparison Spearman
Quantile score against the predicted geometry term0.992
Quantile score against Σj (1 − H(uj))0.992
Two quantile forests with different seeds0.986
Quantile score against COPOD0.81
Quantile score against −log f0.58
Uniform score against its own Monte Carlo prediction0.995

The seed-to-seed agreement puts the ceiling for a noise-free target near √0.986 = 0.993, so 0.992 is as good as it can be.

Quantile cuts ignore the marginals. Take the same ranks under normal and under lognormal marginals (Gaussian copula, d = 4, correlation 0.7). Quantile scores correlate at 1.0000 between the two. Uniform scores correlate at 0.59.

Uniform cuts find far-out magnitudes; quantile cuts cannot. 1% of rows are shifted by k standard deviations in one of five normal features, in training and test data:

Shift k Uniform, AUC-PR Quantile, AUC-PR
30.1180.037
50.4520.043
100.9200.044
1001.0000.044

The geometry term is bounded, so with quantile cuts a far outlier scores no higher than the merely most extreme row.

Quantile cuts find broken dependence; uniform cuts cannot. 1% of rows get each feature from a different row. That keeps the marginals and breaks the dependence:

Pairwise correlation Uniform, AUC-PR Quantile, AUC-PR
0.70.0180.243
0.950.0280.705

With lognormal marginals the quantile numbers are identical; uniform gets 0.015 and 0.020.

Monotone transforms. After a log transform of lognormal data (Gaussian copula, d = 4, correlation 0.5), quantile scores keep their ranking (Spearman 1.0000 to four decimals) but move by up to 0.023. The cause is not traced: midpoint cuts and float32 rounding are both candidates. Uniform scores change a lot (Spearman 0.56).

The small-cell approximation fails. We tested it on the quantile score, replacing step 2’s cell-averaged copula density by the pointwise −log c:

  • On the Gaussian copula, −log c + geometry correlates with the quantile score at only 0.24. Geometry alone gets 0.73.
  • A least-squares fit on both terms explains 76% of the variance, against 46% for geometry alone and a seed ceiling of 96%.
  • The fitted weights are 0.096 on −log c and 0.71 on geometry: a ratio of 0.13, where the approximation predicts 1.
  • Uniform scores correlate with −log c at −0.33 (normal marginals) and −0.19 (lognormal), where step 3 predicts a positive value.

With about two cuts per feature the cells are large, so the scores see a heavily smoothed density. Steps 3 and 4 rest on this approximation. They need the cell-averaged density of step 1, not the pointwise one.

An unexplained observation. With normal marginals, quantile scores track −log f at 0.96, above uniform cuts (0.83). A hypothesis, not measured: the geometry term acts like a fixed bell-shaped marginal, so quantile cuts behave like density scoring after each feature is mapped to a reference shape.

What these checks suggest about the real data. The synthetic pattern matches the benchmark: quantile cuts gain on Wilt and collapse on http. We have not checked whether Wilt’s anomalies are dependence anomalies or http’s are magnitude anomalies.

Limitations

  • No accuracy gain. The result is parity at lower cost.
  • Tuning uses labels. The setting is chosen on a labelled validation part. Fully unsupervised use would fix psi.
  • Tuning is not seeded. The Optuna sampler had no fixed seed. A rerun with the same splits changed ConeForest’s per-run ROC-AUC on 12 of 48 datasets (by up to 0.029; dataset means by at most 0.003).
  • Timing. Compile time is excluded and we report medians. Mean times are inflated, because the last scoring chunk can trigger a recompile inside the timed window.
  • Our ports. xStream and HS-Trees are our JAX ports in a static setting, not the authors’ streaming code. The scoring kernels are checked against reference code; the fitting code is not covered by those checks.
  • The ablation’s A4 step is confounded, as noted above.
  • The theory is a sketch. Steps 1 and 2 are exact at population level. Steps 3 and 4 failed their direct check in the form stated. Step 5 is an unproven claim.

References

  • Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou. Isolation Forest. IEEE International Conference on Data Mining (ICDM), 2008, pp. 413–422. doi:10.1109/ICDM.2008.17
  • Swee Chuan Tan, Kai Ming Ting, Fei Tony Liu. Fast Anomaly Detection for Streaming Data. International Joint Conference on Artificial Intelligence (IJCAI), 2011, pp. 1511–1515. ijcai.org/proceedings/2011/254
  • Emaad Manzoor, Hemank Lamba, Leman Akoglu. xStream: Outlier Detection in Feature-Evolving Data Streams. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2018, pp. 1963–1972. cmuxstream.github.io
  • Zheng Li, Yue Zhao, Nicola Botta, Cezar Ionescu, Xiyang Hu. COPOD: Copula-Based Outlier Detection. IEEE International Conference on Data Mining (ICDM), 2020, pp. 1118–1123. arXiv:2009.09463
  • Songqiao Han, Xiyang Hu, Hailiang Huang, Minqi Jiang, Yue Zhao. ADBench: Anomaly Detection Benchmark. NeurIPS 2022, Datasets and Benchmarks track. arXiv:2206.09426
← Back to Articles and statistics