What if making the whole thing smaller makes one tiny thing harder to reach?
Imagine a library that has achieved impossible compactness. Every book has been compressed into one continuous encoded stream. Wonderful. The total archive is tiny.
Now ask for paragraph three on page 417 of one particular book.
If the decoder must begin from the start of the archive and reconstruct everything before that paragraph, our storage victory has created an access problem.
This tension is called locality in many forms: how easily can we reach the part we need without rebuilding or scanning far more than we asked for?
Quick Read
- Compression can create dependencies between nearby or earlier pieces of data.
- Those dependencies may make random access slower.
- Blocking, indexes and restart points deliberately spend extra space to improve access.
- Streaming systems care about whether data can be decoded progressively.
- Parallel systems care about whether different chunks can be decoded independently.
- Error recovery improves when dependency chains are bounded.
- The smallest possible representation may therefore be less useful than a slightly larger, better-structured one.
The One-Sentence Answer
Compression can reduce total size by coupling pieces together, but useful systems often add blocks, indexes and restart points so that one part can be reached without reconstructing too much of the rest.
Sequential Access and Random Access Are Different Jobs
A cassette tape and a digital music library both contain songs, but the access experience is different.
On a cassette, reaching song five may require moving through the tape physically. A digital index can jump directly to a track.
Compression has a similar distinction. Some formats are excellent when decoded from beginning to end. Others are designed so that arbitrary regions can be reached efficiently.
The required design depends on how the data will be used.
Why Dependencies Save Space
Suppose block B looks almost identical to block A. Rather than store B independently, we can describe B relative to A.
B = A + small difference
Then C may refer to B, D to C, and so on.
The chain can be wonderfully compact because repeated information is not restated.
But now ask for D.
If D requires C, C requires B and B requires A, the decoder cannot necessarily treat D as an isolated object. Compression has converted independent pieces into a dependency graph.
Locality Is About the Cost of Reaching
Locality asks how much neighbouring or prior material must be touched to recover what we want.
A locality-friendly representation may let us retrieve one record, one frame, one page or one genomic region without decoding gigabytes around it.
A locality-poor representation may achieve a better global compression ratio but require substantial reconstruction work for a tiny query.
This is not an abstract edge case. Databases, scientific archives, media formats, search systems and cloud storage all care about selective access.
Blocks: A Deliberate Compromise
One common strategy is to divide data into blocks and compress each block partly independently.
Small blocks improve locality because a request touches less surrounding data. But small blocks may compress less efficiently because the compressor sees less context and repetition.
Large blocks improve compression opportunities but increase the amount of material that may need to be processed for a small request.
larger block → more context, potentially better ratio smaller block → less context, potentially better access
There is no universally correct block size. It depends on workload.
Indexes Make Data Bigger on Purpose
An index consumes space.
That sounds like the opposite of compression. Yet an index can make a compressed archive vastly more useful because it tells the system where relevant chunks begin, where restart points sit, or which blocks contain particular records.
This is a beautiful engineering reversal:
We deliberately add information so that we spend less time searching.
The total file becomes slightly larger, but the user’s waiting time becomes dramatically smaller.
Restart Points Break Dependency Chains
Suppose a decoder normally needs all previous state. Designers can insert periodic restart points where the state is reset or explicitly recorded.
Now random access can begin from the nearest restart point instead of the beginning of the entire file.
Restart points cost bits because some context must be repeated or re-established. But they bound access cost and can also improve resilience after errors.
Again, a small amount of redundancy can make the system better.
Compression and Streaming
Streaming creates another constraint: the decoder should often produce useful output before the entire object has arrived.
A representation that requires the final bytes before anything can be reconstructed is poorly suited to interactive streaming, even if its final size is excellent.
Streaming-friendly compression therefore thinks about order, progressive decoding, buffering and latency.
The compressed object is not only a container. It is a journey through time.
Video Makes Locality Visible
Video compression often exploits similarity across frames. That is powerful because consecutive frames may differ only slightly.
But if every frame depended indefinitely on every earlier frame, seeking would become painful. Practical codecs therefore use structures that bound dependencies and provide independently decodable or periodically anchored frames.
When you drag a video scrubber, you are experiencing a locality problem disguised as a user-interface action.
Databases Care About Different Questions
A database may contain a billion records, but a query may request only 20 rows.
If compression forces the engine to decompress massive unrelated regions, the saved storage may not compensate for the query penalty.
Columnar systems, page-level compression, dictionary encoding and block metadata can be designed so that useful parts remain accessible without fully reconstructing everything.
Compression must respect the access pattern.
Scientific Data and the One Tiny Region
Imagine a researcher has a multi-terabyte dataset but repeatedly studies only one chromosome region, one geographical tile or one time interval.
Global maximum compression may be the wrong objective. The archive may need chunking, spatial indexing, temporal indexing or independently decodable partitions.
A useful format reflects future questions.
Parallelism Changes the Value of Independence
Modern processors contain many cores. Data centres distribute work across machines. GPUs process large numbers of operations in parallel.
If compressed chunks depend heavily on one another, parallel decoding becomes difficult. If chunks are sufficiently independent, different workers can decode simultaneously.
Independence may cost compression ratio because shared context is reduced. But it buys throughput.
This is another case where “best compression” cannot be defined by file size alone.
Errors Also Have Locality
Suppose one bit is corrupted.
In a representation with tightly chained state, that error may poison everything that follows until the decoder can resynchronise.
In a block-based format with restart points, the damage may remain bounded to one region.
Locality therefore matters not only for speed but for failure containment.
The Smallest Archive Can Be the Worst Archive
Imagine two archive formats.
- Format A is 1% smaller but takes ten minutes to extract one file.
- Format B is 1% larger but extracts any file in milliseconds.
Which is better?
For cold archival storage that is never selectively accessed, perhaps A. For interactive use, almost certainly B.
Compression quality is application-relative.
Human Memory Has Locality Problems Too
A student may remember a topic only through one long memorised chain. Ask for the third idea and they mentally recite everything from the beginning.
Another student has built an indexed structure: headings, concepts, relationships and retrieval cues. They can enter the knowledge network from several points.
The amount memorised may be similar, but accessibility differs dramatically.
Learning is not only about storing knowledge. It is about making knowledge reachable.
Primary School: Find One Item Without Reading Everything
Give pupils two lists. One is an unsorted paragraph of 100 names. The other is alphabetised with headings.
Ask them to find one name.
The second representation may occupy slightly more space because of headings, but it saves search time.
Secondary School: Compression Versus Access
Ask students to design a compact revision sheet for a topic, then impose a constraint: a classmate must be able to find any one concept within ten seconds.
Suddenly headings, indexes, colour coding and chunking become valuable. The sheet may become slightly larger but much more usable.
JC and Beyond: Succinct Does Not Mean Slow
Advanced computer science studies succinct and compressed data structures that try to approach information-theoretic space bounds while still supporting useful operations efficiently.
This is a sophisticated version of the same problem: how close can we get to minimal space without giving up fast queries?
The answer depends on the structure, operation set and computational model. There are deep lower bounds showing that space and query time can constrain one another.
Locality Is a Design Choice
When designing a compressed system, ask:
- Will users read sequentially or jump around?
- What is the smallest unit they are likely to request?
- How much surrounding data can we afford to decode?
- How important is parallelism?
- How far can errors propagate?
- How much extra index or restart metadata is acceptable?
- Does the workload favour ratio, latency, throughput or resilience?
The Deeper Point
Compression is often praised for making information occupy less space.
Locality asks a different question:
Can I reach the information I need without reconstructing a world I did not ask for?
That question changes design.
Sometimes we add an index. Sometimes we break the stream into blocks. Sometimes we repeat state. Sometimes we create restart points. Sometimes we accept a slightly worse compression ratio.
Those choices are not failures of compression. They are signs that information has to be useful after it becomes small.