Probabilistic Performance Analysis of Parallel Signature Search Strategies in Multi-Level Tree Networks

Received XX Month, XXXX; revised XX Month, XXXX; accepted XX Month, XXXX; Date of publication XX Month, XXXX; date of current version XX Month, XXXX. Digital Object Identifier 10.1109/XXXX.XXXX.XXXXXXX

Probabilistic Performance Analysis of Parallel Signature Search Strategies in Multi-Level Tree Networks Jingwei Li1 and Thomas G. Robertazzi1,2 , Fellow, IEEE

arXiv:2608.25087v2 [cs.DC] 28 Aug 2026

2

1 Department of Electrical and Computer Engineering, Stony Brook University, 100 Nicolls Rd, Stony Brook, NY 11794, USA Department of Applied Mathematics and Statistics (affiliate), Stony Brook University, 100 Nicolls Rd, Stony Brook, NY 11794, USA

Corresponding author: Thomas G. Robertazzi (email: thomas.robertazzi@stonybrook.edu). This work is based in part on the first author’s doctoral dissertation, Stony Brook University, 2022. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

ABSTRACT Hierarchical distributed search — locating a data pattern, or signature, across a tree-structured

collection of files — underlies distributed index traversal, deep packet inspection and sequence alignment. A practitioner must decide how much parallelism to employ: scan each layer sequentially, fan out within subtrees, or launch the whole tree at once. Existing analyses answer this only partially: they characterize every node by the statistics of a signature-holding file and, for multi-signature files, need quantities revealed only at run time. We develop a probabilistic framework predicting the completion time of five search strategies, spanning sequential to full-tree parallelism, before any file is read. Node scan times are modeled as a mixture over signature presence, layer times as order statistics, and parallel subtree scans by extreme-value arguments; when signature counts are known, occupancy under capacity constraints is treated by generating functions. Each performance formula carries an exactness label — exact (or exact-in-regime), plug-in, asymptotic or bound — each approximation quantified against Monte Carlo simulation and its regime identified. A multicore prototype reproduces the coarse separation between fulltree, layer- and subtree-level parallelism, but shows that synchronization overhead can erase the predicted separation between close strategies. The framework delivers a priori completion-time predictions with explicit accuracy regimes and negligible computational cost, the design example evaluated in under a millisecond; these timing models can support subsequent resource-cost optimization. INDEX TERMS Divisible load theory, signature searching, tree networks, order statistics, performance

analysis, parallel processing.

I. Introduction

A signature is a data pattern of interest inside a large file or a collection of files: a gene fragment in a DNA database, a byte pattern in network traffic, a keyword in a document corpus, a feature in an image archive. When the collection is distributed over a network of processors, the time to locate all signatures depends jointly on the network topology, the search strategy, and the statistics of signature occurrence. Multi-level tree networks are a natural substrate for such searches: work flows from a root to successively wider layers, matching both the structure of hierarchical storage systems and the master–worker pattern of divisible load scheduling.

This paper asks a planning question: before a search is launched, what is its expected completion time? An a priori answer lets an operator compare candidate strategies, dimension a tree, or negotiate a deadline without running the search. On elastic infrastructure the question is sharper still: when processors are rented by the slot, how widely to fan out is a cost decision as much as a latency one, and it must be made before the workload reveals itself. Prior analyses of signature search time in tree networks [1] answer this only partially: they model every node with the statistics of a signature-holding node, and, when files may hold several signatures, require quantities that only become known during the search itself.

This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ VOLUME ,

1

Li et al.:

To the best of our knowledge, this is the first unified a priori framework that jointly covers both information conditions, all three capacity classes, and the full range of layer- and subtree-level parallelism, with every expression traceable to a stated exactness label. Our contributions are as follows. First, a framework spanning two information conditions (signature counts per layer unknown vs. known), three capacity classes (at most one, at most K , unlimited) and five strategies from fully sequential to fully parallel, each with an explicit analytical or numerically evaluable expected-time characterization — except for one complementary capacityconstrained regime, which we identify and leave open. What the unification requires matters more than the count of settings: a mixture correction to the node-time model, explicit conditioning on random layer widths, the occupancy law of subtree counts, and computational routes for small and large parameters alike. Second, a sharper probabilistic foundation: node times are modeled as a mixture over signature presence, parallel stages via order statistics, and parallel subtree scans via central-limit and extreme-value arguments with the correct mixture variance. Third, for known counts we show that persubtree occupancies follow a multivariate hypergeometric law — not the uniform-composition law that stars-andbars counting suggests — characterize the minimum subtree count through a generating function, and solve the multisignature case under both placement conventions in one framework. Fourth, the principal formulas are validated by Monte Carlo simulation, and every formula is classified as exact or approximate with a quantified accuracy range, and a multicore prototype measures how far the unboundedprocessor idealization carries in real execution. The paper is organized as follows. Section II reviews related work. Section III defines the model. Sections IV and V analyze the unknown- and known-count conditions. Section VI reports the simulation study and Section VII a design example with the computational cost of the analysis; Section VIII discusses scope and limitations, and Section IX concludes. II. Related Work

Divisible load theory. DLT studies the optimal partitioning of arbitrarily divisible computation among networked processors [2]–[5]. Closed-form and algorithmic results exist for buses, daisy chains, stars and multi-level trees [6], with continuing extensions, e.g., to coarse-grained workloads [7]. Our work belongs to the performance-analysis branch of this literature: rather than optimizing a load partition, we predict the completion time of a fixed hierarchical search discipline. Signature searching. Ying and Robertazzi [1] introduced the time-cost analysis of signature searching in a networked collection of files, establishing the scenario taxonomy and the basic expected-time arguments on which the present work is built. Their analysis characterizes each node by 2

TABLE 1. Scope of [1] and of this work

Dimension

Prior work [1]

This work

Node time

signature-node law

signature/non-signature mixture

Information Capacity Strategies Known counts Validation

partly runtime one, unlimited layer-level limited limited

strictly a priori one, K, unlimited (unified) five, incl. subtree-level occupancy law under two conventions Monte Carlo, error

Resource view

—

regimes, prototype peak concurrency reported

the statistics of a signature-holding file, which is exact when signatures are plentiful but increasingly optimistic as p decreases, underestimating the latency (Section VI), and it treats the single- and multi-signature cases separately, the latter in terms of quantities revealed during the search. We refine that foundation in four directions: node times are modeled as a mixture over signature presence; a capacity class interpolating between one and unlimited signatures is added; every setting is made computable strictly in advance; and two subtree-oriented disciplines are introduced, requiring centrallimit and extreme-value arguments. Table 1 summarizes the differences dimension by dimension. Distributed pattern search. On the application side, the primitive analyzed here appears wherever a pattern must be located across a distributed corpus: regular-expression and string matching for deep packet inspection and intrusion detection [8], and sequence alignment over clustered genomic data, where read alignment is routinely distributed with data-parallel frameworks [9], [10] such as Apache Spark [11], [12]. Hierarchical summaries — Bloom filters (spaceefficient probabilistic structures for testing set membership) and related structures [13], or the merged indexes of Section III — are what make the pruning assumption realizable in such systems. That literature optimizes the matcher run at a node; we take the per-node scan as given and predict the completion time of the search that coordinates the nodes. Parallel completion-time modeling. A layer of our tree is a fork–join stage: work is split, executed concurrently, and joined, so the stage time is the maximum of the branch times. Exact analysis is hard beyond two branches, and the literature relies on approximations and bounds [14], surveyed in [15], with recent extensions to heterogeneous servers [16] and to bounded, heterogeneous processor sets [17] — the setting our prototype meets empirically. The same maximum-of-many effect appears operationally as the straggler problem [18], mitigated by cause-aware restart and placement [19] or by cloning [20]. Our S4 analysis is its analytical counterpart: the layer √ time is an extreme value over subtrees, growing like ln M rather than with the VOLUME ,

