betaFeedback

WorksComputer Science

Random Cut Forests, Games and Diffusion over Approximately Nested Anisotropic Local Geometry

Abstract

Just as the data in a dynamic stream changes, questions asked of the stream also change in intent: what to hold constant, which counterfactuals to consider, and so forth. Energy-based learning has been celebrated for its uniform approach to losses and estimation, but interpretability remains challenging. Tree-based methods, on the other hand, offer high interpretability but often rely on bespoke, disjointed estimators. Neither paradigm readily supports changing questions on streaming data. In this paper we take a step towards combining energy, interpretability, and streaming. Random cut forests retain an evolving geometry of the data. We study this geometry as the basis for diffusion dynamics, prediction, explanation, and games. We show that several existing scores are escape probabilities of random walks on the trees. The induced affinity is realized exactly by a sparse electrical network on each tree, giving a single energy calculus, a Hamiltonian, maintained along one path per update. This connects an estimate, its supporting evidence, and the response to intervention through the same boxes, gaps, masses, and paths. Different questions correspond to different clamp decisions on the energy. Fixing observed values gives harmonic prediction with Gaussian uncertainty. Fixing a partition gives normalized cuts whose cost is attributed exactly to oriented faces. Releasing clamps gives coalition games, in which collusive displacement measures the field response. With noise, the same energy gives diffusion dynamics whose relaxation rates are read from the boxes. Axis-parallel cuts localize at a rate set by affine rather than ambient dimension, and this control passes to the averaged energy. Across a forest the boxes are only approximately nested; common reference observations align the trees. A rotating star with added noise illustrates the measurements.

Introduction

A stream changes, and so do the questions asked of it; often without foreknowledge. An inference is often the beginning of an analysis. A partition of the data, for example one obtained by normalized cuts, prompts questions about which directions support a group, where it is weakly connected to its surroundings, and how a new observation relates to it. An outlier score prompts related questions: which coordinates contributed, what values would be expected in their place, and what would change if a value were required to be larger than the current one? The answer to one question generates a need for further information and verification.

These questions differ in intent. Reading a prediction can hold the observations and reference values fixed. Testing a prescribed answer allows the other inferred values to respond. Scoring a possible insertion asks how the query would participate in the model. The distinctions are expressed through conditioning and normalization: what is held fixed, what may change, and against which population an answer is compared. Out-of-sample extensions of spectral methods make a related distinction between extending an answer and refitting its evidence [9, 1, 21]. Chaining inference routines can obscure these distinctions when each routine supplies its own neighborhood, scale, or reference population.

Decision forests have long served regression and classification [14, 12, 29, 30, 13]. Streaming tree learners also maintain fitted predictors as observations arrive [25, 32]. These constructions reflect choices about which distinctions are relevant to a particular prediction task. However a directional explanation or a counterfactual likely asks for different distinctions which are discarded by a predictor. Geurts et al. [31] analyze how random splits on irrelevant attributes reduce the sample available for prediction, introducing bias that is not removed by ensemble averaging. Tree-specific explanation methods take a different approach, Lundberg et al. [50] develop efficient Shapley attributions. Using those attributions for another decision requires specifying the reference distribution and the intended use. Bhattacharjee et al. [10], for example, show that small aggregate SHAP values over the data support need not justify discarding a feature, and derive guarantees using an extended distribution. These results reinforce the need to connect an explanation, or a question that is not known ex-ante, to original inference without constructing families of small estimators that fragment the sample or repeat work.

We believe that algorithms should explain their own work, without the need for depending on other algorithms for explanations. The observations, local geometry, and conditions used to obtain an answer should remain available to the questions that follow it. Relevance depends on the question: a distinction that contributes little to a prediction may still matter to a directional explanation or a counterfactual; and follow-up questions often arise on instances where prediction is ambiguous. Retaining that evidence also has an efficiency benefit. When an estimate and its directional contributions are accumulated in the same traversal, separate calls for the answer and its decomposition become one joint query and can be efficiently pipelined in a modern streaming system. For that pair, two tree traversals become one; richer interventions can reuse the geometry while specifying the additional computation they require.

