Compressed Data Structure¶
An encoded data structure whose total space adapts to input compressibility while it still answers specified queries without fully decompressing the object.
Core Idea¶
A compressed data structure stores an object with a bit-space bound that responds to the object's compressibility while supporting named queries on the encoded form. The space count includes the information needed to answer those queries; the full object need not be expanded for each one. Actual savings depend on the input: an incompressible text can still be indexed under the construction's bound.[ref-08e33f3df3f0][ref-21b728869b13]
Scope of Application¶
Four query tasks in two evidenced settings combine input-sensitive total space with access on the encoding:
- Count text matches: An entropy-sensitive index counts occurrences of a pattern over the paper's constant-size alphabet, with its own query-time bound.[^ref-08e33f3df3f0]
- Locate text matches: The same input-sensitive index reports occurrence positions with a separate time bound that depends on the number reported.[^ref-08e33f3df3f0]
- Navigate a tree locally: A clustered labeled ordered tree uses shape and label statistics in its total-space bound while answering parent and first-child queries under the theorem's conditions.[^ref-21b728869b13]
- Inspect tree ancestry: The same encoded tree answers lowest-common-ancestor and depth queries under that total-space and navigation theorem.[^ref-21b728869b13]
Clarity¶
Ask two questions together: Does total space vary with a measure of this input's compressibility? Which operations work on the encoding, and at what cost? A file that must be fully expanded before search gives no native search contract. A compact worst-case structure without input-sensitive space may answer only the second. A structure can be both succinct and compressed, as the labeled-tree example shows.[ref-08e33f3df3f0][ref-21b728869b13]
Manages Complexity¶
The paired contract prevents a compressed payload and a large, uncounted index from being treated as a small whole. It also separates operation costs that a single word such as “search” hides: counting a text pattern and listing all its locations have different guarantees, as do basic tree navigation and some label-aware queries.[ref-08e33f3df3f0][ref-21b728869b13]
Abstract Reasoning¶
Identify the source object, the input-sensitive space measure, and the named query set. Include access machinery in the bit total, then read the query theorem with its model and parameters. Ferragina and Manzini give O(p) counting and O(p + occ log^ε u) occurrence listing for fixed positive ε in their text setting. Gańczorz gives constant-time specified navigation under a different tree/alphabet theorem. Neither bound transfers automatically to the other's object.[ref-08e33f3df3f0][ref-21b728869b13]
Knowledge Transfer¶
The reusable test moves from compressed text search to navigable compressed trees: keep the total-space and native-query questions, but replace the object, entropy measure, and operation contract. Broader Compression and Data Structure ideas may help analyze other systems; the name here remains tied to encoded computational objects and proved bit/time conditions.[ref-08e33f3df3f0][ref-21b728869b13]
Neighborhood in Abstraction Space¶
Compressed Data Structure sits in a sparse region of the domain-specific corpus (89th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Cell-Probe Model — 0.81
- Variable-Length Encoding — 0.80
- Exponential tree — 0.79
- BK-tree — 0.79
- Tree (abstract data type) — 0.79
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-08e33f3df3f0]: Ferragina, Paolo, and Giovanni Manzini. “Opportunistic Data Structures with Applications.” Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), 390–398. DOI; complete original author draft. The complete draft, not a proceedings facsimile, supplies the inspected results: abstract and Our Results (one-based PDF pp.1,3), §3.1 Theorem 1 (PDF p.7), and §3.2 Theorem 3 (PDF p.9). [^ref-21b728869b13]: Gańczorz, Michał. “Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before.” 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), LIPIcs 154, article 22:1–22:29. DOI; complete publisher PDF. The inspected article's abstract (22:1), clustering (§3, 22:6–22:8), query structure (§5, 22:11–22:13), and Theorem 15 (22:21) supply the tree case and its limits.