NOTE
Handling Very Large Data Sets
Strategies for large-scale data: partitioning, external sorting, hashing, Bloom filters, streaming aggregation, distributed storage, and choosing algorithms from access patterns.
This is a historical learning note and may contain outdated or incomplete understanding.
1. Define the Operation Before Saying ‘Big Data’
Different problems need different algorithms:
- membership lookup;
- deduplication;
- top-K;
- frequency counting;
- join/intersection;
- sort;
- aggregation;
- random lookup.
The correct design depends on data size, memory budget, update rate, accuracy requirements, and whether one machine or many are available.
2. Partition First
If the full dataset does not fit on one machine or in memory, partition it by a stable key/hash/range so smaller independent pieces can be processed.
Partitioning is useful both on one host (external algorithms) and across a distributed cluster.
3. External Sorting
For data larger than memory:
- split into chunks that fit memory;
- sort each chunk;
- write sorted runs to disk;
- merge the runs.
This is the basis of external merge sort and many database execution plans.
4. Hash-Based Techniques
Hash partitioning and hash tables are useful for deduplication, joins, and membership when exact results are required.
When memory is insufficient, hash to buckets first and process buckets independently.
5. Probabilistic Structures
Bloom filters can reject definite non-members with low memory at the cost of false positives.
Approximate counters/sketches can estimate frequency/cardinality when exact answers are too expensive.
6. Streaming Aggregation
If the operation is associative/mergeable, aggregate incrementally instead of materializing all raw data.
Examples:
- counts;
- sums/min/max;
- top-K candidates;
- sketches.
7. Distributed Processing
At cluster scale, the same principles become partitioned storage + parallel compute + shuffle/merge.
The expensive part is often data movement, not CPU. Choose partition keys so most work stays local and skew/hot partitions are controlled.
8. Practical Rule
Before introducing a distributed framework, estimate whether a single machine with streaming I/O, SSDs, compression, and an external-memory algorithm already solves the problem.