Energy-based learning provides a uniform formulation of related inference tasks: observed variables are fixed and the remaining ones are inferred by minimizing a common energy [43]. For explanations, its terms must also be connected to the observations and directions retained by the algorithm, and the boundary conditions must specify what a query changes. Here the energy is derived from the local geometry represented by the trees. Its terms remain connected to the boxes, gaps, masses, and paths from which they were computed. Changing the question then changes the boundary conditions or the measurement of this same geometry. This gives prediction, explanation, and intervention a common calculation, with explicit evidence for each reading. We call this scalar energy the Hamiltonian; its noisy relaxation is described by Langevin dynamics with random thermal forces (i.e., Brownian motion) [41, 44] (Pavliotis 2014). For the quadratic fields used here, conditioning the associated Gaussian law gives Kriging predictions and uncertainty [66, 64].

A random cut forest (RCF) provides one way to maintain this evidence as observations change over a dynamic data stream [36]. Its trees recursively cut data boxes, and insertions and deletions preserve their distribution; the estimators are kept apart from the maintained tree structures [33]. Scores, attributions, imputed values, and forecasts are already read from the same trees in OpenSearch (OpenSearch Project, 2026a,b; Random Cut Forest contributors, 2026). RCF also provides anomaly detection in Amazon Managed Service for Prometheus [4].

This paper proposes the development of uniform, energy based analysis techniques that can function on dynamic data streams. It uses RCF both as an example that separates stream maintenance, as well as a class of trees that provides a wealth of properties that make the energy analysis over streams feasible. In particular this paper shows that many of the known uses of RCF can be reinterpreted as hitting functionals of random walks on the trees. We can then derive their energy, and use that energy to treat predictions, partitions, and coalitions together. The geometric identities and energy calculations are conditional on the chosen observations and reference sets; they require no particular sampling scheme. Maintaining the trees as their observations change is distinct from jointly adapting the reference and query sets. Axis-parallel cuts can adapt to affine structure: for width-proportional cuts we prove localization and stretch guarantees controlled by affine dimension, without estimating or rotating the support. This gives a coordinate-cut counterpart, under an affine-support assumption, to the intrinsic-dimension questions studied for random projection and other partition trees [20, 71]. Theorem 9 transfers this geometric control to the averaged Hamiltonian.

Main Results We state the results informally, in the order of the sections that prove them.

Local cuts and affine dimension (Section 2). We prove localization and stretch guarantees controlled by affine dimension for axis-parallel RCF cuts, without identifying the support’s orientation or rotating the observations (Theorem 3). The guarantees persist above a bounded-noise scale (Corollary 1). Exact insertion/deletion consistency keeps this ℓ1\ell_1 geometry maintainable as the sample changes (Proposition 1).

Hitting times and scores (§ 3). We give inverse-depth, range, and normalized displacement a common escape interpretation, identifying what each measurement reads from the same tree geometry (Theorem 5); collusive displacement averages the maximum mass-escape odds along a path (Corollary 2). Requiring a declared reference mass gives near-duplicate resilience without coalition search (Theorem 8). The same calculation retains 2d2d signed contributions that sum to the measurement (5).

Sparse energy and diffusion (§ 4). We realize a dense pairwise agreement energy exactly by a sparse network on each tree (Theorem 12). Affine geometric control passes to the averaged Hamiltonian (Theorem 9) and bounds the statistical distinguishability of Gaussian mean shifts (39). The free observation field’s merge contrasts relax at rates read directly from the hierarchy (55); grounded Langevin relaxation has stationary covariance equal to temperature times the Green’s function (45).

Landmarks and Normalized Cuts (§ 5). We align different tree geometries on common references and compute forest affinity products and normalized-cut objectives by linear tree passes, without constructing a dense affinity matrix (Proposition 13). The pooled Kriging variance separates missing support, weak connection after first contact, and the cost of requiring common prediction weights across trees (Theorem 14); range escape is the initial rate of its support term.

Coalition games and strategic responses (§ 6). We construct a quadratic Hamiltonian and an exact potential game for arbitrary worths assigned to descendant coalitions. Its Green’s function is independent of the worths, and two tree passes find a pure equilibrium under participation clamps (Theorem 16). On the mass-resistance path, collusive displacement is the square of the largest relative change of the minimizing field under a one-clamp release, measured in the energy norm (79).

