Exact normalizing constant E(v,m) of a delayed-hit (list-based) cache. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for retrieval_nc.h:

Namespaces
namespace	line
namespace	line::retrieval

Functions
template<class T>
T	line::retrieval::retrieval_nc (const std::vector< int > &v, const std::vector< int > &m, const std::vector< T > &lambda, const Matrix< T > &eta, const Matrix< T > &gamma)
	Exact normalizing constant E(v,m) of a delayed-hit (list-based) cache.

Detailed Description

Exact normalizing constant E(v,m) of a delayed-hit (list-based) cache.

Templated port of matlab/src/api/retrieval/retrieval_nc.m, cross-checked against jar/src/main/java/jline/api/retrieval/Retrieval_nc.java.

The cache holds h lists of capacities m(1..h) filled from n items, and a missed item is fetched by a retrieval system with one infinite-server station (index s=0) and r processor-sharing stations (s=1..r). The exact recurrence peels off item k:

E(v,m) = (1 + lambda_k eta_{0,k}) E_k(v,m)

sum_{s=1}^r lambda_k eta_{s,k} (v_s+1) E_k(v+1_s, m)
sum_{j=1}^h m_j gamma_{k,j} E_k(v, m-1_j)

with E_k the constant of the system without item k, E = 1 once no item is left, and E = 0 as soon as sum_j m_j exceeds the number of remaining items or some m_j is negative. The plain constant is E(m) = E(0,m); the vector v carries the moment order at each PS station, so E(1_s,m) is what the delayed-hit probability at station s needs.

ARITHMETIC: every step is a multiplication and an addition of the inputs, so this is a finite field computation and the exact instantiation returns the true constant with no rounding at all. That is what makes it the oracle for retrieval_fpi, which only approximates the same quantities.

Definition in file retrieval_nc.h.

Namespaces

Functions

Detailed Description