Package jline.lib.rmf

Class CacheRMF

  • All Implemented Interfaces:
    
public class CacheRMF

    Multi-list cache with RANDOM(m) replacement as a Density-Dependent Population Process (DDPP).

    Models a cache with h lists of capacities m = [m_1, ..., m_h] and n items with popularity distribution p = [p_1, ..., p_n]. The state space tracks in which list each item resides (or if it is outside the cache).

    State vector layout: x[i + k * n] = density of item i in list k where k=0 means "outside cache", k=1..h are the cache lists

    Reference: N. Gast, "Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate", Proc. ACM Meas. Anal. Comput. Syst., 2017.

    • Constructor Detail

      • CacheRMF

        CacheRMF(Array<double> p, Array<int> m)
        Constructs a CacheRMF model.
        Parameters:
        p - Item request probabilities (popularity distribution), normalized.
        m - Capacity of each cache list.

    • Method Detail

      • index

         int index(int i, int k)

        Map (item i, list k) to flat state index.

        Parameters:
        i - Item index (0-based).
        k - List index (0 = outside cache, 1..h = cache lists).
        Returns:

        Flat index into state vector.

      • hitRate

         double hitRate(Array<double> x, int listNumber)

        Compute hit rate contribution from a specific list.

        Parameters:
        x - State vector of dimension modelDimension.
        listNumber - List index (0 = outside cache, 1..h = cache lists).
        Returns:

        Sum of p[i] * x[index(i, listNumber)] over all items i.

      • drift

         Array<double> drift(Array<double> x)

        Compute the mean field drift F(x).

        The drift for RANDOM(m) replacement is: dx[i,k]/dt = -p_i * x[i,k] + hitRate[k] * x[i,k+1] / m[k] dx[i,k+1]/dt = p_i * x[i,k] - hitRate[k] * x[i,k+1] / m[k]

        Parameters:
        x - State vector of dimension modelDimension.
        Returns:

        Drift vector dx/dt of same dimension.

      • jacobian

         Array<Array<double>> jacobian(Array<double> x)

        Compute Jacobian dF/dx at state x.

        Parameters:
        x - State vector of dimension modelDimension.
        Returns:

        Jacobian matrix of shape (modelDimension, modelDimension).

      • hessian

         Array<Array<Array<double>>> hessian(Array<double> x)

        Compute Hessian d^2F/dx^2.

        The Hessian is constant (drift is quadratic in x), so the x argument is unused but kept for interface consistency.

        Parameters:
        x - State vector (unused - Hessian is constant for this model).
        Returns:

        Hessian tensor of shape (modelDimension, modelDimension, modelDimension).

      • noiseMatrix

         Array<Array<double>> noiseMatrix(Array<double> x)

        Compute noise intensity matrix Q(x) for the DDPP.

        Q[a,b] = sum_ell ell[a] * ell[b] * beta_ell(x) where each transition ell is a swap between items i and j across lists k and k+1.

        Parameters:
        x - State vector of dimension modelDimension.
        Returns:

        Noise matrix of shape (modelDimension, modelDimension).

      • fixedPoint

         Array<double> fixedPoint(double tmax)

        Compute mean field fixed point by ODE integration.

        Integrates dx/dt = F(x) until steady state using LSODA.

        Parameters:
        tmax - Maximum integration time (should be large enough for convergence).
        Returns:

        Fixed point state vector of dimension modelDimension.

      • fixedPoint

         Array<double> fixedPoint()

        Compute mean field fixed point with default tmax=10000.

        Returns:

        Fixed point state vector.

      • dimensionReduction

         CacheRMF.DimensionReduction dimensionReduction(Array<Array<double>> Fp)

        Compute dimension reduction matrices for the singular Jacobian.

        The Jacobian is singular because item populations are conserved (sum over lists for each item = 1). This method finds a change of basis that separates the rank-deficient directions.

        Parameters:
        Fp - Jacobian matrix at fixed point.
        Returns:

        DimensionReduction containing P, Pinv, rank.

      • reduceFpFppQ

         CacheRMF.ReducedSystem reduceFpFppQ(Array<Array<double>> Fp, Array<Array<Array<double>>> Fpp, Array<Array<double>> Q)

        Apply dimension reduction to Fp, Fpp, Q.

        Projects the Jacobian, Hessian, and noise matrix onto the non-singular subspace identified by dimension reduction.

        Parameters:
        Fp - Jacobian matrix.
        Fpp - Hessian tensor.
        Q - Noise matrix.
        Returns:

        ReducedSystem with reduced Fp, Fpp, Q, and basis matrices.

      • expandV

         Array<double> expandV(Array<double> V_r, Array<Array<double>> Pinv, int rank)

        Expand reduced V back to full dimension.

        Parameters:
        V_r - Reduced correction vector (rank).
        Pinv - Inverse basis matrix (dim x dim).
        rank - Rank of the non-singular subspace.
        Returns:

        Full-dimension correction vector (modelDimension).

      • expandW

         Array<Array<double>> expandW(Array<Array<double>> W_r, Array<Array<double>> Pinv, int rank)

        Expand reduced W back to full dimension.

        Parameters:
        W_r - Reduced covariance matrix (rank x rank).
        Pinv - Inverse basis matrix (dim x dim).
        rank - Rank of the non-singular subspace.
        Returns:

        Full-dimension covariance matrix (modelDimension x modelDimension).

      • meanFieldExpansionSteadyState

         Array<Object> meanFieldExpansionSteadyState(int order)

        Compute refined mean field steady-state expansion.

        Computes the mean field fixed point pi and the 1/N correction V using the Lyapunov equation approach with dimension reduction to handle the singular Jacobian (due to per-item conservation constraints).

        The refined approximation for a system of N items is: E[X] ~ pi + V/N + O(1/N^2)

        Parameters:
        order - Expansion order (0 = plain mean field, 1 = with 1/N correction).
        Returns:

        Object array {pi (double[]), V (double[]), W (double[][])}.

      • meanFieldExpansionSteadyState

         Array<Object> meanFieldExpansionSteadyState()

        Compute refined mean field steady-state expansion with default order=1.

        Returns:

        Object array {pi (double[]), V (double[]), W (double[][])}.

      • meanFieldExpansionTransient

         Array<Object> meanFieldExpansionTransient(double time, int nPoints, int order)

        Compute refined mean field transient expansion.

        Integrates the coupled ODE system for (X, V, W) where:

        • X(t): mean field trajectory
        • V(t): 1/N correction trajectory
        • W(t): covariance trajectory
        Parameters:
        time - Maximum integration time.
        nPoints - Number of output time points.
        order - Expansion order (0 or 1).
        Returns:

        Object array {T (double[]), X (double[][]), V (double[][]), W (double[][][])}.

      • hitRatesAll

         Array<double> hitRatesAll(Array<double> x)

        Compute hit rates for all lists.

        Parameters:
        x - State vector of dimension modelDimension.
        Returns:

        Array of shape (numberOfLists + 1) with hit rate per list.