One Index for Subsumption and Roll-up across Time, Geography, and Ontology Madhulatha Mandarapu∗
Sandeep Kunkunuru†
arXiv:2606.24677v1 [cs.DB] 23 Jun 2026
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
Abstract Time-series, geospatial, and ontology systems each maintain a hierarchy — day ⊑ month ⊑ year, zip ⊑ 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 under y?) and hierarchical roll-up (aggregate a measure over everything under 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 ∼half the space and building 6–7× 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→hour→day→month with continuous aggregates; spatial systems nest cell→region→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. ∗ †
[email protected] [email protected]
1
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 ∼ 8 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, ⊑, λ) generated by a covering (“parent”) relation; x ⊑ y reads “x is subsumed in y”. The query algebra has two halves. Order: subsumes(x, y), ancestors/descendants(x), lca. Aggregation: rollup(measure, ℓ) folds a monoid measure over {y} ∪ descendants(y) at a target level ℓ, 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 → nested-set. A DFS assigns each node an interval [in, out]; x ⊑ y ⇐⇒ in(y) ≤ in(x) ∧ out(x) ≤ out(y) (2-D containment). The subtree of y is the contiguous in-order range [in(y), out(y)], so roll-up is a Fenwick range-sum in O(log n); two integers per node. Low-width DAGs → chain decomposition. A path partition gives each node a (chain, pos); for each node v and chain c we store reach[v][c], the minimum reachable position on c (Jagadish’s chain index [18]); the chain count relates to the poset width [12]. Subsumption is O(width). Crucially, the descendants of v on chain c are the contiguous suffix from reach[v][c], so set-semantics roll-up is P c suffix-sumc — exact and double-count-free. Width cap. Chain space is O(n · width); it only beats a 2-hop index while width is small. OEH √ declines chain mode above ∼ 8 n (so chain space stays ∼ O(n1.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(width) (DAGs), not by an engine aggregation over the group. This is the capability that distinguishes OEH from prior hierarchy indexes (§5). 2
Table 1: H1: OEH (nested-set) vs. PLL on real trees. n domain (dataset) ontology (NCBI Tax) geo (GeoNames) time (calendar)
1,323,391 329,993 2,675,155
space (M entries)
query (µs)
OEH
PLL
OEH
PLL
2.65 0.66 5.35
4.87 1.39 —
1.17 0.87 0.42
1.10 1.09 —
Figure 1: H1: OEH nested-set vs. 2-hop (PLL) on real trees — half the space, query parity.
4
Evaluation
Setup. Five real hierarchies: Gene Ontology [1] (go-basic, 38,263 nodes / DAG, 51% multi-parent); NCBI Taxonomy [3] Metazoa subtree (1,323,391 / tree); GeoNames [2] 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 [7]; TimescaleDB hierarchical continuous aggregates [4]; 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 ∼half the space and builds 6–7× faster at query parity, and additionally answers roll-up PLL cannot. H2: index-resident roll-up (Fig. 2, Table 2). Roll-up is exact and size-dependent: OEH is ∼constant (3–4 µs, O(log n)) regardless of subtree size, whereas an engine-style aggregation is O(subtree). On large subtrees (avg 28,851 descendants) OEH is 3,488× 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-µs regime as a materialized continuous aggregate, while also answering subsumption, which a continuous aggregate cannot.
3
Table 2: Time-axis roll-up: OEH vs. TimescaleDB (µs). Sums match exactly. level day month
OEH (index-resident)
TS cagg (materialized)
TS raw
2.63 3.13
5.09 6.04
92.17 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 for low-width DAGs, and defers to 2-hop otherwise. On Gene Ontology (width ≈ its 22,807 leaves) and on git/git (width 14% of n) chain mode auto-declines and PLL owns the regime. On postgres (a rebase history, width 38) forced chain is compact and correct; on git/git forced chain is validated correct against git merge-base itself but not space-efficient. A finding worth stating: genuinely low-width multi-parent DAGs are rare — real merge histories are high-width, real low-width histories are trees.
4
Figure 3: Regime map: structure and width determine the winning index.
5
Related work
Order-embedding as subsumption. Encoding a hierarchy so that subsumption becomes coordinate-wise dominance is classical: tree ancestry as a pre/post plane indexed by an R-tree [16], bit-vector lattice encodings [6], and dominance-drawing reachability [22, 20] where the number of coordinates equals the Dushnik–Miller order dimension [13]. These are static, reachability-only; we build on them and do not claim the primitive as novel. Reachability labeling. 2-hop [11], tree-cover [5], GRAIL [23], PLL [7], and the incremental, append-only, width-parameterized index of Bulteau et al. [10] answer reachability but support no aggregation. Bulteau et al. are dynamic by design (Merkle graphs); OEH is static and instead adds roll-up. Hierarchy indexes with aggregation. The TUM/SAP line is the closest: DeltaNI [14] (versioned nested intervals; “aggregate queries out of scope”), Order Indexes [15], SAP HANA hierarchies [8], and the aggregation-focused Index-Assisted Hierarchical Computations [9]. These do roll up user measures, but index-assisted: the index answers IS_DESCENDANT/order/level in O(log n) and a relational structural-grouping (join-group-aggregate) operator computes the sum per query — no measure or partial sum is stored in the index. OEH’s roll-up is index-resident: the partial aggregate is answered from the structure, from the same index that answers subsumption. Empirically (Fig. 2) their approach is our brute-force baseline. OLAP and dynamic theory. Dimension-hierarchy models [21], cube materialization [17], and Graph Cube [24] roll up but do not unify roll-up with a subsumption index over the value poset; the cuboid lattice is not the value-subsumption poset. Dynamic-treewidth maintenance [19] is relevant only to a future dynamic variant. 5
6
Limitations and honest findings • Static only. OEH supports no online insert/delete; on the dynamic axis [10, 14] are ahead. We do not claim a dynamism advantage. • Chain mode rarely wins on real DAGs. Real multi-parent DAGs (ontologies, merge histories) are high-width, so chain declines and 2-hop wins; low-width multi-parent DAGs are uncommon. • Roll-up loses on tiny subtrees (the O(log n) constant exceeds O(small)). • The TimescaleDB comparison is in-process Python vs. SQL — same regime, not a system benchmark. • Order-embedding, nested-set, and dominance are prior art (§5). • GRAIL/PLL are re-implementations (validated exact vs. the oracle); GeoNames is a near-tree DAG (0.9% multi-parent kept to one canonical parent); the chain decomposition is greedy and a near-minimum cover would be smaller.
7
Conclusion
Relationship hierarchies unify the hierarchies that time-series, spatial, and ontology systems index separately. OEH is one structure-selected index that answers subsumption and index-resident roll-up across all three domains, validated on real data and against a production time-series engine. The honest boundary — high-width DAGs defer to 2-hop — and a future dynamic variant are the natural next steps.
References [1] The gene ontology (go-basic, release 2026-05-19). http://geneontology.org, 2026. CC BY 4.0. [2] GeoNames geographical database. https://www.geonames.org, 2026. CC BY 4.0. [3] NCBI taxonomy database. https://ftp.ncbi.nih.gov/pub/taxonomy/, 2026. [4] TimescaleDB: Hierarchical continuous aggregates. https://docs.timescale.com, 2026. [5] Rakesh Agrawal, Alexander Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In SIGMOD, 1989. doi: 10.1145/67544.66950. [6] Hassan Aït-Kaci, Robert Boyer, Patrick Lincoln, and Roger Nasr. Efficient implementation of lattice operations. ACM TOPLAS, 11(1), 1989. doi: 10.1145/59287.59293. [7] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, 2013. doi: 10.1145/2463676.2465315. [8] Robert Brunel, Jan Finis, Gerald Franz, Norman May, Alfons Kemper, Thomas Neumann, and Franz Faerber. Supporting hierarchical data in SAP HANA. In ICDE, 2015. doi: 10.1109/ICDE.2015.7113393. 6
[9] Robert Brunel, Norman May, and Alfons Kemper. Index-assisted hierarchical computations in main-memory RDBMS. PVLDB, 9(12), 2016. doi: 10.14778/2994509.2994524. [10] Laurent Bulteau, Julien David, Florian Horn, and Mathieu Tran-Girard. An incremental reachability index. In SEA, 2025. doi: 10.4230/LIPIcs.SEA.2025.9. [11] Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5), 2003. doi: 10.1137/S0097539702403098. [12] Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1), 1950. doi: 10.2307/1969503. [13] Ben Dushnik and E. W. Miller. Partially ordered sets. American Journal of Mathematics, 63 (3), 1941. doi: 10.2307/2371374. [14] Jan Finis, Robert Brunel, Alfons Kemper, Thomas Neumann, Franz Faerber, and Norman May. DeltaNI: An efficient labeling scheme for versioned hierarchical data. In SIGMOD, 2013. doi: 10.1145/2463676.2465329. [15] Jan Finis, Robert Brunel, Alfons Kemper, Thomas Neumann, Norman May, and Franz Faerber. Indexing highly dynamic hierarchical data. PVLDB, 8(10), 2015. doi: 10.14778/2794367. 2794369. [16] Torsten Grust. Accelerating XPath location steps. In SIGMOD, 2002. doi: 10.1145/564691. 564705. [17] Venky Harinarayan, Anand Rajaraman, and Jeffrey D. Ullman. Implementing data cubes efficiently. In SIGMOD, 1996. doi: 10.1145/233269.233333. [18] H. V. Jagadish. A compression technique to materialize transitive closure. ACM TODS, 15(4), 1990. doi: 10.1145/88636.88888. [19] Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and Marek Sołtys. Dynamic treewidth. In FOCS, 2023. doi: 10.1109/FOCS57990.2023.00102. [20] Panagiotis Lionakis, Giacomo Ortali, and Ioannis G. Tollis. Constant-time reachability in DAGs using multidimensional dominance drawings. SN Computer Science, 2, 2021. doi: 10.1007/s42979-021-00713-6. [21] Torben Bach Pedersen, Christian S. Jensen, and Curtis E. Dyreson. A foundation for capturing and querying complex multidimensional data. Information Systems, 26(5), 2001. doi: 10.1016/ S0306-4379(01)00023-0. [22] Renan Veloso, Loïc Cerf, Wagner Meira Jr., and Mohammed J. Zaki. Reachability queries in very large graphs: A fast refined online search approach. In EDBT, 2014. [23] Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. GRAIL: Scalable reachability index for large graphs. In VLDB, 2010. doi: 10.14778/1920841.1920879. [24] Peixiang Zhao, Xiaolei Li, Dong Xin, and Jiawei Han. Graph cube: On warehousing and OLAP multidimensional networks. In SIGMOD, 2011. doi: 10.1145/1989323.1989413.
7