Package jline.lib.rmf

Class CacheRMF

java.lang.Object
jline.lib.rmf.CacheRMF
public class CacheRMF extends Object
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 Details

    • CacheRMF

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

  • Method Details

    • index

      public 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

      public double hitRate(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

      public double[] drift(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

      public double[][] jacobian(double[] x)
      Compute Jacobian dF/dx at state x.
      Parameters:
      x - State vector of dimension modelDimension.
      Returns:
      Jacobian matrix of shape (modelDimension, modelDimension).

    • hessian

      public double[][][] hessian(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

      public double[][] noiseMatrix(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

      public 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

      public double[] fixedPoint()
      Compute mean field fixed point with default tmax=10000.
      Returns:
      Fixed point state vector.

    • dimensionReduction

      public CacheRMF.DimensionReduction dimensionReduction(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

      public CacheRMF.ReducedSystem reduceFpFppQ(double[][] Fp, double[][][] Fpp, 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

      public double[] expandV(double[] V_r, 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

      public double[][] expandW(double[][] W_r, 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

      public 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

      public Object[] meanFieldExpansionSteadyState()
      Compute refined mean field steady-state expansion with default order=1.
      Returns:
      Object array {pi (double[]), V (double[]), W (double[][])}.

    • meanFieldExpansionTransient

      public 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[][][])}.

    • meanFieldExpansionTransient

      public Object[] meanFieldExpansionTransient()
      Compute refined mean field transient expansion with default parameters.
      Returns:
      Object array {T, X, V, W}.

    • hitRatesAll

      public double[] hitRatesAll(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.

    • getNumberOfItems

      public int getNumberOfItems()

    • getNumberOfLists

      public int getNumberOfLists()

    • getModelDimension

      public int getModelDimension()

    • getP

      public double[] getP()

    • getM

      public int[] getM()

    • getX0

      public double[] getX0()