diff 2bdbbf5..f6bf760 k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt
index ee8319d..865f58f 100644
--- a/k_server_squared_log_v2.txt
+++ b/k_server_squared_log_v2.txt
@@ -335,134 +335,6 @@ as a UNIVERSAL LOWER bound (you cannot do better), but it is FALSE
that O(log k) works as an upper bound for every metric. Some
metrics need log^2 k.
-------------------------------------------------------------------------
-4. THE HISTORY: FROM K TO (2K-1) TO LOG K TO LOG^2 K
-------------------------------------------------------------------------
-
-This section is the "who proved what" that motivates the main
-theorem. Every fact has a citation in the paper's references at the
-end. You can skip to Section 5 if you just want the statement.
-
-4.1 Deterministic era (1988 - 1995).
-
- - 1988, 1990. Manasse, McGeoch, Sleator. Introduced the problem.
- Proved the deterministic lower bound k for metrics with > k
- points. Conjectured k is achieved.
- - 1995. Koutsoupias, Papadimitriou. Proved that the "work
- function algorithm" achieves ratio (2k - 1). Stunning result:
- one algorithm, all metrics, essentially the same constant for
- every metric.
- - 2026 (preprint, Sept). Coester, Koutsoupias, Zbysinski.
- Announced a k-competitive analysis of the work-function
- algorithm. This would prove the original conjecture.
-
-4.2 Randomization: paging is easy (1991).
-
- - 1991. Fleming, Karp, Luby, McGeoch, Sleator, Young. A
- harmonic lower bound H_k on uniform metrics, and a randomized
- marking algorithm achieving 2 H_k.
- - 1991. McGeoch, Sleator. Improved the upper bound to exactly
- H_k, matching the lower bound.
-
-So paging is completely solved: exact ratio H_k.
-
-4.3 Weighted paging reaches log k (2012).
-
- - 2012. Bansal, Buchbinder, Naor. Weighted paging in O(log k)
- competitive ratio, via a fractional primal-dual algorithm plus
- an online rounding. This is exactly the order achieved by the
- marking algorithm in the unweighted case, but for a harder
- problem.
-
-These paging successes fueled the folklore conjecture: "randomized
-k-server should be O(log k) on any metric".
-
-4.4 General-metric upper bounds, polylog (2010 - 2018).
-
- - 2010 (SODA). Bansal, Buchbinder, Naor. First (fractional)
- result for general finite metrics after a tree embedding.
- - 2015 (JACM). Bansal, Buchbinder, Madry, Naor. The first
- POLYLOGARITHMIC upper bound for arbitrary finite metrics. The
- bound is
-
- O( (log^2 k) * (log^3 n) * (log log n) ),
-
- where n is the number of points in the finite metric. So this
- factors a log(k)-squared piece (good) and many log(n) factors
- (not good: not in k alone).
-
- - 2018 (STOC). Bubeck, Cohen, Lee, Lee, Madry. Improved the
- bound on "hierarchically separated trees" (HSTs) to
-
- O(log^2 k),
-
- using "multiscale entropic regularization". But on general
- n-point metrics, the STATIC embedding reduction only gives
-
- O(log^2 k * log n),
-
- which is not a bound in k alone. The log n factor is the
- obstruction.
-
- - 2018 (FOCS). James Lee. Attempted an "evolving, fusible HST"
- framework that changes the tree as requests arrive. The
- general competitive-ratio claim was WITHDRAWN in 2021 by an
- erratum in Section 5.3.2. But the METHOD - "heavy-ball
- protection" and "accounting for changing partitions" - is
- the conceptual ancestor of the paper we are explaining.
-
- - 2026 (ICALP). Coester and Cosson. Made the HST / finite-metric
- bounds POLYNOMIAL TIME, with total number of random bits
- independent of the request length. But their general finite
- metric ratio retains a log n factor.
-
-4.5 Lower bounds (1994 - 2023).
-
- - 1994 - 2005. Karloff-Rabani-Ravid, Blum-Karloff-Rabani-Saks,
- Bartal-Bollobas-Mendel, Bartal-Linial-Mendel-Naor. Developed
- metric decomposition / Ramsey methods, weakening randomized
- k-server lower bounds upward.
- - 2023 (STOC). Bubeck, Coester, Rabani. THE RANDOMIZED
- K-SERVER CONJECTURE IS FALSE. Two main results:
- (i) Theorem 11 + Proposition 8. There exist metrics with
- only (k+1) points requiring competitive ratio
- Omega(log^2 k), even allowing a FIXED additive constant.
- This is the sharp negative answer to the folklore
- conjecture.
- (ii) Corollary 20. Universal lower bound Omega(log k) on
- EVERY metric with more than k points. (This matches
- the paging lower bound and is not contradicted by
- (i): (i) says SOME metrics need log^2 k, which is
- more than log k; (ii) says no metric can be easier than
- log k.)
-
-4.6 What is left? The puzzle of the two logs.
-
-After 2023, the situation is:
-
- - NO metric has a lower bound worse than log^2 k (BCR).
- - SOME metric has a lower bound as bad as log^2 k (BCR).
- - NO constructed strategy for general metrics achieves the
- log^2 k order. The best constructions retain a log n factor
- from the static embedding.
-
-The obvious question: can we prove an upper bound of O(log^2 k)
-matching the BCR lower bound? On EVERY metric, not just HSTs?
-
-The paper we are explaining proves exactly this.
-
-4.7 The main theorem in one sentence.
-
- On every metric, one randomized online strategy has expected
- competitive ratio O((log(k+1))^2), with a finite additive
- correction. When starting positions are distinct, no additive
- correction is needed.
-
-The additive correction is unavoidable when two of the initial
-servers start on the same point, because a "shadow" simulation
-(line 8.3) needs to bridge the gap. In every other case, the bound
-is exact in every input.
-
------------------------------------------------------------------------
5. THE MAIN THEOREM
------------------------------------------------------------------------
@@ -539,194 +411,6 @@ absolute c' > 0 (up to a fixed additive term). So the upper bound
ours and the lower bound theirs disagree at most in the absolute
constant. In that sense the theorem is order-tight.
-------------------------------------------------------------------------
-6. THE BIG PICTURE: HOW THE PROOF IS BUILT
-------------------------------------------------------------------------
-
-At the very highest level, the proof has seven steps. Each step is
-an idea you could explain to a friend. Each subsequent section fills
-in the details. You can read this section first, then read
-subsequent sections, and you will always know where you are.
-
-6.1 Step 1: fix a "hidden optimal solution" and watch its shadow.
-
-Idea. Pretend we cannot see the future, but SOMEONE can. Let that
-someone choose, for each possible future, the best sequence of
-server labels. Treat that chosen sequence as a hidden random
-variable "Z" determined by the request sequence. From the revealed
-prefix we can compute the CONDITIONAL DISTRIBUTION of Z. That
-conditional distribution is called the "posterior".
-
-Think of the posterior as a "shadow" of the hidden optimal solution
-projected onto the current observed history. The shadow is what we
-can actually see.
-
-This is a standard trick in online algorithms and it is central to
-the paper. It converts the online problem into:
-
- "Track the posterior distribution of a hidden optimal solution
- online."
-
-The posterior is a probability distribution over configurations of
-k labeled servers. It is the thing we want to stay close to.
-
-Now, catching up with a DISTRIBUTION is much harder than catching
-up with a POINT. The whole engineering of the paper is about
-representing the distribution in a compact, trackable form. This is
-where tree embeddings, partitions, and rounding all come in.
-
-6.2 Step 2: reduce the true metric to a fixed tree.
-
-Idea. On a tree, moving servers is easy to analyze. On a general
-metric, it is not. Standard theory says: any finite metric can be
-approximated by a tree with O(log n) distortion - and if you are
-careful and change the tree adaptively, you can hope to keep the
-distortion to log k instead of log n.
-
-But the paper does NOT use an approximation of the metric in a naive
-way. It uses something subtler. It builds ONE fixed finite object
-called a "prefix tree of label strings" whose leaves correspond to
-the points of the metric (approximately), and whose edges carry
-"semantic" weights.
-
-The point of the tree is that the posterior distribution's "serving"
-problem on the tree can be solved and tracked by a fractional
-algorithm, and then realized back in the metric.
-
-6.3 Step 3: allocate fractional server mass on the tree.
-
-Idea. On the tree, we want to keep some real-valued "amount of
-serving mass" q_v at each vertex v, with these rules:
-
- (i) The root holds q_root = k, exactly.
- (ii) The children of any vertex v hold amounts that sum to at
- most q_v. (We "spend" all mass going down, or "park" any
- leftover at v itself.)
- (iii) For every vertex v, q_v is at most a constant times the
- posterior expected number of hidden servers in v's
- subtree. So mass is dominated by the shadow.
- (iv) The leaf of every request in the CURRENT tree holds at
- least 1. So the request is always "servable".
-
-If we can maintain such q_v whose CHANGES stay small (sum of
-r_{depth} * |change| is O(log k) times the shadow's movement), and
-we then round it, we get a strong online algorithm.
-
-This is the content of what the paper calls the "allocation
-theorem". It is the hardest single technical component of the
-paper. It uses:
-
- - rank coordinates (the probability that a subtree contains fewer
- than a hidden servers);
- - convex "rank functions" l^beta(p) with parameters tuned to subtree
- sizes;
- - a "simplex tracker" to make proportions vary slowly;
- - a "side tracker" to handle near-dominant children;
- - hysteresis to choose between two output rules.
-
-We will explain the conceptual role of each in Section 11.
-
-6.4 Step 4: choose tree partitions that adapt to local mass.
-
-Idea. The tree structure needs to be built from the metric. It
-cannot follow the fastest-changing ball-mass ratios at every scale,
-because doing so would cost another factor of log. Two structures
-solve this:
-
- - "Heavy balls": balls around requests where the mass is very
- concentrated. Only ONE change per request per level.
- - "Chronological rosters": a small list of balls per level,
- chosen by a deterministic age rule, with a random subroster.
- Changes cost less on average because of the random retire.
-
-Both structures use the pilot potential (Section 6.5) to PAY for
-changes.
-
-The clever bit is that the coefficient on changes is a LOCAL mass
-ratio, not a global worst case. When the ball-mass ratio is small
-(very concentrated), changes are cheap. When it is large, there are
-few such levels (a telescoping "ball-mass" argument controls the
-sum). This local-ratio trick is the reason the log-n factor
-disappears.
-
-6.5 Step 5: pilot potential - a brake for changes.
-
-Idea. Whenever a partition changes, the allocation q_v will likely
-change too. We want to charge those q-changes to something. The
-"pilot potential" is a compact variational object that gives a
-NUMERICAL potential value small enough that its decreases pay for
-the changes, yet large enough that its increases are bounded by
-O(log) times the hidden mover's physical cost.
-
-Concretely, at each scale r, define a function L_r(mu, g) of a
-measure mu and a function g, as the MINIMUM over certain "vector
-of sites" z of a linear functional. Two properties are proved:
-
- - L_r is concave in mu, so filtering (revealing more of the
- history) cannot increase it in conditional expectation.
- - Its DRIFT (physical movement of the hidden mover at scale r)
- is at most O(log k) times the mover's distance, by a local
- concentration argument.
-
-The concavity and drift together make L_r a legitimate potential
-that can be "spent" on partition edits without paying more than
-O(log k) per unit of hidden movement, uniformly in scale.
-
-The "local concentration" step is where the extra log comes from.
-When a scale is "concentrated", the integrator's optimal site is
-almost AT the request, so moving it is cheap. When a scale is "not
-concentrated", the potential is trivially bounded and only a few
-such scales exist by the ball-mass telescope.
-
-6.6 Step 6: real-metric rounding and moving representatives.
-
-Idea. The q_v from Step 3 are REAL NUMBERS. We need k INTEGERS on
-the tree (one per tree vertex, summing to k) whose values stay
-close to q_v in conditional expectation. Also, since the actual
-points of X are represented by tree anchors, we must pay whenever a
-retained tree vertex's anchor moves to a new nearby anchor.
-
-Both are handled by clean local arguments:
-
- - "Balanced rounding with prescribed random total" gives an
- integer n_v with the right mean and with |change| at most 32
- times the fractional changes plus 11 times a small dependence
- on the parent.
-
- - "Retained-anchor travel" pays moving anchors using a normalized
- potential, with a size tracker that resets only when a key's
- posterior size drifts by a factor of 6/5.
-
-Both are local: no horizon-dependent factor.
-
-6.7 Step 7: transfer from one law to one policy.
-
-Idea. Steps 1-6 prove the theorem for a FIXED finite metric and a
-FIXED finite probability distribution on finite request sequences.
-We need to get rid of that.
-
-Three ingredients in the paper:
-
- - "Episode amplification". Cleverly concatenate forward, reversed,
- and reset blocks so that the ADDITIVE term gets amortized away
- over N episodes. Choose N large enough. This gives a policy
- with no additive term on a fixed finite metric, distinct start.
-
- - "Finite separation via Yao". Using the finite minimax theorem,
- turn "for every single sequence there exists some strategy" into
- "there is ONE strategy for every sequence in a finite family".
-
- - "Tychonoff compactness". Take the product of all decision-point
- simplices (one simplex per possible history). The product of
- compact simplices is compact. The "for every finite input there
- is a policy" constraint defines closed subsets of this product.
- Finite-intersection property says ONE policy works for ALL
- finite inputs simultaneously.
-
-Together, these remove every dependence on the input law, the
-horizon, and the size of the metric. What remains is exactly the
-main theorem's statement.
-
------------------------------------------------------------------------
7. THE BOARD: NOTATION WE WILL USE EVERYWHERE
------------------------------------------------------------------------
@@ -1660,7 +1344,7 @@ Dominant. Split at y = 1.
= (1/H) log(1 + H/u).
With u <= 1/4 and H = 1 + log(1/u), H/u <= 4H, so
log(1+H/u) <= log(1+4H) <= 3H, giving <= 3.
- On [1, infty]: u + Hy(1+y) >= Hy^2, so
+ On [1, infinity]: u + Hy(1+y) >= Hy^2, so
int_1^infinity dy/(u+Hy(1+y)) <= int_1^infinity dy/(Hy^2) = 1/H <= 1.
Total <= 4.
@@ -1696,7 +1380,7 @@ alpha_i = 0 contribute nothing (continuous extension).
bounded by C(u + T_alpha).
**Dominant term.** Put g(y) = e^{-y} y(1+y) for y >= 0. It is
-continuous on [0, infty], vanishes at both ends, and its maximum
+continuous on [0, infinity], vanishes at both ends, and its maximum
is 4 e^{-2} / sqrt(5)... concretely g attains ~0.84 < 1 at
y = (3+sqrt(5))/2.
@@ -2566,7 +2250,7 @@ Summing (a), (b), (c) and renaming the total coefficient as a
single larger absolute C_P:
P <= C_P ell Q + D_part,
- D_part := D_H + D_ins + D_phys < infty.
+ D_part := D_H + D_ins + D_phys < infinity.
This is the statement fed into Section 11 (the "embedded cost"
proposition). The partition construction contributes exactly ONE
@@ -3675,315 +3359,6 @@ For SMALLER families of metrics (paging, HSTs, etc.), tighter bounds
continue to hold; the theorem is a worst-case over metrics and does
not claim to be tight on any particular family.
-17.7 The proof is explicit (in principle).
-
-Every lemma is a closed-formula object:
- - l^beta is a convex piecewise function with explicit constants.
- - The simplex tracker is an argmin of an explicit integral.
- - The pilot potential is a specific finite-dimensional min.
- - The rounding lemma is a specific local exchange.
-
-You can in principle SIMULATE every piece. The proof does not
-address complexity; polynomial-time versions require separate
-work (Coester-Cosson 2026), and the theorem we are explaining
-makes no such claim.
-
-------------------------------------------------------------------------
-18. HONEST LIMITS: WHAT THE PAPER DOES NOT CLAIM
-------------------------------------------------------------------------
-
-18.1 No efficiency.
-
-The theorem asserts EXISTENCE of a policy with the stated
-competitive ratio. It says nothing about whether you can compute
-the policy's next move in polynomial time. The compactness
-construction (Section 16.4) is thoroughly non-constructive. For
-implementations, extra work is needed, and that work belongs to
-separate literature.
-
-18.2 No tight constants.
-
-The universal constant C in the main theorem is astronomical (a
-product of many "12 C_A C_P ..." hiding several hundred digits of
-internal absolutes). The paper does not try to minimize C. It could
-be 10^50 and the theorem would still hold. The point of O(log^2 k)
-is the asymptotic growth rate in k.
-
-18.3 The additive term is real.
-
-When two starting servers occupy the SAME point, the additive term
-B cannot generally be zero. The episode amplification produces
-B = (alpha + 1) D where D = M(s, u) is the matching distance to the
-nearest DISTINCT tuple u. There is no claim to remove B in this
-case.
-
-18.4 No new lower bound.
-
-The paper proves an upper bound. It does not prove a matching lower
-bound. It uses the existing Omega(log^2 k) lower bound of BCR 2023.
-The theorem is "matches the known lower bound", not "discovered the
-true factor".
-
-18.5 No claim of "best possible for each metric".
-
-The O(ell^2) bound is tight OVER ALL METRICS. On specific metrics
-the true optimum may be smaller. The theorem does not claim to be
-tight on paging, on HSTs, on trees, or on any particular family.
-
-18.6 No "natural" online rule.
-
-The construction uses:
- (i) a finite distributional estimate that depends on the input
- law;
- (ii) episode amplification to remove that law;
- (iii) Yao / Kuhn to reach a single behavioral policy on finitely
- many inputs;
- (iv) Tychonoff compactness to reach one policy for every input.
-
-At no point is there a "simple, human-improvise-this" rule. That is
-by design: the point is existence, not implementation.
-
-18.7 What "log" means.
-
-All logarithms are natural (base e). Base-2 logarithms differ by a
-fixed constant (1/ln 2), and the statement C (log)^2 with an
-absolute C is unchanged in order by switching bases.
-
-18.8 What the metric space can be.
-
-Nonempty and with at least k+1 points. Otherwise the deterministic
-lower bound "more than k points" is not present, and the offline
-game is trivial (all requests can be served at cost 0 if the metric
-has at most k points).
-
-18.9 B is finite in principle.
-
-For an infinite metric, D = M(s, u) is a minimum over FINITELY many
-permutations, and each d(s_i, u_{pi(i)}) is a finite real number by
-the metric axioms. So D is finite, so B = (alpha + 1) D is finite.
-B may be huge, but it is finite.
-
-18.10 What if the metric has no minimum gap?
-
-The "minimum gap delta > 0" is used only inside the fixed-finite-Y
-analysis (Section 7.5) to make level-J cells singletons. In the
-final theorem, Y is replaced by the finite support of the actual
-sequence: only finitely many points ever appear, so delta > 0 always
-holds there. Hence no discreteness assumption is needed at the level
-of a final theorem statement.
-
-------------------------------------------------------------------------
-19. A ONE-PAGE GLOSSARY
-------------------------------------------------------------------------
-
-SYMBOLS (alphabetical):
-
- A, A_t Actual labelled server configuration at time t. The
- context distinguishes ACTUAL A from SIMULATED
- configurations C_t.
-
- A_s A behavioral strategy starting from tuple s.
-
- A_j Alphabet at tree level j. A finite set of labels.
-
- B Additive correction in the main theorem. Depends only
- on (metric, k, starting tuple). Zero when starting
- positions are distinct.
-
- beta_v The rank-function parameter at tree vertex v, in
- [3, 3 + epsilon_*]. Explicit in terms of M_v.
-
- C Generic absolute constant. Also C_0, C_1, C_A, C_P,
- C_T, C_sim, C_final. All fixed numbers.
-
- c_v(t) Integer "park" at tree vertex v at time t: how many
- simulated servers occupy vertex v.
-
- C_loc Local Lipschitz constant of the pilot integrand near
- a concentrated request (Section 12.6).
-
- d(x, y) Distance in the metric.
-
- D_*, D_1 Pilot template "outer radius" constants. Also
- D_H, D_L heavy-template and tier-template outer radii:
- D_1 = 10 D_* = 100 R (heavy template),
- D_L = 100 R = 400 D_H (tier template).
-
- D_T, D_A, Fixed additive constants in the budget inequalities.
- D_P, D_part Each depends on (tree, radii, k), never on the input
- law, on the horizon, or on the number of histories.
-
- diam(Y) Diameter of the (finite) metric.
-
- delta Minimum nonzero distance in the finite metric.
-
- e_x Expected mover distance for request x:
- int d(x, y) dnu(y). Sum over t of E[e_{r_t}] = Q.
-
- ell Little ell: 1 + log(k+1). Order log k.
-
- epsilon_* = 1/100. Upper end of the useful interval for beta.
-
- eta_i = c_t h_i / ell. Tolerance in the alpha feasibility
- constraint.
-
- F_t Filtration at time t. Generated by r_1, ..., r_t and
- any independent partition tape.
-
- F_z^g Pilot integrand:
- (1+g(p)) (1 - sum_s z_s b_s(p))
- + 256 sum_s z_s (1+g(s)) a_s(p).
-
- gamma_H, Inner radii of the heavy template and the tier
- gamma_L template, both < 1/100.
-
- h_i log(M_v / M_i). Size of child i relative to its
- parent. Bounded in [0, C ell].
-
- H Horizon (number of requests). Also "H = 1 + log(1/u)"
- in one dominant-child inequality; context names it.
-
- H_k Set of tiers, {1, 2, 4, ..., 2^b}, of size
- 1 + floor(log_2 log k).
-
- K_h = ceil(e^{C_K h}). Age threshold for tier h. Also
- serves as the density parameter for tier-h radii.
-
- k Number of servers.
-
- L Length of a padded word in episode amplification.
-
- l^beta The rank function: convex, nonincreasing, equal to
- 1 - beta p on [0, p_*], and zero from s_* on.
-
- L_v^beta Rank aggregation sum_a l^beta(p_{va}) at vertex v.
-
- M_v Size aggregation sum_a l^siz(p_{va}). M_v <= m_v.
-
- m_v(t) = E[N_v(t) | F_t]. Posterior expected subtree count.
-
- M(A, C) Minimum matching distance between configurations A
- and C (a bipartite assignment cost).
-
- mu_t Posterior counting measure on Y. Total mass k.
-
- mu^-, mu^+ Filtered and drifted posterior measures just before
- and just after observing the request at time t.
-
- nu Mover's law. nu <= mu^-, nu(Y) = 1.
-
- N_v(t) Random number of hidden servers at leaves below v.
-
- N_rnd = E sum_t sum_{v != root} r_{|v|-1} |Delta n_v|.
- Total integer tree movement after rounding.
-
- OPT, OPT_s Offline optimum from starting tuple s.
-
- p_{va}(t) Pr[N_v(t) < a | F_t]. Nonincreasing in a.
-
- p_v^circ(t) Parked mass q_v - sum_{i child of v} q_i.
-
- P = E sum_t sum_a d_T(xi_{t-1}(X_{t-1}^a), xi_t(X_t^a)).
- Expected comparator movement on the tree.
-
- q_v(t) Fractional tree allocation at vertex v. Root holds k.
-
- Q = E[OPT] on the input law. The budget for all budgets.
-
- r_j = r_0 tau^{-j}, j = 0, ..., J. Scales of the tree.
-
- R Constant in episode amplification:
- floor(k diam(Y) / delta) + 1.
-
- s, s_i Starting tuple and its entries (i = 1, ..., k).
-
- S, D, b, d Core and flex amounts held at tree vertices, plus
- various absolute tolerances.
-
- sigma Request sequence.
-
- tau Large absolute constant. "Separation ratio" of the
- tree. >= 22 in Section 15 (rounding), >= 2 elsewhere.
-
- T_anchor = E sum_{t,j,lambda} r_j b_{t,j,lambda} 1_{E}.
-
- T The fixed prefix tree (Section 10). In Section 15
- the L1 change term sum_i |a_i - b_i| of the rounding
- lemma is ALSO called T; the context disambiguates.
-
- u Either the tuple with distinct entries in transfer
- (Section 16.5), or u = U/A in the near-dominant case
- (Section 11.13).
-
- V = E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|.
- Expected fractional tree movement.
-
- w_i Side tracker coordinates in the near-dominant case.
-
- Z The chosen optimal hidden labelled service.
-
- z A site vector in the pilot potential.
-
- Z_r Feasibility set of the pilot at scale r:
- 0 <= z_s, capacity constraint, separation constraint.
-
-TERMS:
-
- Allocator. The q_v(t) construction of Section 11.
-
- Anchor. The point in Y representing a tree vertex's
- current label. Any member of that label's cell
- is within 20 r_j of the anchor.
-
- Balanced rounding. n_v in {floor(q_v), ceil(q_v)} with
- E[n_v | F_t] = q_v.
-
- Cell. The set of points of Y sharing a given level-j
- label.
-
- Chronological roster. Ordered list of insertion events with
- ages and lifetimes, used to label points of Y.
-
- Dominant child. At a vertex, the unique child holding more than
- 84% of the mass (when such exists).
-
- Drift. Change due to the underlying object moving at
- step t, not merely due to information.
-
- Filtering. Change due to the filtration growing from F_{t-1}
- to F_t (information, not motion).
-
- Heavy ball. A ball at the current level whose inner mass is
- comparable to its outer mass, kept by the map.
-
- HST. Hierarchies of Separated Trees. The prefix tree
- of Section 10, with tau-separated levels.
-
- Lazy simulation. The straight-line car-following lemma of
- Section 8.
-
- Parked mass. q_v - sum_children q_i, at vertex v.
-
- Pilot potential. L_r(mu, g) of Section 12. A compact potential
- that pays for partition edits in one logarithm.
-
- Posterior. Distribution of Z given the observed prefix.
-
- Rank function. The convex l^beta of Section 11.
-
- Side. Any child of a vertex other than its dominant
- child.
-
- Simplex tracker. The alpha update rule of Section 11.11.
-
- Strong laziness. A strategy that does nothing when the request
- is already covered and otherwise moves exactly
- one server.
-
- Tier. A lifetime-based ball structure, indexed by h in
- {1, 2, 4, ...}.
- Witness. A point of Y whose leaf lies below a given tree
- vertex v. Used to define anchors and masses.