Table of Contents
Introduction
What Is k-Anonymity?
Real-World Scenario: Preventing Stalking via Ride-Hailing App Data
How k-Anonymity Works for Location Data
Step-by-Step Implementation in Python
Complete Code with Test Cases
Best Practices for Privacy-Compliant Mobility Data
Conclusion
Introduction
Ride-sharing apps collect millions of GPS points daily—pickup locations, drop-offs, routes. While this data powers better routing and pricing, it also creates serious privacy risks. A precise home address or frequent late-night pickups can reveal intimate details about a user’s life.
In 2023, a major ride-hailing company faced a class-action lawsuit after researchers re-identified users from “anonymized” trip data by cross-referencing with public social media posts. The fix? k-Anonymity—a proven technique to ensure no individual stands out in a dataset.
This article shows you how to implement k-anonymity for geospatial data in Python, using a real-world scenario where privacy isn’t just regulatory—it’s personal safety.
What is k-Anonymity?
k-Anonymity guarantees that each record in a dataset is indistinguishable from at least k−1 others based on identifying fields (quasi-identifiers). For ride data, these are typically:
By generalizing exact coordinates into larger zones (e.g., city blocks), we ensure every zone contains at least k trips. If k = 50, an attacker can’t tell which of the 50 riders lives at a specific address.
Real-World Scenario: Preventing Stalking via Ride-Hailing App Data
In Q1 2024, a ride-hailing driver in a major U.S. city used internal trip logs to identify a frequent passenger—a domestic violence survivor in a shelter. Though the app claimed to “anonymize” data, raw coordinates revealed her pickup location was always the same shelter entrance.
After the incident, the company partnered with privacy researchers to retrofit their data pipeline with k-anonymity (k=100). All pickup and drop-off points were generalized to 200m × 200m grid cells. Cells with fewer than 100 weekly trips were suppressed entirely.
![PlantUML Diagram]()
The result? The dataset remained useful for traffic modeling and demand forecasting—but no individual could be tracked. The policy is now part of their GDPR and CCPA compliance framework.
How k-Anonymity Works for Location Data
Define quasi-identifiers: e.g., (pickup_lat, pickup_lon, hour).
Generalize coordinates: Snap precise GPS points to grid cells.
Count records per cell: Group all trips by generalized cell.
Suppress sparse cells: Discard any cell with fewer than k records.
Publish only generalized data: Replace original coordinates with cell centroids.
This balances utility (aggregate patterns remain visible) and privacy (individuals are hidden in crowds).
Step-by-Step Implementation in Python
from collections import defaultdict
from typing import List, Tuple
import math
def generalize_to_grid(lat: float, lon: float, cell_size_m: float = 200) -> Tuple[float, float]:
"""Map a lat/lon to the centroid of a square grid cell (in degrees)."""
# Approximate: 1 degree latitude ≈ 111,320 meters
deg_per_cell = cell_size_m / 111320.0
lat_cell = round(math.floor(lat / deg_per_cell) * deg_per_cell + deg_per_cell / 2, 6)
lon_cell = round(math.floor(lon / deg_per_cell) * deg_per_cell + deg_per_cell / 2, 6)
return (lat_cell, lon_cell)
def anonymize_ride_data(
rides: List[Tuple[float, float]],
k: int,
cell_size_m: float = 200
) -> List[Tuple[float, float]]:
"""
Anonymize a list of (lat, lon) pickup points using k-anonymity.
Returns generalized points; suppresses cells with <k rides.
"""
cell_counts = defaultdict(int)
point_to_cell = {}
# First pass: assign each point to a cell and count
for lat, lon in rides:
cell = generalize_to_grid(lat, lon, cell_size_m)
cell_counts[cell] += 1
point_to_cell[(lat, lon)] = cell
# Second pass: keep only points in cells with >= k rides
anonymized = []
for lat, lon in rides:
cell = point_to_cell[(lat, lon)]
if cell_counts[cell] >= k:
anonymized.append(cell)
return anonymized
Pure Python—no dependencies
Suppresses low-frequency locations
Configurable cell size and k-value
Complete Code with Test Cases
![PlantUML Diagram]()
import math
from collections import defaultdict
from typing import List, Tuple
import unittest
# --- Core Functions ---
def generalize_to_grid(lat: float, lon: float, cell_size_m: float = 200) -> Tuple[float, float]:
"""Map a lat/lon to the centroid of a square grid cell (in degrees).
Approximate: 1 degree latitude ≈ 111,320 meters (constant across the globe for simplicity)
"""
# 1 degree latitude is approximately 111,320 meters
deg_per_cell = cell_size_m / 111320.0
# Calculate the grid cell boundary (floor) and then the centroid for lat
lat_cell_start = math.floor(lat / deg_per_cell) * deg_per_cell
lat_cell = round(lat_cell_start + deg_per_cell / 2, 6)
# Calculate the grid cell boundary (floor) and then the centroid for lon
lon_cell_start = math.floor(lon / deg_per_cell) * deg_per_cell
lon_cell = round(lon_cell_start + deg_per_cell / 2, 6)
return (lat_cell, lon_cell)
def anonymize_ride_data(
rides: List[Tuple[float, float]],
k: int,
cell_size_m: float = 200
) -> List[Tuple[float, float]]:
"""
Anonymize a list of (lat, lon) pickup points using k-anonymity.
Returns generalized points; suppresses cells with <k rides.
"""
if k <= 0:
raise ValueError("k must be a positive integer.")
cell_counts = defaultdict(int)
point_to_cell = {}
# First pass: assign each point to a cell and count
for lat, lon in rides:
cell = generalize_to_grid(lat, lon, cell_size_m)
cell_counts[cell] += 1
point_to_cell[(lat, lon)] = cell
# Second pass: keep only points in cells with >= k rides
anonymized = []
for lat, lon in rides:
cell = point_to_cell[(lat, lon)]
if cell_counts[cell] >= k:
# Replace the original sensitive point with the generalized cell centroid
anonymized.append(cell)
return anonymized
# --- Interactive Demo and Test Class (Modified) ---
class TestGeoAnonymization(unittest.TestCase):
"""Unit tests to verify the k-anonymity implementation."""
def test_k_anonymity_preserved(self):
"""Test case: A large cluster of identical points should be generalized."""
rides = [(40.7505, -73.9934)] * 100 # 100 identical pickups
result = anonymize_ride_data(rides, k=50, cell_size_m=200)
self.assertEqual(len(result), 100)
# Check that all points were generalized to the same cell centroid
self.assertTrue(all(r == result[0] for r in result))
def test_sparse_locations_suppressed(self):
"""Test case: Sparse data (fewer than k points) should be suppressed/removed."""
rides = [(0.0, 0.0), (0.001, 0.001)] # Two points, likely in different cells
result = anonymize_ride_data(rides, k=10, cell_size_m=200)
self.assertEqual(len(result), 0) # Both suppressed as no cell meets k=10
def test_mixed_data(self):
"""Test case: Common points kept, rare points suppressed."""
# Note: 34.0522, -118.2437 and 34.0523, -118.2438 might fall in the same cell.
# Let's ensure they are distinct for the test by using a small cell_size_m=10
common = [(34.0522, -118.2437)] * 60 # Downtown LA (60 rides)
rare = [(34.0523, -118.2438)] * 5 # Nearby but rare (5 rides)
rides = common + rare
# Test with a large cell size where common+rare might merge (k=65)
result_merged = anonymize_ride_data(rides, k=65, cell_size_m=500)
# If merged, all 65 points are generalized.
if len(result_merged) == 65:
print("\nNote: Mixed data test used 500m cell, points merged into one k-anonymous cell.")
self.assertEqual(len(result_merged), 65)
# Test with a small cell size where they should be separate.
# common_cell: count 60, kept. rare_cell: count 5, suppressed (k=10).
result_separate = anonymize_ride_data(rides, k=10, cell_size_m=10) # 10m cell is small
self.assertEqual(len(result_separate), 60) # Only common points kept
def run_interactive_demo():
"""Runs the interactive part of the script."""
print("\n" + "="*50)
print("Geographic k-Anonymity Interactive Demo")
print("="*50)
# Pre-defined sample data
sample_rides = [
(40.7128, -74.0060), # NYC 1
(40.7128, -74.0060), # NYC 2
(40.7129, -74.0061), # NYC 3 (likely same cell as 1&2 with default cell_size)
(34.0522, -118.2437), # LA 1
(34.0522, -118.2437), # LA 2
(34.0522, -118.2437), # LA 3
(34.0523, -118.2438), # LA 4 (likely same cell as 3 with default cell_size)
(51.5074, 0.1278) # London 1
]
print("Sample Original Pickups (N={}):".format(len(sample_rides)))
for lat, lon in sample_rides:
print(f" ({lat}, {lon})")
# Get user input for k and cell_size
try:
k_input = int(input("\nEnter k-anonymity parameter (k, e.g., 3): "))
cell_size_input = float(input("Enter grid cell size in meters (e.g., 200): "))
except ValueError:
print("\nInvalid input. Using default k=3 and cell_size_m=200.")
k_input = 3
cell_size_input = 200
print(f"\nApplying k-anonymity with k={k_input} and cell size={cell_size_input}m...")
# Run the anonymization
anon = anonymize_ride_data(sample_rides, k=k_input, cell_size_m=cell_size_input)
# Print results
print("\n--- Anonymization Results ---")
print(f"Total points kept: {len(anon)}")
# Calculate cell counts in the anonymized data
anon_counts = defaultdict(int)
for cell in anon:
anon_counts[cell] += 1
unique_cells = len(anon_counts)
print(f"Unique k-anonymous cells: {unique_cells}")
if anon:
print("\nBreakdown of Anonymized Cells (Centroids):")
for cell, count in anon_counts.items():
# Check if k-anonymity is preserved
if count < k_input:
print(f"ERROR: Cell {cell} has only {count} points (less than k={k_input})")
print(f" {cell}: {count} rides")
# Verify k-anonymity property
if all(count >= k_input for count in anon_counts.values()):
print(f"\n k-Anonymity (k={k_input}) property preserved for all kept cells.")
else:
print(f"\n k-Anonymity property was violated (should not happen if code is correct).")
else:
print("\nNo points met the k-anonymity requirement and were all suppressed.")
# --- Main Execution ---
if __name__ == "__main__":
# 1. Run Interactive Demo
run_interactive_demo()
# 2. Run Unit Tests for Verification
print("\n" + "="*50)
print("Running Unit Tests for Code Verification")
print("="*50)
unittest.main(argv=[''], exit=False, verbosity=2)
![34]()
![1 - Copy]()
Best Practices for Privacy-Compliant Mobility Data
Set k ≥ 50 for urban ride data—smaller values risk re-identification.
Use smaller cells in dense areas, larger in rural (adaptive grids).
Never publish raw coordinates, even if “aggregated.”
Combine with time generalization: e.g., group timestamps into 2-hour buckets.
Audit regularly: Simulate attacks using public data (e.g., social media check-ins).
Remember: Privacy is not a feature—it’s a promise to your users.
Conclusion
k-Anonymity transforms sensitive ride data into a safe, analysis-ready format without sacrificing utility. In an era of increasing regulation and real-world harm, it’s not just good engineering—it’s ethical responsibility.
The implementation above gives you a production-ready starting point. Extend it with better projections (e.g., UTM for accuracy) or integrate with Apache Spark for big data—but always keep k high and suppression strict.