geom_seq_nth_root_algo

Maintain constant size complexity with recency-proportional strata spacing.

The approximate space-filling MRCA-recency-proportional resolution policy imposes an O(1) limit on the number of retained strata and guarantees that retained strata will be exponentially distributed with respect to ranks elapsed since their deposit. MRCA rank estimate uncertainty scales in the worst case scales as O(n) with respect to the greater number of strata deposited on either column. However, with respect to estimating the rank of the MRCA when lineages diverged any fixed number of generations ago, uncertainty scales as O(n^{1/k}).

Under the MRCA-recency-proportional resolution policy, the number of strata retained (i.e., space complexity) scales as O(1) with respect to the number of strata deposited.

Suppose k is specified as the policy’s target precision k. Then, the first k strata deposited will be retained. Subsequently, strata are retained so that MRCA rank estimate uncertainty is less than or equal to s * (1 - n^(-1/k)) is the number of strata deposited and s is the true number of ranks deposited since the MRCA. As n goes to infinity, the number of strata retained fluctuates below a hard upper limit of 4k + 2 (inclusive) strata. For larger target space utilizations, number of strata retained appears generally less than twice the target space utilization.

See Also

geom_seq_nth_root_tapered_algo:

For a predicate retention policy that achieves the same guarantees for resolution but retains a constant column size exactly equal to the hard upper limit on number of strata retained.

Classes

CalcMrcaUncertaintyAbsExact	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyAbsUpperBound	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyAbsUpperBoundAtPessimalRank
CalcMrcaUncertaintyAbsUpperBoundPessimalRank	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyRelExact
CalcMrcaUncertaintyRelUpperBound	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyRelUpperBoundAtPessimalRank
CalcMrcaUncertaintyRelUpperBoundPessimalRank	Functor to provide member function implementation in Policy class.
CalcNumStrataRetainedExact	Functor to provide member function implementation in Policy class.
CalcNumStrataRetainedUpperBound	Functor to provide member function implementation in Policy class.
CalcRankAtColumnIndex	Functor to provide member function implementation in Policy class.
GenDropRanks	Functor to implement the approximate space-filling MRCA-recency- proportional resolution stratum retention policy, for use with HereditaryStratigraphicColumn.
IterRetainedRanks	Functor to provide member function implementation in Policy class.
Policy	Instantiate policy implementation for particular policy specification parameters.
PolicySpec	Contains all policy parameters, if any.

class CalcMrcaUncertaintyAbsExact

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → int

Exactly how much uncertainty to estimate rank of MRCA?

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyAbsUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → int

At most, how much relative uncertainty to estimate rank of MRCA? Inclusive.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyAbsUpperBoundAtPessimalRank

class CalcMrcaUncertaintyAbsUpperBoundPessimalRank

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int | None, second_num_strata_deposited: int | None) → int

Calculate rank for which upper bound on absolute MRCA uncertainty is pessimized.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyRelExact

class CalcMrcaUncertaintyRelUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → float

At most, how much relative uncertainty to estimate rank of MRCA? Inclusive.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyRelUpperBoundAtPessimalRank

class CalcMrcaUncertaintyRelUpperBoundPessimalRank

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase | None, first_num_strata_deposited: int, second_num_strata_deposited: int) → int

Calculate rank for which upper bound on relative MRCA uncertainty is pessimized.

__init__(policy_spec: PolicySpec | None) → None

class CalcNumStrataRetainedExact

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, num_strata_deposited: int) → int

Exactly how many strata are retained after n deposited?

__init__(policy_spec: PolicySpec | None) → None

class CalcNumStrataRetainedUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, num_strata_deposited: int) → int

At most, how many strata are retained after n deposited? Inclusive.

__init__(policy_spec: PolicySpec | None = None) → None

class CalcRankAtColumnIndex

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, index: int, num_strata_deposited: int | None) → int

After n strata have been deposited, what will the rank of the stratum at column index k be?

Enables a HereditaryStratigraphicColumn using this predicate to optimize away storage of rank annotations on strata. Takes into the account the possibility for in-progress stratum depositions that haven’t been reflected in num_strata_deposited.

__init__(policy_spec: PolicySpec | None) → None

