Note
This repository contains the final project for the Algorithms for Massive Datasets course at Università degli Studi di Milano (2025/2026). You can find the notes for the course in this repository.
This project implements and evaluates two fundamental data streaming algorithms: Flajolet-Martin and Bloom Filter. The objective is to analyze a massive dataset of New York Times comments (from 2020) within a strictly memory-constrained environment.
The main goal is to demonstrate how to efficiently process large data streams using
-
Flajolet-Martin: Estimates the total number of unique active users who commented on the NYT platform. The implementation utilizes bitwise operations to isolate trailing zeros and applies grouping/median techniques (with a correction factor) to mitigate variance and achieve an accurate estimate (relative error ~5%).
-
Bloom Filter: Efficiently isolates and counts comments related specifically to "Science" articles. Parameters were chosen based on theoretical mathematical formulas to minimize the False Positive Rate (achieving a real FPR of ~0.3%).
The project utilizes the New York Times Comments (2020) dataset.
Note
All experimental results refer to the dataset version downloaded on March 20, 2026.
All the implementations can be found in the Stream_analysis.ipynb notebook.
You can run the code directly in your browser using Google Colab:
To understand all the decisions and sources that led to the final implementations, please refer to the report