On Developing New Models, with Paging as a Case Study
Bibliographic record
Abstract
As computer science has progressed, numerous models and measures have been developed over the years. Among the most commonly used in theoretical computer science are the RAM model, the I/O model, worst case analysis, space (memory) usage, average case analysis, amortized analysis, adaptive analysis and the competitive ratio. New models are added to this list every few years to re ect varying constraints imposed by novel application or advances in computer architectures. Examples of alternative models are the transdichotomous RAM or word-RAM, the data stream model, the MapReduce model, the cache oblivious model and the smoothed analysis model. New models and measures, when successful expand our understanding of computation and open new avenues of inquiry. As it is to be expected relatively few models and paradigms are introduced every year, and even less are eventually proven successful. In this paper we discuss rst certain shortcomings of the online competitive analysis model particularly as it concerns paging, discuss existing solutions in the literature as well as present recent progress in developing models and measures that better re ect actual practice for the case of paging. From there we proceed to a more general discussion on how to measure and evaluate new models within theoretical computer science and how to contrast them, when appropriate, to existing models. Lastly, we highlight certain \natural" choices and assumptions of the standard worst-case model which are often unstated and rarely explicitly justied. We contrast these choices to those made in the formalization of probability theory.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.013 | 0.042 |
| Meta-epidemiology (narrow) | 0.003 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.003 |
| Bibliometrics | 0.005 | 0.006 |
| Science and technology studies | 0.002 | 0.011 |
| Scholarly communication | 0.011 | 0.027 |
| Open science | 0.008 | 0.006 |
| Research integrity | 0.007 | 0.012 |
| Insufficient payload (model declined to judge) | 0.015 | 0.004 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".