mean. Unlike queueing fork–join models, our branches are not service stations fed by arrivals but bounded scans of known length, which is what makes closed forms attainable. Combinatorial occupancy. The known-count analysis draws on classical occupancy theory [21], [22], whose ballsinto-bins asymptotics are standard tools for load distribution [23]. Capacity-constrained counts of placements of identical balls into distinct urns, used in Section V-B, are derived in our companion combinatorial paper [24]; the equal-composition vs. uniform-placement distinction of Section VIII mirrors the classical Bose–Einstein vs. Maxwell– Boltzmann dichotomy [22]. III. System Model and Assumptions A. Multi-Level Tree Networks

We consider a rooted tree network of height H . The root (layer 0) acts as coordinator; every non-root node holds one searchable object, which we call its file: at a leaf a shard (one partition of a horizontally split data set), internally a summary index over the shards below. A node in layer i − 1 that participates in the search has ni children in layer i, i = 1, . . . , H ; all subtrees rooted in the same layer are therefore homogeneous in size. The ni children of a common parent form a subtree of layer i. Derivations keep ni general; a bare n means ni = n for all i. A table of notation is given in the supplementary material. B. Search-Time Model

Scanning a file takes time s; we normalize the scan to proceed at unit speed, so a signature located at position u ∈ [0, s] is found at time u. Signature positions are uniformly distributed, hence for a file that contains a signature the discovery time is U [0, s] with mean X = s/2. If a file contains no signature, the scan can only terminate after the entire file has been read, taking the deterministic time s = 2X . Assumption 1 (Signature inheritance). If a node holds no signature, none of its descendants holds a signature, and its subtree is pruned from the search. If a node holds a signature, each of its children holds a signature with probability p at capacity one, independently across children. Writing K for the maximum number of signatures a single file may hold (Section III-E), p is for K > 1 the perslot occupancy and a child is nonempty with probability q = 1 − (1 − p)K (Remark 1). Remark 1 (Two readings of p). At capacity one, p is a node-level presence probability. For K > 1 (Section IV-C) p is the slot-level occupancy probability, each of the K slots being filled independently, so the node-level probability of holding at least one signature is q = 1 − (1 − p)K , which reduces to p at K = 1. Assumption 1, from [1], is not arbitrary but the semantics of a summarized hierarchical index, the running example of this paper (Figure 1). Leaves store data shards; an internal VOLUME ,

coordinator

layer 0

scanned, no match: descendants pruned

summary index

summary

summary

layer 2 shard shard

shard shard

shard shard

layer 1

FIGURE 1. Reference architecture, shown for H = 2 with n1 = 3 and n2 = 2. The root acts as query coordinator; internal nodes hold a summary index over their subtree; leaves hold data shards (partitions of the data set). A summary is itself scanned; one ending without a match prunes its descendant subtree (dashed).

node stores a summary index over the shards below — the merged list of patterns occurring anywhere in its subtree, or an equivalent digest — which is itself scanned. Because the index is complete, a scan that reaches its end without a match certifies that no descendant can match and the subtree is skipped: exactly the pruning of Assumption 1. The same completeness fixes the two scan times of Section III-B. A node whose index holds no match must be read in full before that conclusion is safe, costing s; a node whose index does hold one stops at the matching entry, at a position we take to be uniform, costing U [0, s] in expectation. Versioned storage and provenance graphs read the same way. C. Search Scenarios

Layers are always processed one after another; the five scenarios differ in how the nodes within a layer are processed: S1 : all nodes of the layer are searched sequentially; S2 : all nodes of the layer are searched in parallel; S3 : within each subtree (the ni children of one parent) the nodes are searched in parallel, subtrees sequentially; S4 : the nodes of each subtree are searched sequentially, subtrees in parallel; S5 : every node of the entire tree is searched in parallel (single stage, no layer synchronization).

Remark 2 (Execution semantics of S5 ). S1 –S4 synchronize between layers, so a node is started only after its parent is known to hold a signature and pruning saves work. S5 has no such synchronization point, and we P define Q it as speculative full-tree execution: all N = i≤H j≤i nj nodes are launched at t = 0, and the scans of subtrees that pruning would have eliminated are performed but discarded. Completion time is thus the maximum over all launched nodes, and the processor cost is charged for all N of them — the accounting used in Section VII. S5 consequently upper-bounds the achievable parallelism of any dependencyrespecting schedule and serves as an idealized latency lower bound; its interest lies precisely in the resource price of that bound. 3

Li et al.:

D. Random Quantities and Conditioning

Because several quantities below are random, we fix their status once and for all. Deterministic parameters: H , ni , s, p, K , and — in the known-count condition — the signature counts mi . Random variables: the per-node search time t; the ci ) of signature-holding nodes in layer i number Mi (resp. M when files hold at most one (resp. at most K ) signature; the per-subtree occupancy vector; and every layer completion time. The number of nodes searched in layer i is Mi−1 ni ci−1 ni in the capacity-K case), itself random for (resp. M i ≥ 2. Note that Mi counts only the signature-holding nodes among those Mi−1 ni : at capacity one Mi | Mi−1 ∼ Bin(Mi−1 ni , p). Hat convention: throughout, a hat marks the ci , Tbj , capacity-K counterpart of a capacity-one quantity — M τbi — each reducing to it at K = 1. Layer times are therefore analyzed conditionally on the width of the preceding layer — the number Mi−1 of its signature-holding nodes, which fixes how many nodes layer i searches — and the total is obtained by averaging over that width. Writing τi (·) for the conditional expected time of layer i given the number of searched parents, the exact total is H H X X   X T = E τi (Mi−1 ) = P(Mi−1 = k) τi (k). (1) i=1

i=1

k

When τi is affine in Mi−1 , (1) collapses to τi (EMi−1 ) and the result is exact; otherwise we evaluate τi (EMi−1 ) as a plug-in (mean-field) approximation and report its error. Note that EMi−1 is generally not an integer, so whenever τi involves combinatorial quantities defined only for integer arguments, the plug-in is used with EMi−1 rounded to the nearest integer; (1) remains available as the exact alternative at higher cost. Remark 3 (Exactness labels). Every result below carries one of five labels: EXACT (rigorous in the stated model); PLUG - IN (uses Eg(M ) ≈ g(EM )); CLT / EVT (relies on asymptotic distributions); BOUND (systematic under- or over-estimate); and EXACT- IN - REGIME (rigorous under a stated parameter condition). Section VI quantifies the error of every non-exact label.

convention S1 –S4 differ only in how work is parallelized; S5 additionally executes speculatively (Remark 2), so its work set is the full tree. The supplementary material quantifies what cancellation would save for S1 and S2 , both in closed form, and why subtree-level cancellation (S3 , S4 ) does not yield a comparable closed form under the present analysis. Orthogonally, three capacity classes are considered: each file holds at most one signature; at most K signatures; or an unlimited number of signatures. The results of this paper are a priori computable: they depend only on (H, ni , s) together with p (and K ), or with {mi } — quantities available before the search starts. IV. Unknown Number of Signatures A. At Most One Signature per File 1) Single-Node Statistics

