Change search
ReferencesLink to record
Permanent link

Direct link
Cost of searching: probabilistic analysis of the self-organizing move-to-front and move -to-root sorting rules
KTH, Superseded Departments, Mathematics.
1997 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

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.

Place, publisher, year, edition, pages
Stockholm: Matematik , 1997. , 208 p.
URN: urn:nbn:se:kth:diva-2505ISBN: 91-7170-153-2OAI: diva2:8106
Public defence
NR 20140805Available from: 2000-01-01 Created: 2000-01-01Bibliographically approved

Open Access in DiVA

No full text

By organisation

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 60 hits
ReferencesLink to record
Permanent link

Direct link