Collective cut improvement and attribution (§ 6). We prove that a partition can resist every smaller move while a descendant-block move improves its normalized cut by an arbitrarily large factor (Theorem 19). The collusive cut proposes blocks by tree passes and tests a common move against the pooled objective (Theorem 20). Boundary prices attribute the fixed cut cost exactly to tree merges, to oriented faces together with unresolved leaf contributions, and to members (Theorem 17; (84) and (83)).

Directional audits and perturbations (§ 7). We compute how directional geometry changes the minimized energy (Proposition 21) and sharply bound changes in harmonic predictions under conductance perturbations, with edge support and boundary values fixed (Theorem 22). Audit stiffness quantifies the energy cost of requiring a different answer at the probe ((92)).

Measurements and an illustration (§ 8). Directional ratios ((101)) compare a query’s expansion with a neighborhood of declared mass. A rotating star with noise coordinates compares these readings, the cuts, and their Nyström extension.

Local and Global Geometry

Approximate Nesting and Organization Each tree supplies an exact laminar hierarchy of descendant sets, with boxes nested along every ancestral chain. Inspecting both children or comparing siblings does not change this hierarchy. Query intent can nevertheless require a branching family of neighborhoods: masking coordinates or augmenting boxes by the query can produce overlapping boxes from different branches (§ 2.4 and § 2.5). Across trees, the resulting neighborhoods need not belong to one common nested hierarchy. We use approximately nested geometry for these combined readings; the per-tree escape identities and energy realizations remain exact. Common references align the trees for pooled predictions and cuts (§ 5).

In closing, the sections take multiple steps toward one goal. Section 2 discusses the affine geometry. § 3 explains what the forest already computes, as hitting times on its trees. § 4 and § 5 hold the boundary fixed and read the field it induces: predictions, their uncertainty, and the energy of a partition on common references. § 6 moves the boundary and lets the players respond. § 7 and § 8 keep the directional evidence, bound its response to perturbation, and compare the measurements on a rotating star. Diffusion ties these together: the multiscale structure of the trees becomes the multiscale structure of a dynamics, whose rates are read from the boxes and change only on an insertion or a deletion that affects the approximately nested geometry. Affine structure controls tree geometry; tree geometry controls energy; energy controls distinguishability of field responses. Hitting times, Laplacians, and Nyström extensions thus formalize the notion of diffusion dynamics in streaming data; estimates and objects of interest being formed and dissociated by clamping the energy of the operators, aided by the information geometry ([3]) of approximately nested anisotropic local neighborhoods.

Local and Global Geometry

This section identifies the evidence a tree retains and the computations a query can reuse. We begin with the two sides of each coordinate, the boxes around the observations, and the observations visited by a query. We then define the cut family and explain why length allocation permits insertions and deletions while preserving the tree distribution. The same probabilities combine an answer and its directional contributions on the way back up the tree.

The global question is whether these local cuts preserve useful distances. We recall the original RCF stretch guarantee, then show how affine dimension controls localization and stretch without rotating the coordinates, including above a bounded-noise scale. The final two examples use these ingredients to explain a score, propose a replacement, and complete a time-series history. § 3 then reads the query probabilities as escape functionals.

Local Geometry and Query Traversals

Let SS be a finite empirical sample in Rd\mathbb{R}^d, allowing multiplicities or nonnegative weights. A rooted binary tree assigns each nonempty node vv a sample SvS_v, mass mvm_v, and data box Bv=bbox⁡(Sv)=∏j[ℓvj,uvj]B_v = \operatorname{bbox}(S_v) = \prod_j[\ell_{vj},u_{vj}]. Write ψ=mroot\psi= m_{\mathrm{root}} for the total sample mass. These boxes are nested along ancestry. The routing cell, defined by the cuts, can contain a query outside its data box.

Definition 1 (Query-relative half dimensions). Fix a complete query x∈Rdx \in\mathbb{R}^d and write t+=max⁡{t,0}t_+ = \max\{t,0\}. The two half dimensions of coordinate jj retain the nonnegative reaches

