A Novel Framework for Self-Organizing Lists in Environments with Locality of Reference: Lists-on-Lists
Bibliographic record
Abstract
We examine the problem of self-organizing linear search lists, which are lists that react to queries received from an environment by running a heuristic to reorganize the records in order to minimize the search cost. In particular, we are concerned with environments with the locality of reference phenomenon, when the queries exhibit a probabilistic dependence between themselves. We introduce a novel list organization framework that we call Lists-on-Lists (LOL), which regards the list as a set of sublists that are manageable in the same way that individual records are. An LOL organization involves a reorganization operation on the accessed record level, as well as another on the sublist which it belongs to (the record's context). We show that it is beneficial to consider the reorganization of the context together with the accessed record, since other records within the context are likely to be accessed in the near future. With the aid of a learning automaton-based partitioning algorithm, we demonstrate that we can accurately classify the different contexts of the sublist. To the best of our knowledge, both the concept of reorganizing the list ‘hierarchically’ using such a two-step LOL process, and the application of stochastic learning to this problem are new to the field. Indeed, while the costs involved to achieve these enhancements are almost of the same order as that which achieves basic list-organizing, using this framework, we were able to empirically achieve asymptotic search costs that are significantly superior to (sometimes even an order of magnitude better than) the Move-To-Front heuristic, widely acknowledged as the best algorithm for such environments.
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.002 | 0.007 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.002 | 0.002 |
| Scholarly communication | 0.003 | 0.006 |
| Open science | 0.004 | 0.003 |
| Research integrity | 0.003 | 0.002 |
| Insufficient payload (model declined to judge) | 0.004 | 0.001 |
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".