Under Assumption 1 a searched node holds a signature with probability p. Its search time t therefore follows the mixture f (t) = p f1 (t) + (1 − p) f2 (t),

(2)

where f1 is the density of U [0, s] and f2 is a unit point mass at t = s. Lemma 1. With X = s/2, the search time of a searched node satisfies s E(t) = p + (1 − p) s = (2 − p)X, (3) 2 2 s p (4 − 3p) p (4 − 3p) 2 V(t) = E(t2 ) − E(t)2 = X . = 12 3 (4) Proof: The mixture mean is the probability-weighted R s 2 mean, giving (3). For the
second moment, E(t2 ) = p 0 us du+(1−p)s2 = p 2 2 2 3 + 1 − p s , and (4) follows from V(t) = E(t ) − E(t) with E(t) = (1 − p2 )s. Remark 4. Note that the variance of a mixture is not the weighted sum of the component variances: the dispersion between the component means p contributes the p additional term visible in (4). We write σ ≜ V(t) = X p(4 − 3p)/3.

E. Information Conditions and Capacity Classes

Two information conditions are studied. In the unknowncount condition (Section IV), signature occurrence is only known statistically through Assumption 1. In the knowncount condition (Section V), the exact number mi of signatures in each layer is known in advance, and the signatures are placed at random over the searched nodes of that layer: uniformly over node subsets when files hold at most one signature, and, for capacity K > 1, according to one of the two placement conventions introduced in Section V-B. Assumption 2 (No global cancellation). Knowing mi tells the coordinator when a layer’s signatures have all been found, but we do not assume it can retract dispatched work: every dispatched node completes its scan. Under this 4

2) Expected Number of Searched Nodes

Let Mi denote the number of signature-holding nodes in layer i (M0 = 1). Each of the Mi−1 ni searched nodes of layer i holds a signature independently with probability p, hence E(Mi | Mi−1 ) = p ni Mi−1 and, by induction, E(Mi ) = p i

i Y

nj ,

i = 1, . . . , H.

(5)

j=1

Remark 5 (Plug-in approximation). Mi enters several of the formulas below nonlinearly. Wherever this happens
we use the plug-in approximation E g(Mi−1 ) ≈ g EMi−1 , and we quantify the resulting error by exact enumeration of the width law in Section VI. Formulas that are linear in Mi−1 VOLUME ,

(T1 , T3 ) are exact. We set τi (0) = 0: a layer whose parent width is zero is never executed, and µ(1) = 0 in (12), whose expansion is undefined at M = 1. The plug-in also presumes the width distribution is concentrated. In subcritical trees (pni ≲ 1) extinction carries substantial probability, and evaluating a nonlinear τi at a mean width that the process may never reach is a structural, not a rounding, error: at H = 3, n = 6, p = 0.1 the exact average (1) gives T2 = 1.72 against 3.00 for the plug-in. We recommend, as a conservative rule of thumb, (1) when pni is around 2 or below.

3) Parallel Search of n Nodes

Lemma 2. Let t̂ be the completion time of n nodes searched in parallel, each holding a signature independently with probability p. Then  pn  E(t̂) = 1 − (6) 2X. n+1 Proof: If at least one node holds no signature (probability 1 − pn ), that node scans its whole file, so t̂ = s exactly. If all n nodes hold signatures (probability pn ), t̂ = max(t1 , . . . , tn ) with tk ∼ U [0, s] i.i.d.; the maximum has CDF (y/s)n and mean n n n n n+1 s. Combining, E(t̂) = p n+1 s+(1−p )s, which is (6).

Proof sketch: T1 : conditionally on Mi−1 the layer-i workload is Mi−1 ni sequentially searched nodes of mean (2 − p)X each (Lemma 1); the conditional expectation is affine in Mi−1 , so (1) collapses and (5) gives (7) exactly. T2 and T3 follow from Lemma 2 applied to the whole layer and to one subtree: T3 is again affine in Mi−1 and hence exact, whereas T2 ’s conditional expectation is nonlinear in Mi−1 and is evaluated by plug-in (Remark 5). T5 involves no random width — by Remark 2 all N nodes are launched — so Lemma 2 applies directly with n = N and the result is exact. For T4 , the layer-i time is the maximum over Mi−1 Pni t parallel subtrees of the sum Uj = k=1 j,k of ni i.i.d. node times. By the central limit theorem Uj ≈ ni (2 −p)X + √ ni σZj with Zj ∼ N (0, 1); the expected maximum of M i.i.d. standard normal variables admits the expansion µ(M ) of (12) [25], in the tradition of [26]. Combining the two yields (10). Remark 6 (Applicability of T4 ). (10) rests on two asymptotic steps: the CLT (accurate for ni ≳ 30) and the extremevalue expansion (accurate for Mi−1 ≳ 10). Within it the formula stays within about 1% of simulation (supplementary accuracy table). Outside this regime, the numerical convolution route in (13) should be used instead.

5) Exact Numerical Evaluation of the S4 Layer

4) Total Expected Search Times

Theorem 1. Under the model of Section III with at most one signature per file, the total expected search times are T1 =

H X

p i−1

i=1

i Y

 nj (2 − p)X,

j=1

EXACT

(7)

The asymptotic stepPin (10) can be avoided entirely. The n subtree time U = k=1 tk is a sum of i.i.d. node times whose law is known exactly — density p/s on [0, s) plus an atom of mass 1 − p at s — so its CDF FU is the n-fold convolution of that law, computable on a grid, and the layer time follows from the identity Z ns   E max(U1 , . . . , UM ) = ns − FU (x)M dx. (13) 0

H  X

This is EXACT up to discretization and costs O(n2 G) for a PLUG - IN grid of G points, against O(1) for (10). We therefore select (8) automatically: use (10) when ni ≥ 50 and Mi−1 ≥ 10, and (13) otherwise. Over configurations spanning n ∈ [4, 100] H  X p ni  T3 = E(Mi−1 ) 1 − 2X, EXACT (9) and M ∈ [3, 50] (supplementary material), the numerical n + 1 route stays within 0.06% of simulation everywhere, while i i=1 the asymptotic formula degrades from 0.5% at n = 100, H h i X
√ T4 ≈ ni σ µ E(Mi−1 ) + ni (2 − p)X , PLUG - IN , CLT / EVT M = 50 to 3.3% at n = 4, M = 5 — so the selection rule buys accuracy exactly where it is needed. i=1 (10) H Y i B. General Discovery-Time Distributions  X pN  T5 = 1 − 2X, N = nj , EXACT Signature positions need not be uniform. Let the discovery N +1 i=1 j=1 time in a signature-holding file have an arbitrary CDF Fs (11) on [0, s], with mean µs and second moment µ(2) s . The node p time is still the mixture (2), so where σ = X p(4 − 3p)/3 and 2 2 E(t) = p µs +(1−p)s, V(t) = p µ(2) s +(1−p)s − E(t) , √ ln ln M + ln 4π − 2γ (14) √ µ(M ) = 2 ln M − , (12) 2 2 ln M and the node CDF is Ft (x) = pFs (x) for x < s, with the with γ ≈ 0.5772 the Euler–Mascheroni constant. remaining mass at s. Sequential stages (T1 , and the subtree p νi  2X, νi = E(Mi−1 )ni , T2 ≈ 1− νi + 1 i=1

VOLUME ,

5

Li et al.:

sums inside T4 via the CLT) depend on Fs only through these moments; parallel stages do not. For n nodes searched concurrently, Z s    n E max(t1 , . . . , tn ) = s − p Fs (x) dx, (15)

