Common Techniques for Processing Massive Data Sets

The article provides a concise overview of several common techniques for dealing with massive data problems, acknowledging that while the methods may not cover every possible case, they address the majority of typical interview and practical scenarios.

1. Bloom Filter

Applicable for implementing data dictionaries, duplicate detection, and set intersections. The basic principle uses a bit array and k independent hash functions; setting bits to 1 on insertion and checking all bits on query, with a false‑positive rate that can be minimized by choosing k = (ln2)*(m/n). Counting Bloom filters replace the bit array with counters to support deletions. For an error rate of 0.01, the bit array size m is roughly 13 × n, and k ≈ 8.

2. Hashing

Used for fast lookup and deletion when the entire dataset fits in memory. Key points include selecting appropriate hash functions for strings, integers, or permutations and handling collisions via open hashing (chaining) or closed hashing (open addressing). The article also describes 2‑left hashing, where two hash tables T1 and T2 each have their own hash function, and a new key is placed in the less loaded table.

3. Bit‑Map

Employs a bit array to indicate the presence of elements, suitable for quick lookup, duplicate detection, and deletion when the data range is within roughly ten times the integer size. Bloom filter can be viewed as an extension of a bit‑map.

4. Heap

Ideal for finding the top‑n largest or smallest items in massive datasets when n is relatively small. A max‑heap can be used to keep the smallest n elements, and a min‑heap for the largest n. A double‑heap (max + min) can maintain the median.

5. Two‑Level Bucket Partition

Based on the divide‑and‑conquer principle, this method repeatedly partitions the data range to narrow down the target region, enabling efficient processing of problems such as finding the k‑th largest element or the median in billions of integers.

6. Database Index

Applies to large‑scale insert, delete, update, and query operations by leveraging appropriate data structures and storage designs.

7. Inverted Index

Used in search engines to map each term to the list of documents containing it. The article illustrates building an inverted index for three example sentences and explains the relationship between forward and inverted indexes.

8. External Sort

Handles sorting and deduplication of data that exceeds memory capacity, using merge‑based algorithms, replacement selection, and optimal merge trees. Example: sorting a 1 GB file of 16‑byte words with only 1 MB of memory to find the top‑100 most frequent words.

9. Trie

Effective for large datasets with many repeated strings but a limited alphabet, supporting compressed implementations and useful for tasks like frequency counting of queries.

10. Distributed Processing (MapReduce)

Divides data across multiple machines for parallel processing, followed by a reduction phase to combine results. The article discusses typical MapReduce applications such as word counting, top‑N aggregation across distributed nodes, and median finding in a distributed setting, emphasizing the importance of hash‑based partitioning to avoid skewed data distribution.

Overall, the article combines theoretical principles with practical examples to guide the selection and implementation of appropriate algorithms and data structures for big‑data processing tasks.