zx,j−(y)=(xj−yj)+,zx,j+(y)=(yj−xj)+.z^-_{x,j}(y) = (x_j-y_j)_+, \qquad z^+_{x,j}(y) = (y_j-x_j)_+.

Their extents on SvS_v are the reaches from xx to the faces of Mv(x)=bbox⁡(Bv∪{x})M_v(x) = \operatorname{bbox}(B_v \cup\{x\}):

avj−=max⁡y∈Svzx,j−(y)=(xj−ℓvj)+,avj+=max⁡y∈Svzx,j+(y)=(uvj−xj)+.a^-_{vj} = \max_{y\in S_v} z^-_{x,j}(y) = (x_j-\ell_{vj})_+, \qquad a^+_{vj} = \max_{y\in S_v} z^+_{x,j}(y) = (u_{vj}-x_j)_+.

The 2d2d reaches retain both sides of the original dd coordinates. For fixed xx, the augmented boxes remain nested along ancestry.

Fix coordinate units. At a box B=∏j[ℓj,uj]B = \prod_j[\ell_j,u_j], put rj=uj−ℓjr_j = u_j-\ell_j, R(B)=∑jrjR(B) = \sum_j r_j, and define the exterior face gaps

gj−=(ℓj−xj)+,gj+=(xj−uj)+,G=∑j(gj−+gj+).g^-_j = (\ell_j-x_j)_+, \qquad g^+_j = (x_j-u_j)_+, \qquad G = \sum_j(g^-_j+g^+_j).

Definition 2 (Query transcript). A transcript records the visited nodes, their ancestry, masses and boxes, including the origin of query-adjusted and sibling boxes. At a split on an observed coordinate, the query follows its child. A missing split coordinate admits both children; their projected boxes can overlap.

On the way down, the traversal identifies the relevant observations and geometry. On the way back up, it combines the child answers under the query’s declared branch probabilities. We call this upward combination a fold. It can carry a scalar estimate and its directional contributions together. The next subsection specifies the cut law and the probabilities used in this computation.

Cut Laws and Dynamic Maintenance

A cut law specifies which coordinate is cut and where its threshold falls. Repeating the law on the two children defines the distribution of a tree. We first give the family of cut laws, then ask which one can be maintained by inserting and deleting observations.

Definition 3 (The pp-cut law and its tree distance). At a box with coordinate widths wjw_j, choose a positive-width axis with probability

πp,j(w)=wjp∑ℓ:wℓ>0wℓp,wj>0,p≥0,(1)\pi_{p,j}(w) = \frac{w_j^p}{\sum_{\ell:w_\ell>0}w_\ell^p}, \qquad w_j>0,\quad p\ge0, \tag*{(1)}

then choose a uniform threshold on that axis and recurse. The exponent p=0p=0 gives uniform coordinate allocation, as in isolation forests ([48]); p=1p=1 gives the length allocation of RCF; p=2p=2 gives squared-width allocation. For p>0p>0 put Rp(B)=(∑jwjp)1/pR_p(B) = (\sum_j w_j^p)^{1/p}, with R1(B)=R(B)R_1(B)=R(B). For p≥1p\ge1 this is the ℓp\ell_p diameter of the box. For stored points and p>0p>0 define dT,p(a,b)=Rp(Blca(a,b))d_{T,p}(a,b)=R_p(B_{\mathrm{lca}(a,b)}); for p≥1p\ge1 write Δp(A)=diam⁡p(A)\Delta_p(A)=\operatorname{diam}_p(A) for their data diameter. Uniform allocation is an exponent-zero cut law, with no ℓ0\ell_0 ruler intended.

Insertion and restriction. For p=1p=1, an auxiliary cut of M=bbox⁡(B∪{x})M=\operatorname{bbox}(B\cup\{x\}) separates the query on the exterior face intervals with probabilities

pj,±(x,B)=gj±R(B)+G,q(x,B)=GR(B)+G.(2)p_{j,\pm}(x,B)=\frac{g_j^{\pm}}{R(B)+G},\qquad q(x,B)=\frac{G}{R(B)+G}. \tag*{(2)}

