One Index for Subsumption and Roll-up across Time, Geography, and Ontology
Madhulatha Mandarapu, Sandeep Kunkunuru · 2026
Read One Index for Subsumption and Roll-up across Time, Geography, and Ontology by Madhulatha Mandarapu, Sandeep Kunkunuru (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24677.txt.
Introduction
Madhulatha Mandarapu and Sandeep Kunkunuru argue that three fields maintain the same structure in separate silos. Time systems nest days inside months and years. Geography systems nest postcodes inside cities. Ontology systems arrange concepts in is a and part of hierarchies. Each field keeps its own index for its hierarchy. Yet all are subsumption posets with two recurring queries. One asks whether an item sits under another. The other rolls up a measure over all below it.
Their index, OEH, first probes the shape of a hierarchy. Trees get a nested set embedding, and low width directed graphs get a chain decomposition. Tested on five real hierarchies, OEH matches a two hop index on tree query speed. It uses half the space and builds six to seven times faster. Tests include a taxonomy with 1.3 million nodes. On high width graphs, though, two hop indexing wins.
Catalog record
| CREATOR | Madhulatha Mandarapu, Sandeep Kunkunuru |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24677
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
One Index for Subsumption and Roll-up across Time, Geography, and Ontology Madhulatha Mandarapu, Sandeep Kunkunuru Abstract Time-series, geospatial, and ontology systems each maintain a hierarchy — day ⊑ \sqsubseteq month ⊑ \sqsubseteq year , zip ⊑ \sqsubseteq city , is-a / part-of — and each indexes it in a separate silo. We observe these are all subsumption posets , with one recurring workload: order testing (is x x under y y ?) and hierarchical roll-up (aggregate a measure over everything under y y ). We present OEH , a single declarable index that, by a cheap structural probe, encodes a hierarchy as a nested-set order-embedding (trees) or a chain decomposition (low-width DAGs), and answers both subsumption and index-resident monoid roll-up from one structure. On five real hierarchies — Gene Ontology, NCBI Taxonomy (1.3M), GeoNames (330k), a 2.6M-node calendar, and git commit DAGs — OEH on trees matches a 2-hop index on query latency using ∼ \sim half the space and building 6–7 × \times faster, and adds roll-up that 2-hop cannot. Its roll-up matches TimescaleDB’s continuous aggregates exactly and in the same latency regime, while also answering subsumption. On high-width DAGs the chain index is declined and 2-hop dominates. Order-embedding is classical; our contribution is the unification and the structure-selected index over subsumption and index-resident roll-up. 1 Introduction Three of the most active corners of data management each revolve around a hierarchy , yet each indexes it in isolation. Time-series engines roll up minute \to hour \to day \to month with continuous aggregates; spatial systems nest cell \to region \to country with grids and space-filling curves (S2, geohash); knowledge graphs and reasoners walk is-a / part-of taxonomies. The structures and the queries are, underneath, the same: a partial order given by a subsumption (parent) relation, over which we ask (i) order tests — is x subsumed in y ? — and (ii) roll-up — aggregate a measure over everything subsumed by y . We call such a structure a relationship hierarchy and ask whether one index can serve all three domains. The answer is a qualified yes. We present OEH (Order-Embedded Hierarchy), a single index that chooses its encoding from the data’s shape and answers subsumption and roll-up from one structure. Contributions. C1 The relationship-hierarchy abstraction and its query algebra (§ 2 ). C2 OEH : one declarable, structure-selected index answering subsumption and index-resident monoid roll-up — the aggregate is answered from the structure (a Fenwick range-sum over a nested-set, or a per-chain suffix-sum), not delegated to an engine join-group-aggregate. This is the precise distinction from the index- assisted hierarchy line of SAP HANA (§ 5 ). C3 An empirical study on five real hierarchies, including an exact cross-validation of roll-up against TimescaleDB and of subsumption against git merge-base (§ 4 ). C4 A regime map — when nested-set, chain, or 2-hop each win — with a principled \sim\!8\sqrt{n} width cap. We are deliberately scoped: OEH is a static index (dynamic maintenance is future work), and order-embedding/dominance as a subsumption primitive is classical prior art that we build on, not claim. 2 Problem and model A relationship hierarchy is a labeled partial order (V,\sqsubseteq,\lambda) generated by a covering (“parent”) relation; x\sqsubseteq y reads “ x is subsumed in y ”. The query algebra has two halves. Order: subsumes (x,y) , ancestors / descendants (x) , lca . Aggregation: rollup (\textit{measure},\ell) folds a monoid measure over \{y\}\cup\textsf{descendants}(y) at a target level \ell , with set semantics on DAGs (each descendant counted once). Time, geo, taxonomy, and genealogy are instances; the same two halves recur. 3 The OEH index A cheap structural probe (the “knob”) picks the encoding. Trees \to nested-set. A DFS assigns each node an interval [\textsf{in},\textsf{out}] ; x\sqsubseteq y\iff\textsf{in}(y)\leq\textsf{in}(x)\wedge\textsf{out}(x)\leq\textsf{out}(y) (2-D containment). The subtree of y is the contiguous in -order range [\textsf{in}(y),\textsf{out}(y)] , so roll-up is a Fenwick range-sum in O(\log n) ; two integers per node. Low-width DAGs \to chain decomposition. A path partition gives each node a (\textit{chain},\textit{pos}) ; for each node v and chain c we store \textsf{reach}[v][c] , the minimum reachable position on c (Jagadish’s chain index [ 15 ] ); the chain count relates to the poset width [ 8 ] . Subsumption is O(\textit{width}) . Crucially, the descendants of v on chain c are the contiguous suffix from \textsf{reach}[v][c] , so set-semantics roll-up is \sum_{c}\textsf{suffix-sum}_{c} — exact and double-count-free. Width cap. Chain space is O(n\cdot\textit{width}) ; it only beats a 2-hop index while width is small. OEH declines chain mode above \sim\!8\sqrt{n} (so chain space stays \sim\!O(n^{1.5}) ) and defers to 2-hop, which is the right substrate for high-width DAGs (§ 4 ). Index-resident roll-up. In both encodings the partial aggregate is answered from the index in O(\log n) (trees) or O(\textit{width}) (DAGs), not by an engine aggregation over the group. This is the capability that distinguishes OEH from prior hierarchy indexes (§ 5 ). 4 Evaluation Setup. Five real hierarchies: Gene Ontology [ 20 ] ( go-basic , 38,263 nodes / DAG, 51% multi-parent); NCBI Taxonomy [ 18 ] Metazoa subtree (1,323,391 / tree); GeoNames [ 12 ] administrative hierarchy (329,993 / tree); a 5-year per-minute calendar (2,675,155 / tree); and git commit DAGs ( postgres , 102,560 / tree, width 38; git/git , 84,891 / DAG, width 14%). Baselines: a brute-force oracle; exact transitive closure; GRAIL [ 23 ] ; PLL [ 3 ] ; TimescaleDB hierarchical continuous aggregates [ 21 ] ; git merge-base as a subsumption ground truth. Correctness is exact; timings are pure-Python and machine-specific, used for apples-to-apples comparison. H1: subsumption parity across three domains (Fig. 1 , Table 1 ). One nested-set index serves ontology, geo, and time trees. Against PLL it uses \sim half the space and builds 6–7 \times faster at query parity, and additionally answers roll-up PLL cannot. Table 1: H1: OEH (nested-set) vs. PLL on real trees. n space (M entries) query ( \mu s) domain (dataset) OEH PLL OEH PLL ontology (NCBI Tax) 1,323,391 2.65 4.87 1.17 1.10 geo (GeoNames) 329,993 0.66 1.39 0.87 1.09 time (calendar) 2,675,155 5.35 — 0.42 — Figure 1: H1: OEH nested-set vs. 2-hop (PLL) on real trees — half the space, query parity. H2: index-resident roll-up (Fig. 2 , Table 2 ). Roll-up is exact and size-dependent : OEH is \sim constant ( 3 – 4\,\mu s, O(\log n) ) regardless of subtree size, whereas an engine-style aggregation is O(\textit{subtree}) . On large subtrees (avg 28,851 descendants) OEH is 3{,}488\times faster; it loses only on trivially small subtrees. The brute-force baseline is precisely the index- assisted join-group-aggregate of the HANA line (§ 5 ); OEH beating it by orders of magnitude is the direct case for index-residence. Against TimescaleDB on the same calendar, OEH’s roll-up matches exactly (day 704{,}800 , month 21{,}168{,}000 ) and in the same single-digit- \mu s regime as a materialized continuous aggregate, while also answering subsumption, which a continuous aggregate cannot. Table 2: Time-axis roll-up: OEH vs. TimescaleDB ( \mu s). Sums match exactly. level OEH (index-resident) TS cagg (materialized) TS raw day 2.63 5.09 92.17 month 3.13 6.04 1516.58 Figure 2: Index-resident (OEH) vs. index-assisted (engine join-group-aggregate) roll-up. H3: regime map (Fig. 3 ). The knob picks nested-set for trees, chain