← All papers
First page of General Classification for Digital Knowledge: Algorithm, Identifiers and a First Benchmark

General Classification for Digital Knowledge: Algorithm, Identifiers and a First Benchmark

David Awad

cs.DL Oct 14, 2026 · v1
Proves identifier-stability guarantees, class contiguity, exactness of the collapse dynamic program, and the optimal order-preserving tree in Lean 4, with no sorry.
Digital libraries and knowledge graphs need a way to organize very large collections so that related works are close and any work is quick to reach. The classifications libraries inherited for this, such as LCC and DDC, are maintained by editorial staff, are partly closed, and were not built against a stated, measurable objective. We propose the opposite: a general classification that is fitted, under the constraints that make a classification usable on a shelf or in a browse list, to the same quantity that a companion survey and benchmark (Awad, 2026) ranks existing schemes by. The objective is J = D + 0.005 N, where D is the normalized Dasgupta cost of the class tree on a fixed similarity graph (Dasgupta, 2016) and N is an expected navigation cost in bits with a per-level charge. Two constraints are hard: every class is a contiguous run of one fixed shelf order (the optimal-alphabetic-tree constraint of Hu and Tucker, 1971), and new works are filed by splitting leaf classes only, so that every existing class keeps its code, label and parent. On a corpus of 10,000 arXiv papers the fitted prototype has 110 hand-labelled classes and reaches cost 0.1722 in sample (average linkage 0.1518; arXiv's own categories 0.3333; the best existing scheme reached through the same lexical classifier 0.6414, from the survey). Filing 500 library books as new works created 16 classes and changed no existing identifier. Fit, filing and scoring share one embedding: the held-out skill of 0.922 falls to 0.896 when the same fit is scored on the graphs of the two other models, and on books the average falls from 0.806 to 0.731. The scheme has also seen only arXiv, and labels for inserted classes are weak. We state those limits plainly, release the scheme as CC0 open data, and ask whether a learned, open, order-preserving classification can become a general one.

Library classifications such as LCC and DDC are editorially maintained and partly closed. They were not built to optimize any stated, measurable objective. Digital libraries need an open classification that keeps related works close, makes works quick to reach, and keeps identifiers stable as new works are added.

The classification is fitted to the objective J = D + 0.005 N. D is the normalized Dasgupta cost on a similarity graph and N is the expected navigation cost in bits. Two hard constraints apply: every class is a contiguous run of a fixed shelf order (the Hu-Tucker alphabetic-tree constraint), and new works are filed only by splitting leaf classes. The identifier-stability guarantees, class contiguity, collapse-DP exactness and the optimal order-preserving tree are proved in Lean 4, with no sorry and no extra axioms.

On 10,000 arXiv papers, the 110-class prototype reaches cost 0.1722, against 0.3333 for arXiv's own categories and 0.6414 for the best existing scheme. Filing 500 books created 16 classes and changed no existing identifier. Scores drop when the fit is evaluated on graphs built from other embedding models.

SchemeCost
Fitted prototype0.1722
Average linkage0.1518
arXiv categories0.3333
Best existing scheme (via lexical classifier)0.6414
In-sample objective cost on 10,000 arXiv papers