Theorem 2. With at most K signatures per file, writing ν̂i = ci−1 ) ni and N = PH Qi nj , E(M j=1 i=1 Tb1 =

0

which requires the entire CDF. Uniform positions give Rs n (px/s) dx = pn s/(n + 1) and recover Lemma 2; the K 0 signature case follows by replacing the early-finish weight p with pK and Fs with the CDF Fs (x)K of the K th order statistic. Every result below thus transports to non-uniform positions via (14)–(15), at the price of one numerical integral where no closed form exists. C. At Most K Signatures per File

We now allow each file to hold up to K signatures. The number of signatures in a searched node is modeled as Binomial(K, p): each of the K capacity slots is occupied independently with probability p. A node therefore holds at least one signature with probability q ≜ 1 − (1 − p)K , and, ci for the number of signature-holding nodes in writing M layer i, the argument leading to (5) gives ci ) = q i E(M

i Y

nj ,

c0 = 1. M

(16)

j=1

The scan of a node can terminate early only when the K th signature is found, since only then can the searcher be certain that nothing remains. Consequently, with probability pK (exactly K signatures) the node time is the largest of K i.i.d. U [0, s] positions, with density KtK−1 /sK and mean K K+1 s; otherwise the node time is s. This yields the following analogue of Lemma 1 (derivations in the supplementary material). Lemma 3. With at most K signatures per file,  pK  E(t) = 1 − 2X, (17) K +1 h i K
2 p 2 K V(t) = pK K+2 + 1 − pK − 1 − K+1 s2 ≜ σK . (18)

Tb2 ≈ Tb3 = Tb4 ≈

H X

 ci−1 ) ni 1 − E(M

i=1 H  X

1−

i=1 H X

p ν̂i K  2X, ν̂i K + 1

 ci−1 ) 1 − E(M

i=1 H h X

√

pK  2X, K +1

p ni K  2X, ni K + 1


ci−1 ) + ni 1 − ni σK µ E(M

i=1

(20)

(21)

(22) pK  i 2X , K +1 (23)

p NK  2X. (24) NK + 1 Tb1 and Tb3 are EXACT (their conditional expectations are affine ci−1 , so (1) collapses); Tb5 is EXACT by Remark 2; Tb2 is in M b4 is PLUG - IN , CLT / EVT, inheriting Remark 6. PLUG - IN ; T

 Tb5 = 1 −

D. Unlimited Signatures per File

Removing the capacity bound corresponds to K → ∞. For 0 < p < 1, pK → 0 and q → 1, so early termination becomes impossible (E(t) → 2X , σK → 0) and every node ci ) → Q nj ); the endpoints p ∈ {0, 1} is searched (E(M j≤i are degenerate and excluded. Theorem 2 then collapses accordingly. Q P Writing Ni = j≤i nj , the limits are T1 = 2X i Ni , P P T2 = 2HX , T3 = 2X i Ni−1 , T4 = 2X i ni and T5 = 2X . V. Known Number of Signatures

We now assume the exact number of signatures per layer, m1 , . . . , mH (with m0 = 1), is known in advance — e.g., from an index, a checksum manifest, or a prior coarse scan. For the capacity-one case, layer i contains mi−1 searched subtrees (ni nodes each), and the mi signatures occupy a uniformly random mi -subset of the mi−1 ni searched nodes.

For K = 1 these reduce to (3) and (4).

A. At Most One Signature per File 1) Sequential Search (S1 )

Lemma 4. If ν such nodes are searched in parallel, the expected completion time is  p νK  2X. E(t̂) = 1 − (19) νK + 1

Write ηi = mi−1 ni for the number of searched nodes of layer i. Under Assumption 2 every searched node is scanned: mi of them stop at a signature (mean X ), the other ηi − mi scan in full. By linearity,

Proof: The completion time is smaller than s only if every node holds exactly K signatures, an event of probability (pK )ν = pνK , in which case it is the maximum of ν i.i.d. variables νK with CDF (t/s)K , i.e., has CDF (t/s)νK and mean νK+1 s. νK νK νK Hence E(t̂) = p νK+1 s + (1 − p )s, which simplifies to (19). For K = 1 this is Lemma 2.

6

T1kn =

H X

2ηi − mi X,

(25)

i=1

which is EXACT and requires no independence between nodes.

2) Fully Parallel Layers (S2 )

If mi < ηi at least one searched node is empty and the layer takes exactly 2X (an empty node always scans its full file, VOLUME ,

and no node can exceed s). If mi = ηi , the layer time is the maximum of ηi uniforms. With the indicator 1{·}, H  X 1{mi = ηi }  T2kn = 1− 2X (exact). (26) mi + 1 i=1 3) Parallel Subtrees, Sequential Across (S3 )

Fi
 = P
(a given subtree is fully occupied) ηi (mi−1 −1)ni (zero when mi < ni ), i.e., mi mi −ni

= the hypergeometric probability that a fixed subtree receives ni of the mi signatures. A subtree that is not fully occupied contains an empty node and takes exactly 2X ; a fully i 2X in expectation. By linearity of occupied one takes nin+1 expectation over the mi−1 subtrees, H  X Fi  (exact). (27) T3kn = mi−1 1 − 2X ni + 1 i=1

Let

4) Sequential Subtrees, Parallel Across (S4 )

Let X1 , . . . , Xmi−1 be the signature counts of the subtrees of layer i. Since the mi signatures occupy a uniform subset of the ηi nodes, (X1 , . . . , Xmi−1 ) follows a multivariate hypergeometric law — not the uniform-composition (“stars and bars”) law, under which all count vectors would be equally likely. The two models differ substantially; see Section VI. Lemma
5. Let Xmin P ni ni x x=j x z . Then

=

P(Xmin ≥ j) =

mink Xk and φj (z)

[z mi ] φj (z) mi−1
, ηi

=

(28)

mi m

m

where [z ] extracts the coefficient of z ; P(Xmin = j) = P(Xmin ≥ j) − P(Xmin ≥ j + 1). The coefficient is computable by an O(mi−1 mi ni ) convolution. Proof: A placement with all counts ≥ j chooses xk ≥ j nodes P inside subtree k with x k k = mi ; the Qnumber of such mi placements is the coefficient of z in k φj (z), and all
ηi placements are equally likely. mi A subtree with x signatures takes xX + (ni − x)2X = (2ni − x)X in expectation. The subtree with the fewest signatures therefore has the largest conditional mean time, though not necessarily the largest realized time; identifying the layer maximum with it gives T4kn ≈

/mi−1 ⌋ H ⌊miX X i=1

P(Xmin = j) 2ni − j X.

(29)

j=0

Remark 7 (Nature of the approximation). (29) identifies the layer time with the expected time of the minimumcount subtree. Conditionally on the counts, however, the layer time is the maximum of random sums, which can be attained by another subtree; hence (29) is a lower bound, VOLUME ,

observed within about 2% of simulation in the configurations of Section VI.

5) Fully Parallel Tree (S5 )