class GenDropRanks

Functor to implement the approximate space-filling MRCA-recency- proportional resolution stratum retention policy, for use with HereditaryStratigraphicColumn.

This functor enacts the approximate space-filling MRCA-recency- proportional resolution stratum retention policy by specifying the set of strata ranks that should be purged from a hereditary stratigraphic column when the nth stratum is deposited.

__call__(policy: PolicyCouplerBase, num_stratum_depositions_completed: int, retained_ranks: Iterable[int] | None) → Iterator[int]

Decide which strata within the stratagraphic column should be purged.

Every time a new stratum is deposited, this method is called to determine which strata should be purged. All strata at ranks yielded from this functor are immediately purged from the column, meaning that for a stratum to persist it must not be yielded by this functor each and every time a new stratum is deposited.

Parameters

policy: Policy

Policy this functor enacts.

num_stratum_depositions_completedint

The number of strata that have already been deposited, not including the latest stratum being deposited which prompted the current purge operation.

retained_ranksiterator over int

An iterator over ranks of strata currently retained within the hereditary stratigraphic column. Not used in this functor.

Returns

iterator over int

The ranks of strata that should be purged from the hereditary

stratigraphic column at this deposition step.

See Also

depth_proportional_resolution_tapered_algo:

For details on the rationale, implementation, and guarantees of the tapered depth-proportional resolution stratum retention policy.

__init__(policy_spec: PolicySpec | None) → None

class IterRetainedRanks

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, num_strata_deposited: int) → Iterator[int]

Iterate over retained strata ranks at num_strata_deposited in ascending order.

__init__(policy_spec: PolicySpec | None) → None

class Policy

Instantiate policy implementation for particular policy specification parameters.

GetEvalCtor() → str

GetSpec() → PolicySpec

Get policy’s parameter specification.

WithoutCalcRankAtColumnIndex() → PolicyCoupler

Make a copy of this policy instance with CalcRankAtColumnIndex disabled.

Useful to prevent optimization-out of strata rank number storage in a stratum ordered store backing a hereditary stratigraphic column.

__init__(*args, parameterizer: Callable[[Type], PolicySpecBase | None] | None = None, policy_spec: PolicySpecBase | None = None, **kwargs)

Construct a PolicyCoupler instance.

If policy_spec is not provided, all arguments are forwarded to policy spec initializer.

__repr__() → str

Return repr(self).

__str__() → str

Return str(self).

policy_spec_t

alias of PolicySpec

CalcMrcaUncertaintyAbsUpperBound: Callable

CalcMrcaUncertaintyAbsUpperBoundPessimalRank: Callable

CalcMrcaUncertaintyAbsUpperBoundAtPessimalRank: Callable

CalcMrcaUncertaintyRelUpperBound: Callable

CalcMrcaUncertaintyRelUpperBoundAtPessimalRank: Callable

CalcMrcaUncertaintyRelUpperBoundPessimalRank: Callable

CalcNumStrataRetainedUpperBound: Callable

CalcMrcaUncertaintyAbsExact: Callable | None

CalcMrcaUncertaintyRelExact: Callable | None

CalcNumStrataRetainedExact: Callable | None

CalcRankAtColumnIndex: Callable | None

IterRetainedRanks: Callable | None

GenDropRanks: Callable

class PolicySpec

Contains all policy parameters, if any.

static GetAlgoIdentifier() → str

Get programatic name for underlying retention algorithm.

static GetAlgoTitle() → str

Get human-readable name for underlying retention algorithm.

GetDegree() → int

GetEvalCtor() → str

GetInterspersal() → int

__init__(degree: int, interspersal: int = 2) → None

Construct the policy spec.

Parameters

degreeint

How many should target recencies for uncertainty-capped coverage should be spaced exponentially from zero recency to maximum recency (i.e., number strata deposited)? Adjust this parameter to set upper bound on space complexity (i.e., to ensure available space is not exceeded).

interspersalint

At least how many retained ranks should be spaced between zero recency and each target recency? Must be greater than 0. No bound on MRCA rank estimate uncertainty provided if set to 1. For most use cases, leave this set to 2.

__repr__() → str

Return repr(self).

__str__() → str

Return str(self).