How to Process 100GB Logs and Massive Datasets with Hash Partitioning and Bloom Filters

Big Data Overview

Big data (also called mega data) refers to massive, rapidly growing, and diverse information assets that require new processing models to gain stronger decision‑making, insight and process‑optimization capabilities. The 4V characteristics are Volume, Velocity, Variety and Value.

Finding the Most Frequent IP in a >100 GB Log File

Because the log cannot fit into memory, split it into many smaller files (e.g., 1000 files of ~500 MB each). Use hash partitioning (e.g., BKDRHash) to ensure the same IP hashes to the same file, then load each file sequentially, count occurrences, and finally select the IP with the highest count.

Finding Top‑K IP Addresses

Apply the same hash partitioning, maintain a min‑heap of size K for each partition, merge the heaps across all partitions, and the heap finally contains the top‑K most frequent IPs.

Identifying a Single‑Occurrence Integer among 10 billion Numbers

Estimate memory (10 billion × 4 bytes ≈ 40 GB) → cannot load at once. Solutions include hash partitioning into 100 files, bitmap‑based extensions using two bits per integer to represent three states (absent, once, multiple), or recursive bit‑wise splitting.

Computing the Intersection of Two 10 billion‑integer Files with 1 GB Memory

Three approaches: naive pairwise scanning, hash partitioning of both files into matching buckets, and bitmap (or Bloom‑filter) based methods that map integers to bits and compare the bitmaps.

Finding All Integers Appearing No More Than Twice

Similar to previous tasks, use hash partitioning or an extended bitmap that uses two bits to encode the count state (00 absent, 01 once, 10 twice, 11 >2).

Exact and Approximate Intersection of Two 10 billion‑query Files

Exact method: hash partitioning with the same hash function. Approximate method: Bloom filter built from one file and queried with the other; false positives are possible but false negatives are not.

Extending Bloom Filters for Deletion and Counting

Deletion requires reference counting for each bit; counting can be achieved with a counting Bloom filter where each bit is replaced by a small counter (e.g., an integer).

Keyword Search Across Thousands of Files with 100 KB Memory

Generate a Bloom filter for each file, store them externally, and stream filters and files in two memory buffers, using the filters to test whether a given keyword may appear in a file.

Finding All Dictionary Words Containing a Given Substring

Build a Trie (prefix tree) from the dictionary; traverse the tree matching the substring character by character, exploring all branches that share the prefix, and collect all words that contain the substring.