The denominator is R(M)R(M), since aj−+aj+=rj+gj−+gj+a_j^-+a_j^+=r_j+g_j^-+g_j^+. At zero expanded range set these probabilities to zero. At a node vv write Gv=R(Mv(x))−R(Bv)G_v=R(M_v(x))-R(B_v) for its total exterior gap. If the cut does not isolate the query, its restriction to the old box has the original cut law. An existing cut of BB therefore supplies the correct continuation of an insertion.

The restriction criterion also explains deletion. For any width-based coordinate probabilities πj(w)\pi_j(w) and uniform thresholds, let aj(B)=πj(w(B))/wj(B)a_j(B)=\pi_j(w(B))/w_j(B) be the cut-position density on a positive-width axis. For B⊆MB\subseteq M,

Wj(B,M)=aj(M)aj(B),EBW=∑jwj(B)aj(M).(3)W_j(B,M)=\frac{a_j(M)}{a_j(B)},\qquad\mathbb{E}_B W=\sum_j w_j(B)a_j(M). \tag*{(3)}

The expectation is the probability that a cut of MM lies in the old cut intervals. Conditional on those intervals, the old cut law is recovered exactly when WjW_j is constant there. Length allocation gives Wj=R(B)/R(M)=1−q(x,B)W_j=R(B)/R(M)=1-q(x,B).

Proposition 1 (Length allocation and deletion). Suppose a recursive tree law chooses a positive-width coordinate jj with probability πj(w)>0\pi_j(w)>0 as a function of the widths ww, then a uniform threshold on that coordinate. Deleting any stored location and contracting its parent preserves the construction law on the remaining sample if and only if

πj(w)=cjwj∑lclwl(cj>0)\pi_j(w)=\frac{c_jw_j}{\sum_l c_lw_l}\qquad(c_j>0)

on the positive-width coordinates. The probability of separating two points of a box BB is then their weighted ℓ1\ell_1 distance divided by ∑jcjRj(B)\sum_j c_jR_j(B).

Proof. For these probabilities, rescaling the coordinates by cjc_j gives the ordinary random-cut construction, which is preserved by deletion [36]. For the converse, enlarge a box of widths w′w' by adding one point beyond just one face, producing widths ww. A root cut outside the old box isolates the added point, leaving a fresh subtree of the old sample after contraction. A root cut inside the old box remains the root cut after deletion. The contracted root law is the mixture of these two laws. Whenever the old box admits a cut, the second has positive weight and must equal the original root law. By (3), the densities πj(w)/wj\pi_j(w)/w_j and πj(w′)/wj′\pi_j(w')/w'_j are proportional on the positive coordinates of w′w'. By enlarging one coordinate at a time to the coordinatewise maximum of any two width vectors, this fixes every density ratio on their shared positive coordinates. Comparing to an all-positive box gives the constants cjc_j, and normalization gives the stated probabilities. Integrating the cut density over the intervals between the two points gives the separation probability. □\square