Q Under Remark 2, S5 launches all Ni = j≤i nj nodes of layer i regardless of pruning, so it finishes before s only if mi = Ni for every i: QH  1{mi = Ni }  T5kn = 1 − i=1 P (exact). (30) 2X 1 + i mi B. At Most K Signatures per File

When a file can hold up to K signatures, the mi signatures of ci−1 ni searched nodes subject to layer i are placed into the M the capacity bound. Two placement conventions are natural, and we analyze both. Assumption 3 (Equal-composition placement, BE). All capacity-feasible count vectors (compositions) are equally likely — the Bose–Einstein convention for indistinguishable signatures. Assumption 4 (Uniform placement, MB). Each signature independently selects a node uniformly at random, conditioned on no node exceeding K — the Maxwell–Boltzmann convention, natural when signatures arise at nodes by independent physical processes. For K = 1 the two conventions coincide with each other and with the uniform-subset model of Section V-A; for K > 1 they genuinely differ (Section VIII). Both are captured by one generating-function device. Lemma PK r 6 (Capacity-constrained PK r counts). Let ϕK (z) = z and ψ (z) = K r=0 r=0 z /r!. The number of placements of m signatures into n nodes of capacity K is n,K Ωm = [z m ]ϕK (z)n (BE),

n,K Am = m! [z m ]ψK (z)n (MB),

n,K where Ωm is the capacity-constrained count derived in our companion paper [24]; every capacity-feasible configuration is equally likely within its convention. Both are computable by an O(nmK) convolution.

Three node-level probabilities drive the analysis; writing η for the (conditioned) number of searched nodes in the layer and suppressing the layer index, they are, under BE and MB respectively: P0 =

η−1,K Ωm

η,K Ωm Ω η−1,K PK = m−K η,K Ωm

or or

η−1,K Am η,K Am   η−1,K m Am−K η,K K Am

(node empty), (31) (node exactly K ), (32)

η−ni ,K Ω η−ni ,Ki Am−Kn i F = m−Kn or c (saturated), (33) η,K η,K Ωm Am
m where c = Kn (Kni )!/(K!)ni counts the ways of choosi

ing and arranging the signatures inside a saturated subtree.

7

Li et al.:

