Consider two (or more) users who request records in adatabase independently and with different frequencies. On arequest, the user's probability of calling a certain record iseither constant or changes deterministically in time. One userhas priority over the other(s) and rearranges the recordsaccording to seff-organizing rules.
Extending the model to include not just constant but alsotime-dependent request probabilities allows us to treat a widerclass of situations naturally arising in applications. Theintroduction of several users provides means to model morecomplex systems such as e.g. cach-hierarchies.
Assuming a finite number of records, the low-priority user'stransient and stationary/long-term search cost distribution(including mean, variance and generating function) is derivedwhen the self-organizing rule ismove-to-frontresp.move-to-root.
For move-to-front with constant request probabilities, ratesof convergence to stationarity are considered and some examplesfor standard distributions are given.
As the number of records tends to infinity, the transientresp. long-term search cost as a fraction of the total numberof records (under some regularity assumptions) converges indistribution. The asymptotic distribution function is derivedfor move-to-front assuming deterministically time-dependentrequest probabilities. Also, some stochastic ordering resultsallowing us to decide which low-priority user requestprobability distribution yields the better asymptotic searchcost fraction are given. Taking the request probabilitydistributions to be constant in time, the results stillapply.
All results for the low-priority user reduce to analogousones for the high-priority one when all users are taken to beidentical. In particular, we recapture the probability functionfor move-to-root with uniform request probabilities.Numerically, we find that the 'worst' set of requestprobabilities, maximizing the expected search cost, closelyresembles the uniform which justifies the interest in thisspecial case.
Keywords and phrases:Poisson embedding, self-organizingsearch, move-to-front, move-to-root, coupling, search cost,caching.
Stockholm: Matematik , 1997. , 208 p.