References

  1. [1]Carlos Alzate and Johan A. K. Suykens. Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(2):335–347, 2010.
  2. [2]Shun-ichi Amari. Information Geometry and Its Applications, volume 194 of Applied Mathematical Sciences. Springer, Tokyo, 2016. doi: 10.1007/978-4-431-55978-8.DOI
  3. [3]Shun-ichi Amari and Hiroshi Nagaoka. Methods of Information Geometry, volume 191 of Translations of Mathematical Monographs. American Mathematical Society and Oxford University Press, 2000. doi: 10.1090/mmono/191.
  4. [4]Amazon Web Services. Amazon managed service for prometheus user guide: Anomaly detection. https://docs.aws.amazon.com/prometheus/latest/userguide/prometheus-anomaly-detection.html, 2026.
  5. [5]Pablo Arbeláez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5):898–916, 2011. doi: 10.1109/TPAMI.2010.161.DOI
  6. [6]Konstantin Avrachenkov, Aleksei Yu. Kondratev, Vladimir V. Mazalov, and Dmytro Rubanov. Network partitioning algorithms as cooperative games. Computational Social Networks, 5:11, 2018. doi: 10.1186/s40649-018-0059-5.DOI
  7. [7]Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003. doi: 10.1162/089976603321780317. URL https://misha.belkin-wang.org/papers/LEM_NC_03.pdf.DOI
  8. [8]A. D. Bendikov, A. A. Grigor’yan, Ch. Pittet, and W. Woess. Isotropic Markov semigroups on ultra-metric spaces. Russian Mathematical Surveys, 69(4):589–680, 2014.
  9. [9]Yoshua Bengio, Jean-François Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Le Roux, and Marie Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, Eigenmaps, and spectral clustering. In Advances in Neural Information Processing Systems 16, 2004. URL https://proceedings.neurips.cc/paper/2003/hash/cf05968255451bdefe3c5bc64d550517-Abstract.html.
  10. [10]Robi Bhattacharjee, Karolin Frohnapfel, and Ulrike von Luxburg. How to safely discard features based on aggregate SHAP values. In Proceedings of the 38th Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 280–314, 2025. URL https://proceedings.mlr.press/v291/bhattacharjee25a.html.arxiv.org/abs/2503.23111
  11. [11]Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5(3):387–424, 1993. doi: 10.1006/game.1993.1023.DOI
  12. [12]Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. doi: 10.1007/BF000058655.
  13. [13]Leo Breiman. Random forests. Machine Learning, 45(1):5–32, 2001. doi: 10.1023/A:1010933404324.DOI
  14. [14]Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth, 1984a. ISBN 0-534-98053-8.DOI
  15. [15]Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984b.DOI
  16. [16]Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, and Jörg Sander. LOF: Identifying density-based local outliers. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 93–104, 2000. doi: 10.1145/342009.335388.DOI
  17. [17]Kenneth C. Chou, Alan S. Willsky, and Albert Benveniste. Multiscale recursive estimation, data fusion, and regularization. IEEE Transactions on Automatic Control, 39(3):464–478, 1994.DOI
  18. [18]Michael B. Cohen and Richard Peng. ℓₚ row sampling by lewis weights. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 183–192, 2015. doi: 10.1145/2746539.2746567. URL https://arxiv.org/abs/1412.0588.
  19. [19]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
  20. [20]Sanjay Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 537–546, 2008. doi: 10.1145/1374376.1374452. URL https://cseweb.ucsd.edu/~yfreund/papers/rptree-tr.pdf.DOI
  21. [21]Olivier Delalleau, Yoshua Bengio, and Nicolas Le Roux. Efficient non-parametric function induction in semi-supervised learning. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, volume R5 of Proceedings of Machine Learning Research, pages 96–103, 2005. URL https://proceedings.mlr.press/r5/delalleau05a.html.
  22. [22]Xiaotie Deng and Christos H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257–266, 1994. doi: 10.1287/moor.19.2.257.DOI
  23. [23]Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means, spectral clustering and normalized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 551–556, 2004. URL https://people.bu.edu/bkulis/pubs/spectral_kdd.pdf.
  24. [25]Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 71–80, 2000. doi: 10.1145/347090.347107. URL https://alchemy.cs.washington.edu/papers/pdfs/domingos-hulten00.pdf.DOI
  25. [26]Florian Dörfler and Francesco Bullo. Kron reduction of graphs with applications to electrical networks. IEEE Transactions on Circuits and Systems I: Regular Papers, 60(1):150–163, 2013. doi: 10.1109/TCSI.2012.2215780. URL https://motion.me.ucsb.edu/pdf/2011d-db.pdf.
  26. [27]Peter G. Doyle and J. Laurie Snell. Random Walks and Electric Networks, volume 22 of Carus Mathematical Monographs. Mathematical Association of America, 1984. URL https://arxiv.org/abs/math/0001057.
  27. [28]Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004.pubmed.ncbi.nlm.nih.gov/15376896
  28. [29]Yoav Freund and Robert E. Schapire. Experiments with a new boosting algorithm. In Machine Learning: Proceedings of the Thirteenth International Conference (ICML ’96), pages 148–156, Bari, Italy, 1996. Morgan Kaufmann.
  29. [30]Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189–1232, 2001.DOI
  30. [31]Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine Learning, 63(1):3–42, 2006. doi: 10.1007/s10994-006-6226-1.DOI
  31. [32]Heitor Murilo Gomes, Jean Paul Barddal, Luis Eduardo Boiko, and Albert Bifet. Adaptive random forests for data stream regression. In Proceedings of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, pages 267–272, 2018. URL https://www.esann.org/sites/default/files/proceedings/legacy/es2018-183.pdf.
  32. [33]Sudipto Guha and Joshua Tokle. Random cut forests. OpenSearch Blog; first posted on the Open Distro for Elasticsearch blog, 26 November 2019. https://opensearch.org/blog/random-cut-forests/, 2019.
  33. [34]Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. CURE: An efficient clustering algorithm for large databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 73–84, 1998. doi: 10.1145/276304.276312.DOI
  34. [35]Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan. Clustering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):515–528, 2003. URL https://www.cs.emory.edu/~cheung/Courses/584/Syllabus/papers/Clustering/2003-Guha-clustering.pdf.DOI
  35. [36]Sudipto Guha, Nina Mishra, Gourav Roy, and Okke Schrijvers. Robust random cut forest based anomaly detection on streams. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2712–2721, 2016. URL https://proceedings.mlr.press/v48/guha16.html.
  36. [37]John C. Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194–220, 1963. doi: 10.2307/2525487.DOI
  37. [38]Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 8(48): 1325–1368, 2007. URL https://jmlr.org/papers/v8/hein07a.html.arxiv.org/abs/math/0608522
  38. [39]Till Hoffmann and Nick S. Jones. Unified treatment of the asymptotics of asymmetric kernel density estimators. arXiv:1512.03188, 2015. URL https://arxiv.org/abs/1512.03188.
  39. [40]Hans-Peter Kriegel, Peer Kröger, Erich Schubert, and Arthur Zimek. Outlier detection in axis-parallel subspaces of high dimensional data. In Advances in Knowledge Discovery and Data Mining, 13th Pacific-Asia Conference, PAKDD 2009, volume 5476 of Lecture Notes in Computer Science, pages 831–838. Springer, 2009. doi: 10.1007/978-3-642-01307-2_86.DOI
  40. [41]Paul Langevin. Sur la théorie du mouvement brownien. Comptes Rendus de l’Académie des Sciences, 146:530–533, 1908.
  41. [42]Günter Last and Mathew Penrose. Lectures on the Poisson Process. Cambridge University Press, 2017. doi: 10.1017/9781316104477. URL https://stoch.math.kit.edu/img/Last/lastpenrose2017.pdf.DOI
  42. [43]Yann LeCun, Sumit Chopra, Raia Hadsell, Marc’Aurelio Ranzato, and Fu Jie Huang. A tutorial on energy-based learning. In GöKhan BakIr, Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola, Ben Taskar, and S. V. N. Vishwanathan, editors, Predicting Structured Data. MIT Press, 2006.
  43. [44]Don S. Lemons and Anthony Gythiel. Paul langevin’s 1908 paper “on the theory of brownian motion”. American Journal of Physics, 65(11):1079–1081, 1997.
  44. [45]D. R. Lewis. Finite dimensional subspaces of Lₚ. Studia Mathematica, 63(2):207–212, 1978. doi: 10.4064/sm-63-2-207-212.
  45. [48]Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In Proceedings of the Eighth IEEE International Conference on Data Mining, pages 413–422, 2008. doi: 10.1109/ICDM.2008.17.DOI
  46. [49]D. O. Loftsgaarden and C. P. Quesenberry. A nonparametric estimate of a multivariate density function. The Annals of Mathematical Statistics, 36(3):1049–1051, 1965. doi: 10.1214/aoms/1177700079.DOI
  47. [50]Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable AI for trees. Nature Machine Intelligence, 2:56–67, 2020. doi: 10.1038/s42256-019-0138-9. URL https://pmc.ncbi.nlm.nih.gov/articles/PMC7326367/.
  48. [51]Russell Lyons and Yuval Peres. Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016. doi: 10.1017/9781316672815. URL https://rdlyons.pages.iu.edu/prbtree/.
  49. [52]Charalampos Mavroforakis, Michael Mathioudakis, and Aristides Gionis. Absorbing random-walk centrality: Theory and algorithms. In 2015 IEEE International Conference on Data Mining, pages 901–906, 2015. doi: 10.1109/ICDM.2015.103. URL https://arxiv.org/abs/1509.02533.
  50. [53]Marina Meilă and Jianbo Shi. A random walks view of spectral segmentation. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, volume R3 of Proceedings of Machine Learning Research, pages 203–208, 2001. URL https://proceedings.mlr.press/r3/meila01a.html.
  51. [54]Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996.
  52. [55]Roger B. Myerson. Conference structures and fair allocation rules. International Journal of Game Theory, 9(3):169–182, 1980. doi: 10.1007/BF01781371.DOI
  53. [56]John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951.
  54. [57]Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, volume 14, pages 849–856, 2001. URL https://papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.
  55. [58]OpenSearch Project. OpenSearch documentation: Anomaly detection. https://docs.opensearch.org/latest/observing-your-data/ad/index/, 2026a.
  56. [59]OpenSearch Project. OpenSearch documentation: Forecasting. https://docs.opensearch.org/latest/observing-your-data/forecast/index/, 2026b.
  57. [60]Grigorios A. Pavliotis. Stochastic Processes and Applications: Diffusion Processes, the Fokker–Planck and Langevin Equations, volume 60 of Texts in Applied Mathematics. Springer, New York, 2014. doi: 10.1007/978-1-4939-1323-7.
  58. [63]Random Cut Forest contributors. Random cut forest: Java library used by OpenSearch. https://github.com/aws/random-cut-forest-by-aws/tree/4.4.0-java, 2026.
  59. [64]Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, Cambridge, MA, 2006. doi: 10.7551/mitpress/3206.001.0001. URL https://gaussianprocess.org/gpml/.DOI
  60. [65]Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000. doi: 10.1109/34.868688.DOI
  61. [66]Michael L. Stein. Interpolation of Spatial Data: Some Theory for Kriging. Springer, New York, 1999.
  62. [67]Streaming Algorithms. Random cut forest: Java implementation. https://github.com/streamingalgorithms/randomcutforest, 2026.
  63. [68]Jian Tang, Zhixiang Chen, Ada Wai-Chee Fu, and David W. Cheung. Enhancing effectiveness of outlier detections for low density patterns. In Advances in Knowledge Discovery and Data Mining, 6th Pacific-Asia Conference, PAKDD 2002, volume 2336 of Lecture Notes in Computer Science, pages 535–548. Springer, 2002. doi: 10.1007/3-540-47887-6_53.
  64. [69]George R. Terrell and David W. Scott. Variable kernel density estimation. The Annals of Statistics, 20(3):1236–1265, 1992. doi: 10.1214/aos/1176348768. URL https://doi.org/10.1214/aos/1176348768.
  65. [70]Anne van den Nouweland, Peter Borm, and Stef Tijs. Allocation rules for hypergraph communication situations. International Journal of Game Theory, 20(3):255–268, 1992. doi: 10.1007/BF01253780.DOI
  66. [71]Nakul Verma, Samory Kpotufe, and Sanjoy Dasgupta. Which spatial partition trees are adaptive to intrinsic dimension? In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages 565–574, 2009.
  67. [72]Jeffrey S. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37–57, 1985. doi: 10.1145/3147.3165.DOI
  68. [73]Tal Wagner, Sudipto Guha, Shiva Kasiviswanathan, and Nina Mishra. Semi-supervised learning on data streams via temporal label propagation. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5095–5104. PMLR, 2018. URL https://proceedings.mlr.press/v80/wagner18a.html.
  69. [74]Joe H. Ward, Jr. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236–244, 1963.DOI
  70. [75]Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on Machine Learning, pages 912–919, 2003. URL https://pages.cs.wisc.edu/~jerryzhu/pub/zgl.pdf.
  71. [76]Arthur Zimek, Matthew Gaudet, Ricardo J. G. B. Campello, and Jörg Sander. Subsampling for efficient and effective unsupervised outlier detection ensembles. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 428–436, 2013.DOI

Paper details

vlnc:W_xjap92yr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

multiple generative AI tools

View statement
Looking for related papers…
Contents