Q Each formula counts the placements of the remaining sig- Remark 2 all Ni = j≤i nj nodes of layer i are launched natures in the remaining capacity. A node is nonempty with irrespective of occupancy, so S5 is a single stage over the probability 1 − P0 , which gives the PLUG - IN recursion for the whole tree and (39) is EXACT. expected number of searched nodes, Corollary 1 (Totals and their plug-in). For j ∈ {1, 2, 3, 4}
ci ≈ EM ci−1 ni 1−P0 (mi , EM ci−1 ni , K) , c0 = 1, the total expected search time is the average of the condiEM M (34) tional layer times over the width distribution, Equation (34) is a mean-field recursion: P0 is nonlinear in H H X X   X
the width, so the exact propagation carries the full law of kn b c ci−1 = r τj,i (r), Tj = E τj,i (Mi−1 ) = P M ci (Remark 8) rather than its mean. Below, Pi,K denotes M i=1 i=1 r (40) (32) evaluated at layer i. ci = r) available from Remark 8, and Tb5kn = τ5 . with P(M Remark 8 (Integrality and the exact alternative). Unlike the For j ∈ {1, 2, 3} the averaging (40) is EXACT; for j = 4 it is capacity-one case, where the number of searched subtrees ci−1 is genuinely EXACT- IN - REGIME, being exact only when the scarcity condition is the known integer mi−1 , the width M mi < rK of (38) holds for every r of positive probability, random for K > 1: a node may hold several signatures, and otherwise leaving the residual mass to the open case so the count does not determine the number of occupied of Remark 9. Evaluating each layer at the rounded expected nodes. Hence (34) propagates an expected width, generally width instead of averaging gives the PLUG - IN form η,K η,K not an integer, whereas Ωm and Am are defined only for H X integer η (we evaluate at ⌊ηi ⌉); and Pi,K , Fi are nonlinear
bkn,plug = ci−1 ⌉ , T τj,i ⌊EM (41) j in ηi , so the plug-in approximates even before rounding. i=1 c The exact alternative is (1): propagate the full law of Mi , ci = k | M ci−1 = r) the which is what the numerical results of Section VI implement; whose conditional transition P(M same generating functions supply (supplementary material), it is cheaper than (40) by a factor equal to the support size the marginal following by summing over r. This needs of the width distribution. generating-function computations per layer; Section VI re- Remark 9 (The regime condition must be checked per ports a 0.07% plug-in error in the case examined, so we keep realization). The scarcity condition of (38) concerns the ci−1 is small. it by default, using the exact route when M ci−1 ] K does not imply mi < rK realized width: mi < E[M c for every r in the support. The exact average (40) checks Since Mi−1 is random (Remark 8), we state the results the condition at every r of positive probability; the plugconditionally on its realization and average afterwards, folin checks only the rounded mean width, so it may apply lowing (1). (38) to realizations violating it. The residual mass needs Theorem 3 (Conditional layer times). Fix a layer i and the capacity-constrained minimum-count distribution and is ci−1 = r, an integer, so that the layer has condition on M left open. In the configurations reported here the condition ηi (r) = r ni searched nodes. Let Pi,K (r) and Fi (r) denote holds with probability above 0.99, but a deployment near (32) and (33) evaluated at ηi (r) for the chosen convention the boundary should evaluate (40) term by term. (Assumption 3 or 4). Then the conditional expected time of layer i under strategy Sj is Proof sketch (full derivations in the supplementary material):  K Pi,K (r)  τ1,i (r) = r ni 1 − (35) (35): per-node expectation as in Lemma 3 with p replaced 2X, K +1 by Pi,K (r), summed over the ηi (r) nodes. (36) and (39):  1{mi = ηi (r)K}  a node finishes before s only with exactly K signatures; τ2,i (r) = 1 − 2X, (36) for all nodes this forces mi = ηi (r)K , which the capacity ηi (r)K + 1   constraint admits in one configuration under either convenFi (r) τ3,i (r) = r 1 − 2X, (37) tion, and the time is then the largest of η (r)K uniforms. i Kni + 1 τ4,i (r) = 2ni X (mi < r K), (38) (37): a subtree finishes early only if saturated (probability Q Fi (r)), giving the maximum of Kni uniforms; summing  Y = Ni K}  i 1{mi P over subtrees is affine in the width. (38): when mi < rK the τ5 = 1 − 2X, Ni = nj . 1 + K i Ni signatures cannot supply an exactly-K node to every subtree, j≤i

(39) Given the realized width r, (35)–(37) are EXACT: (35) and (37) because their conditional expectations are affine in the number of nodes and of subtrees, (36) because the saturated and non-saturated cases are exhaustive — and (38) is EXACT- IN - REGIME, valid whenever the realized width satisfies mi < rK . Expression (39) carries no layer index and no width argument: under the speculative semantics of 8

so some subtree scans all ni files fully and the layer time is the deterministic 2ni X (Remark 9). C. Unlimited Signatures per File

As K → ∞ the capacity bound disappears and early termination becomes impossible (Pi,K → 0): every searched node scans in full. The nonempty probability becomes m/(m + η − 1) under BE and 1 − (1 − 1/η)m under MB, VOLUME ,

(34) unchanged, and Theorem 3 reduces to Tb1kn = P applies P kn kn b b c c i−1 ]ni 2X , T2 = 2HX , T3 = i E[M i E[Mi−1 ] 2X , P Tb4kn = i 2ni X , and Tb5kn = 2X . VI. Numerical Results and Monte Carlo Validation

All closed forms of Sections IV and V were checked against a discrete-event Monte Carlo simulator that implements the model of Section III directly: trees are grown layer by layer under Assumption 1, or, for known counts, under the applicable placement law (uniform node subsets at capacity one; the BE or MB convention of Section V-B for K > 1); per-node scan times are drawn from the mixture, and each scenario’s completion time is measured on the sampled tree. Unless noted otherwise we use 105 –106 replications; the simulator and scripts are available from the authors.

C. The Mixture Variance and the S4 Regime

Modeling both node types matters most when signatures are sparse: assigning every node the signature-holding mean X understates the sequential layer time by (1 − p)/(2 − p), 33.3% at p = 0.5 and approaching 50% as p → 0, whereas the mixture mean (2 − p)X of Lemma 1 matches simulation to within 0.1% across p ∈ [0.1, 1]. Figure 2(a) reports the relative error of the S4 layer formula against simulation over (n, M ). With the standard deviation σ of (4) the error decays below 1% once n ≳ 50, consistently across M , and is onesided: the expansion overstates the layer maximum at small n, where µ(M ) has not yet settled. Outside the asymptotic regime (small n or M ≲ 10) we recommend numerical evaluation of the layer maximum, per Remark 6.

A. Exact Formulas

Exactness is a property of the derivation, not of a measurement: simulation can refute a claimed identity but cannot establish one. The EXACT labels are therefore earned in Sections IV–V, and simulation serves as an implementation check that analysis and simulator describe the same process. Under that reading, the EXACT expressions — namely T1 , T3 , T5 , the EXACT members Tb1 , Tb3 , Tb5 of Theorem 2, and, conditionally on the realized width, T1kn , T2kn , T3kn , T5kn — reproduce simulation to within Monte Carlo noise (< 0.1%) in every configuration tested (e.g., T3kn : 2.6875 predicted vs. 2.6870 simulated at mi−1 = 3, ni = 3, mi = 7), and (38) does so on the realizations satisfying its regime condition. Discrepancies elsewhere are attributable to the plug-in and asymptotic steps, quantified next. B. Cost of the Plug-in Step

Enumerating the width law exactly and comparing with (1) gives the unknown-count plug-in error directly. For T2 it is 0.07% in the design example (pn = 5), 1.1% at the prototype setting (pn = 3, where T4 gives 1.9%), and 74% in the subcritical case of Remark 5 (pn = 0.6). The product pni is the dominant predictor across our sweep but not the only one, since Bin(ni , p) fixes the spread and the extinction probability and not merely the mean: at fixed pni = 1.8 the error runs from 1.5% at (n, p) = (2, 0.9) to 13.3% at (18, 0.1). Read pni ≳ 2 as a heuristic, with (1) available whenever the margin matters. The known-count numerics for K > 1 use the plug-in form (41) of Corollary 1 — τj,i at the rounded expected width — rather than the exact average (40). Enumerating ci−1 in a configuration small enough to the full law of M admit it (K = 2, n1 = 3, m1 = 4, n2 = 2, m2 = 3, MB convention) gives an expected width of 2.5 — non-integer, as anticipated — and a second-layer term τ1,2 of Tb1kn equal to 4.1083 under exact conditioning against 4.1111 under the plug-in, a 0.07% discrepancy. The gap grows as the width ci−1 distribution spreads, so Remark 8 is preferable when M is small. VOLUME ,

D. Known-Count Occupancy Laws

Figure 2(b) compares P(Xmin = j) under the multivariate hypergeometric law of Lemma 5 and under the uniformcomposition law, against simulation of uniform signature placement within a single layer of mi−1 = 4 subtrees of ni = 8 nodes sharing mi = 10 signatures. The hypergeometric distribution matches simulation pointwise, and the resulting layer-time estimate (29) lies within 2% of simulation (Remark 7). The uniform-composition law that “stars and bars” counting would suggest is not equivalent: it overstates P(Xmin = 0) by a factor of about five here and the layer time by 4%, a gap that can widen with mi . The conventiondependent probabilities (31)–(33) were verified by rejectionsampling the conditioned multinomial law, which realizes uniform placement directly. At (η, K, m) = (4, 2, 5): P0 formula 0.1500 against 0.1510 sampled, PK 0.4000 against 0.4012, saturation probability F for a two-node subtree 0.1000 against 0.1008, and the S1 layer time 3.4667 against 3.4661; agreement is equally close at (6, 3, 10). The same two configurations give PK = 0.4375 and 0.2839 under BE — 9% and 31% away from their MB counterparts — confirming that the choice of convention is quantitatively consequential. The two are not interchangeable defaults: MB suits signatures arising by independent processes, BE a feasible allocation drawn uniformly, which connects to the counting theory of [24].

E. Scenario Comparison

The strategies separate by growth order in the fan-out n: the speedup over S1 is Θ(nH ) for S2 and S5 , Θ(n) for S3 , and Θ(nH−1 ) for S4 up to the logarithmic extreme-value correction — one power of n short of full parallelism, the price of scanning each subtree sequentially. Only the S3 /S4 pair has an order that changes with (H, n), since theirs are the two exponents that can coincide; Section VII locates the crossing. 9

Li et al.:

M=5 M = 20 M = 100

4 2

(b) subtree occupancy law

(Xmin = j)

layer-time error (%)

(a) S4 formula error, ±1% band shaded

0 101

subtree size n

102

simulation hypergeometric (Lemma 5)

0.6 0.4 0.2 0.0

0

1 j

2

FIGURE 2. (a) Relative error of the asymptotic S4 layer-time formula (10) against simulation (p = 0.5), using the variance (4); the shaded band is ±1%. (b) P(Xmin = j) under the multivariate hypergeometric law of Lemma 5 against simulation of uniform placement within one layer : mi−1 = 4 subtrees of ni = 8 nodes, carrying mi = 10 signatures between them.

VII. Applying the Analysis

TABLE 2. A priori strategy selection: H = 4, n = 10, p = 0.5. Times in

The closed forms are meant to be used before any file is read. We illustrate that on a design example, then measure how far the idealization carries in real execution.

units of the full-file scan s; Cres = Ppeak T per Definition 1, computed from

A. A Design Example 4

An archive of roughly 10 files forms a 4-layer tree with fanout n = 10; a searched file holds a signature with probability p = 0.5. Which parallelism is worth its cost? Table 2 answers from Section IV, using (13) for S4 . Definition 1 (Reservation cost). Let Ppeak be the expected peak concurrency — the largest expected number of nodes run at once, maxi E(Mi−1 )ni for S2 — and T the completion time. We report Cres = Ppeak T , the cost of reserving that capacity for the run. It is a planning figure at the mean width, not a worst-case P guarantee, and it is not processor-seconds, which equal v E(tv ) — identical for S1 –S4 , larger for S5 . Cres prices reserved capacity but not elapsed time, so S1 minimizes it by construction: its single processor is busy throughout, and its reserved rectangle coincides with the work performed, which no parallel schedule can undercut. A monetary account would add a term for the time itself — a deadline penalty, or the opportunity cost of the reserved window — and the ordering it induces can differ from, or invert, the ordering by latency, since the two extremes differ by a factor of 1170 in time and 11110 in processors. This paper supplies the physical quantities T and Ppeak and their exactness; pricing them into a joint objective, where the optimum depends on the price ratio and on the tree shape at once, is a harder problem and is the subject of a companion paper. The table brackets the strategies and then separates the one pair that inspection cannot. S1 and S5 are the extremes: 1170 time units on one processor against 1.0 on 11110, the latter being the floor of Remark 2. Their order in time is evident, but fixing them is not idle, because they are the 10

unrounded predictions. S4 uses the hybrid rule of Remark 6, which selects the numerical route (13) at n = 10.

Strategy

Pred.

Sim.

Ppeak

Cres

S1 sequential S2 layer-parallel S3 subtree-parallel S4 subtrees-parallel

1170.0 4.0 156.0 35.2

1173.8 4.0 156.5 35.1

1 1250 10 125

1170 5000 1560 4394

1.0

1.0

11110

11110

S5 all-parallel

endpoints any cost objective must interpolate between, and an objective that also prices processors need not order them the same way — S1 is the cheapest schedule in reserved capacity and the most expensive in elapsed time. S2 shows how quickly the return on parallelism decays: it reaches 4.0 using 1250 processors, so the remaining 3.0 units down to the floor cost the other 9860 processors. S3 and S4 are the pair whose order is not fixed, and the reason is that their speedups grow differently in n: Θ(n) for S3 , whose layer time scales with the width Mi−1 because subtrees run one after another, against Θ(nH−1 ) for S4 , whose layer time depends on the width only through the logarithmic µ. Depth therefore helps S4 and not S3 : at p = 0.5 and uniform fan-out, S3 returns 4.51 at n = 6 for any H , while S4 gains a factor of n per layer. The two cross near n = 8 for H = 3 and below n = 4 for H = 4, so the configuration here puts S4 ahead at 33.2 against 7.5 while the shallower tree of Table 3 reverses it, 4.5 against 3.8; S3 ’s invariance in H is itself an artifact of the uniform fan-out, since its speedup is in general a width-weighted average of per-layer ratios. Deciding this pair is what the S4 derivation of Section IV is for. Simulation confirms every prediction to within 0.5%, including S4 , for which the hybrid rule selects the numerical route (13) at this fan-out. VOLUME ,

TABLE 3. Multicore prototype: measured speedup over S1 (median [IQR] over 8 trees) against the analytical prediction. “Tasks” is the number of units dispatched per run; “rounds” is the number of synchronization barriers.

W =8

W =4

theory

Strategy med. [IQR]

med. [IQR]

tasks rounds unbdd.

S2 S3 S4 S5

3.07 2.59 2.58 3.45

3.69 3.03 3.02 4.30

[3.32, 4.02] [2.61, 3.23] [2.42, 3.33] [3.58, 4.66]

[3.01, 3.17] [2.53, 2.70] [2.36, 2.73] [3.34, 3.57]

78 78 13 78

3 13 3 1

19.5 4.5 3.8 58.5

B. A Multicore Prototype

The analysis idealizes execution: processors are unbounded and dispatch is free. To see how far that carries, we ran the five strategies as real concurrent programs on an Apple M1 (4 performance and 4 efficiency cores, macOS 26.2, Python 3.11.3, multiprocessing with fork). Each strategy is a dispatch schedule executed by operating-system processes over real files, so the measured times include process creation, scheduling and synchronization costs that the model does not predict. Each node owns a 1 MB file scanned in 64 KB chunks, with early termination at the chunk holding the signature, so the work is proportional to the bytes examined; the supplementary material gives the implementation details. We report medians and interquartile ranges over 8 independent trees grown with a common fanout (H = 3, ni = n = 6, p = 0.5), each repeated twice, with the S1 baseline measured within the same tree. Layer widths vary across realizations; the tasks and rounds in Table 3, and the 63.2 MB scanned per tree quoted below, are medians, the median tree having widths 1, 3, 9 and thus 78 searched nodes. What the prototype does and does not test. All five strategies run on the same tree realization, so their total work is identical by construction (median 63.2 MB). This isolates execution order, the worker cap and synchronization, but it also means the prototype’s S5 is not the speculative variant of Remark 2. With that and the synthetic payloads, the measurements speak to scheduling behavior alone: not to the extra work speculation would incur, nor to what a real corpus would cost. Three observations follow from Table 3. First, absolute speedups collapse towards the worker count: all strategies do identical total work, so a work-conserving execution on W processors cannot beat W : for reference, the unbounded 19.5× and 58.5× for S2 and S5 are measured as 3.7× and 4.3× on eight workers. Doubling W from four to eight adds only 17–25%, the additional concurrency having to engage the efficiency cores: on a heterogeneous machine the core count overstates the parallelism available. At W = 8 the binding limit also differs by strategy: 8 for S2 and S5 , but 4.5 and 3.8 for S3 and S4 , capped by their own structure. Second, the coarse separation is reproduced — S5 , then S2 , then the subtree-level pair — as predicted at that VOLUME ,

granularity. Third — and not predicted by the model — measurement does not separate S3 and S4 at all. This tree sits just below the crossing of Section VII-A, so the formulas already place them close, S3 ahead by 20% (4.5 vs. 3.8); measurement closes even that gap, to within 0.01 at both worker counts, with heavily overlapping interquartile ranges and a median difference that varies between repetitions of the same configuration (0.08 vs. 0.01 at W = 4; supplementary material). This is consistent with the task column: S3 issues one dispatch round per subtree (13 barriers over 78 tasks) whereas S4 issues one task per subtree and synchronizes once per layer, so when per-node work is small relative to dispatch cost the barrier count can offset the advantage the latency model assigns; we did not isolate barrier cost directly. Strategies this close in predicted latency should be separated by their synchronization structure, not by the formulas. A bounded-pool analysis (⌈ν/W ⌉ rounds per layer, with the extreme-value argument inside a round) is the natural next step.

C. Cost of the Analysis

Both information conditions are cheap to evaluate, though not equally so: O(H) arithmetic operations for unknown counts, independent of tree size, against polynomialconvolution computations per layer for known counts, which grow with the signature counts and are the binding cost when mi is large (supplementary material). Every quantity in Table 2 was computed in under a millisecond, against minutes for the corresponding Monte Carlo estimate. The margin matters less for planning than for revision. A scheduler that re-evaluates as each layer completes knows the realized width Mi−1 and can use the conditional τi (Mi−1 ) directly, which removes the width plug-in and its error. Every other qualification stands: τ4 still carries its CLT/EVT approximation or the grid error of (13).

VIII. Discussion A. Approximations and Their Ranges

Expressions not listed below are exact or exact-in-regime under the stated model. Four approximations are used, all quantified in Section VI. A1, the plug-in Eg(M ) ≈ g(EM ) of Remark 5, affects T2 , T4 and their ≤ K analogues, where pni predicts its size well enough to guide use: under 2% on the trees reported here but 74% at pni = 0.6, with (1) available instead. In the known-count totals of Corollary 1 the same step draws on the spread of the capacity-constrained width and is far smaller (0.07%). A2 and A3, the extremevalue expansion µ(M ) and the CLT for subtree sums, enter the S4 formulas only jointly; the combined approximation stays within about 1% for M ≳ 10 and ni ≳ 50, and (13) replaces both outside that regime. A4, identifying the layer maximum with the minimum-count subtree in (29), is a lower bound within about 2%. 11

Li et al.:

B. Limitations and Extensions

The model assumes homogeneous subtrees, uniform signature positions, the inheritance property of Assumption 1, no cancellation (Assumption 2), and unbounded processors. The last is the most consequential: with W workers the attainable speedup is capped at W and eroded by dispatch overhead, which the prototype shows can leave two strategies indistinguishable that the formulas separate by 20% (Section VIIB). One regime is left open: on widths r with mi ≥ rK the known-count S4 layer time needs a capacity-constrained minimum-count distribution we do not derive. Evaluating (40) term by term handles the regime-satisfying widths exactly and isolates the rest. Heterogeneous fan-outs ni,j leave T1 /T3 -type results intact (linearity) but complicate the extreme-value analysis; non-uniform position distributions are handled by the general-CDF forms of Section IV-B, under which sequential stages depend on the discovery-time law only through its first two moments while parallel stages depend on the full CDF. Beyond time, the monetary cost of reserving processors for tree search — and the design of tree shapes that minimize a joint time–cost objective — builds directly on the expressions derived here and is treated in a companion paper. IX. Conclusion

We derived a priori computable expected search times for signature searching in multi-level tree networks under five search strategies, two information conditions (known and unknown signature counts), and three per-file capacity classes. The analysis rests on a mixture model of node scan times, order statistics for parallel stages, and, for known counts, the multivariate hypergeometric law of subtree occupancy. Formulas were checked against Monte Carlo simulation and classified as exact, exact-in-regime, plug-in, asymptotic, or bounded, with quantified accuracy ranges for the latter three. The framework thus delivers a prediction available before any file is read, together with a statement of how far to trust it: the design example of Section VII is answered in under a millisecond to within 0.5% of simulation. Extending the analysis to a bounded processor pool and closing the open capacity-constrained regime are the natural next steps; the expressions derived here also supply the temporal building blocks for cost-optimal tree design, treated in a companion paper. Acknowledgment

The authors used Anthropic Claude to draft and edit the English prose and grammar. All results and conclusions are the authors’ own, who verified every derivation, number and reference and take full responsibility.

[2] V. Bharadwaj, D. Ghose, V. Mani, and T. G. Robertazzi, Scheduling Divisible Loads in Parallel and Distributed Systems. Los Alamitos, CA: IEEE Computer Society Press, 1996. [3] T. G. Robertazzi, “Ten reasons to use divisible load theory,” IEEE Computer, vol. 36, no. 5, pp. 63–68, May 2003. [4] V. Bharadwaj, D. Ghose, and T. G. Robertazzi, “Divisible load theory: A new paradigm for load scheduling in distributed systems,” Cluster Computing, vol. 6, no. 1, pp. 7–17, 2003. [5] T. G. Robertazzi and L. Shi, Networking and Computation: Technology, Modeling and Performance, 2nd ed. Springer, 2020. [6] O. Beaumont, H. Casanova, A. Legrand, Y. Robert, and Y. Yang, “Scheduling divisible loads on star and tree networks: Results and open problems,” IEEE Trans. Parallel Distrib. Syst., vol. 16, no. 3, pp. 207–218, Mar. 2005. [7] X. Wang, B. Veeravalli, K. Wu, and X. Song, “Extension of divisibleload theory from scheduling fine-grained to coarse-grained divisible workloads on networked computing systems,” Mathematics, vol. 11, no. 7, Art. no. 1752, 2023. [8] C. Xu, S. Chen, J. Su, S. M. Yiu, and L. C. K. Hui, “A survey on regular expression matching for deep packet inspection: Applications, algorithms, and hardware platforms,” IEEE Commun. Surveys Tuts., vol. 18, no. 4, pp. 2991–3029, 2016. [9] J. Dean and S. Ghemawat, “MapReduce: Simplified data processing on large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, 2008. [10] M. Zaharia et al., “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing,” in Proc. USENIX NSDI, 2012, pp. 15–28. [11] J. M. Abuı́n, J. C. Pichel, T. F. Pena, and J. Amigo, “SparkBWA: Speeding up the alignment of high-throughput DNA sequencing data,” PLoS ONE, vol. 11, no. 5, p. e0155461, 2016. [12] M. AlJame and I. Ahmad, “DNA short read alignment on Apache Spark,” Applied Computing and Informatics, vol. 19, no. 1/2, pp. 64– 81, 2023. [13] A. Broder and M. Mitzenmacher, “Network applications of Bloom filters: A survey,” Internet Mathematics, vol. 1, no. 4, pp. 485–509, 2004. [14] R. Nelson and A. N. Tantawi, “Approximate analysis of fork/join synchronization in parallel queues,” IEEE Trans. Comput., vol. 37, no. 6, pp. 739–743, Jun. 1988. [15] A. Thomasian, “Analysis of fork/join and related queueing systems,” ACM Comput. Surv., vol. 47, no. 2, art. 17, pp. 1–71, 2014. [16] M. Mohanty, G. Gautam, V. Aggarwal, and P. Parag, “Analysis of forkjoin scheduling on heterogeneous parallel servers,” IEEE/ACM Trans. Netw., vol. 32, no. 6, pp. 4798–4809, Dec. 2024. [17] H. Wang and O. Sinnen, “Scheduling fork-joins to heterogeneous processors,” in Euro-Par 2023: Parallel Processing Workshops, LNCS 14351. Cham: Springer, 2024, pp. 318–329. [18] J. Dean and L. A. Barroso, “The tail at scale,” Commun. ACM, vol. 56, no. 2, pp. 74–80, Feb. 2013. [19] G. Ananthanarayanan, S. Kandula, A. Greenberg, I. Stoica, Y. Lu, B. Saha, and E. Harris, “Reining in the outliers in Map-Reduce clusters using Mantri,” in Proc. USENIX OSDI, 2010, pp. 265–278. [20] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica, “Effective straggler mitigation: Attack of the clones,” in Proc. USENIX NSDI, 2013, pp. 185–198. [21] N. L. Johnson and S. Kotz, Urn Models and Their Application: An Approach to Modern Discrete Probability Theory. New York: Wiley, 1977. [22] W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1, 3rd ed. New York: Wiley, 1968, ch. II. [23] M. Raab and A. Steger, “‘Balls into bins’ — A simple and tight analysis,” in Randomization and Approximation Techniques in Computer Science (RANDOM), LNCS 1518. Springer, 1998, pp. 159–170. [24] J. Li and T. G. Robertazzi, “Capacity constraints in ball and urn distribution problems,” Results in Applied Mathematics, vol. 26, Art. no. 100592, 2025. [25] H. A. David and H. N. Nagaraja, Order Statistics, 3rd ed. Wiley, 2003. [26] H. Cramér, Mathematical Methods of Statistics. Princeton Univ. Press, 1946.

REFERENCES [1] Z. Ying and T. G. Robertazzi, “Signature searching in a networked collection of files,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 5, pp. 1339–1348, May 2014.

12

VOLUME ,

Related documents

• Probabilistic Performance Analysis of Parallel Signature Search Strategies in Multi-Level Tree Networks#785226
• Probabilistic Performance Analysis of Parallel Signature Search Strategies in Multi-Level Tree Networks#783635
• CBOR Object Signing and Encryption (COSE): Hash Algorithms#502494
• HIV modelling - parallel implementation strategies#641815
• CAS II: Symmetric Partitions as Kolmogorov Models#1154551