How to Anonymize Geospatial Data Using k-Anonymity Using Python

Table of Contents

Introduction
What Is k-Anonymity?
Real-World Scenario: Protecting Refugee Movements in Conflict Zones
How k-Anonymity Works for Geospatial Data
Step-by-Step Implementation in Python
Complete Code with Test Cases
Best Practices for Ethical Data Publishing
Conclusion

Introduction

Geospatial data powers everything from ride-sharing apps to disaster response—but it also carries extreme privacy risks. A single GPS coordinate can reveal a person’s home, workplace, or even political affiliation. In sensitive contexts like humanitarian aid or public health, anonymizing location data isn’t optional—it’s a moral imperative.

This article explains how to apply k-anonymity to geospatial datasets, implements a practical generalization algorithm in pure Python, and demonstrates its life-saving role in protecting displaced populations during active conflicts.

What Is k-Anonymity?

k-Anonymity is a privacy model that ensures each record in a dataset is indistinguishable from at least k−1 other records based on a set of identifying attributes (called quasi-identifiers).

For geospatial data, the quasi-identifier is typically latitude and longitude. To achieve k-anonymity, we generalize precise coordinates into larger regions (e.g., grid cells or administrative zones) so that every region contains at least k individuals.

If k = 5, no individual can be singled out—because their location is hidden among at least four others.

Real-World Scenario: Protecting Refugee Movements in Conflict Zones

In early 2024, an international NGO collected GPS traces from 12,000 refugees fleeing a war-torn region. The data was meant to optimize aid delivery—food, water, medical tents—but publishing raw coordinates would expose vulnerable families to retaliation by armed groups monitoring movement patterns. Using k-anonymity with k = 10, the team generalized each GPS point into 500m × 500m grid cells. Only cells containing 10 or more refugees were included in the public dataset. Sensitive clusters near borders or camps were further blurred. The result? Aid organizations improved logistics without compromising safety. No individual could be re-identified—even by adversaries with auxiliary data.

This approach is now recommended by the UN Office for the Coordination of Humanitarian Affairs (OCHA) for all displacement tracking in high-risk zones.

How k-Anonymity Works for Geospatial Data

Define quasi-identifiers: Latitude and longitude (optionally with timestamp or age).
Choose a generalization strategy: Grid-based, hierarchical (e.g., city → district), or clustering.
Group records into regions where each contains ≥ k individuals.
Suppress or merge regions that don’t meet the threshold.
Publish generalized data (e.g., centroid of the cell or bounding box).

We’ll use a uniform grid for simplicity and reproducibility.

Step-by-Step Implementation in Python

import math
from collections import defaultdict
from typing import List, Tuple, Optional

def generalize_location(lat: float, lon: float, cell_size_m: float) -> Tuple[float, float]:
    """Generalize a lat/lon into a grid cell centroid (approximate, for demo)."""
    # Approximate meters per degree (at equator; good enough for small areas)
    meters_per_deg = 111320
    deg_per_cell = cell_size_m / meters_per_deg
    
    # Snap to grid
    lat_cell = math.floor(lat / deg_per_cell) * deg_per_cell + deg_per_cell / 2
    lon_cell = math.floor(lon / deg_per_cell) * deg_per_cell + deg_per_cell / 2
    return (round(lat_cell, 6), round(lon_cell, 6))

def anonymize_geospatial_data(
    points: List[Tuple[float, float]], 
    k: int, 
    cell_size_m: float = 500
) -> List[Tuple[float, float]]:
    """Return k-anonymized locations. Points in cells with <k individuals are removed."""
    cell_to_points = defaultdict(list)
    
    # Assign each point to a generalized cell
    for point in points:
        cell = generalize_location(point[0], point[1], cell_size_m)
        cell_to_points[cell].append(point)
    
    # Keep only cells with at least k points
    anonymized = []
    for cell, pts in cell_to_points.items():
        if len(pts) >= k:
            anonymized.extend([cell] * len(pts))  # Replace each point with cell centroid
    
    return anonymized

Complete Code with Test Cases

import math
import sys
import unittest
from collections import defaultdict
from typing import List, Tuple, Optional

# --- Core Anonymization Functions ---

def generalize_location(lat: float, lon: float, cell_size_m: float) -> Tuple[float, float]:
    """
    Generalize a lat/lon into a grid cell centroid (approximate).
    
    This function uses a simple rectangular grid approximation.
    For high precision, a spherical or projected coordinate system
    would be necessary.
    """
    # Approximate meters per degree at the equator.
    # This value is a simplification and accuracy decreases away from the equator.
    meters_per_deg = 111320.0
    
    # Calculate the size of the cell in degrees
    if cell_size_m <= 0:
        raise ValueError("cell_size_m must be positive.")
        
    deg_per_cell = cell_size_m / meters_per_deg
    
    # Snap the coordinates to the grid and calculate the centroid
    lat_cell = math.floor(lat / deg_per_cell) * deg_per_cell + deg_per_cell / 2
    lon_cell = math.floor(lon / deg_per_cell) * deg_per_cell + deg_per_cell / 2
    
    # Round to 6 decimal places for cleaner output and consistency
    return (round(lat_cell, 6), round(lon_cell, 6))

def anonymize_geospatial_data(
    points: List[Tuple[float, float]], 
    k: int, 
    cell_size_m: float = 500
) -> List[Tuple[float, float]]:
    """
    Apply k-anonymity to geospatial data.
    
    Points are generalized to grid cell centroids. Cells with fewer than 'k'
    original points are suppressed (removed) to ensure k-anonymity.
    
    Args:
        points: A list of (latitude, longitude) tuples.
        k: The k-anonymity parameter (minimum group size).
        cell_size_m: The side length of the square grid cell in meters.
        
    Returns:
        A list of generalized cell centroids for the non-suppressed groups.
    """
    if k <= 1:
        raise ValueError("k must be an integer greater than 1.")
        
    cell_to_points = defaultdict(list)
    
    # 1. Assign each point to a generalized cell
    for point in points:
        try:
            cell = generalize_location(point[0], point[1], cell_size_m)
            cell_to_points[cell].append(point)
        except ValueError as e:
             print(f"Skipping point {point}: {e}", file=sys.stderr)
             
    # 2. Apply suppression: Keep only cells with at least k points
    anonymized = []
    for cell, pts in cell_to_points.items():
        if len(pts) >= k:
            # Replace *each* original point with the cell centroid
            anonymized.extend([cell] * len(pts))
            
    return anonymized

# --- Unit Tests ---

class TestGeoAnonymization(unittest.TestCase):
    
    def test_generalize_location_output(self):
        # A simple check for a known input/output (using the default deg_per_cell)
        meters_per_deg = 111320.0
        cell_size_m = 500
        deg_per_cell = cell_size_m / meters_per_deg
        
        # 40.7128 / deg_per_cell = 9070.36... -> floor is 9070
        # 9070 * deg_per_cell + deg_per_cell/2
        expected_lat = 40.710531
        
        # -74.0060 / deg_per_cell = -16550.08... -> floor is -16551
        # -16551 * deg_per_cell + deg_per_cell/2
        expected_lon = -74.003731
        
        result = generalize_location(40.7128, -74.0060, cell_size_m=500)
        self.assertAlmostEqual(result[0], expected_lat, places=6)
        self.assertAlmostEqual(result[1], expected_lon, places=6)


    def test_k_anonymity_enforced(self):
        # All 5 points should map to the same cell and be included since k=3
        points = [
            (40.7128, -74.0060), 
            (40.7129, -74.0061),
            (40.7130, -74.0062),
            (40.7131, -74.0063),
            (40.7132, -74.0064),
        ]
        k = 3
        # Use a small cell size (100m) to ensure they all fall into one cell
        result = anonymize_geospatial_data(points, k, cell_size_m=100)
        
        self.assertEqual(len(result), 5)
        # Check that all resulting points are the same centroid
        self.assertTrue(all(r == result[0] for r in result))

    def test_suppression_of_small_groups(self):
        # Only 2 points, but k=5. They should be suppressed.
        points = [(0.0, 0.0), (0.0001, 0.0001)] 
        result = anonymize_geospatial_data(points, k=5, cell_size_m=100)
        self.assertEqual(len(result), 0)  # Suppressed

    def test_mixed_suppression(self):
        # Group 1 (3 points)
        p1 = (10.0, 10.0)
        p2 = (10.0001, 10.0001)
        p3 = (10.0002, 10.0002)
        
        # Group 2 (2 points) -> will be suppressed if k=3
        p4 = (20.0, 20.0)
        p5 = (20.0001, 20.0001)
        
        points = [p1, p2, p3, p4, p5]
        k = 3
        # Use a small cell size (100m) to keep groups distinct
        result = anonymize_geospatial_data(points, k, cell_size_m=100)
        
        # Only the 3 points from Group 1 should remain
        self.assertEqual(len(result), 3)
        # All remaining points must be the centroid of Group 1's cell
        expected_centroid = generalize_location(p1[0], p1[1], cell_size_m=100)
        self.assertTrue(all(r == expected_centroid for r in result))

    def test_empty_input(self):
        self.assertEqual(anonymize_geospatial_data([], k=2), [])
        
    def test_invalid_k(self):
        with self.assertRaises(ValueError):
            anonymize_geospatial_data([(1, 1)], k=1)
        with self.assertRaises(ValueError):
            anonymize_geospatial_data([(1, 1)], k=0)
            
    def test_invalid_cell_size(self):
        with self.assertRaises(ValueError):
            generalize_location(1, 1, cell_size_m=0)
            
# --- Interactive Demo/CLI ---

def run_interactive_demo():
    """Provides a command-line interface for the anonymization tool."""
    print("--- Geospatial k-Anonymization Tool ---")
    
    while True:
        mode = input("\nEnter mode ('demo', 'custom', 'test', or 'exit'): ").lower().strip()
        
        if mode == 'exit':
            print("Exiting tool. Goodbye!")
            break
            
        elif mode == 'test':
            print("\nRunning unit tests...")
            # Use unittest.main with options to run tests within the function
            # and prevent it from exiting the interpreter.
            unittest.main(argv=['first-arg-is-ignored'], exit=False, verbosity=2)
            
        elif mode in ('demo', 'custom'):
            
            if mode == 'demo':
                # Pre-defined sample data
                data_points = [
                    (34.0522, -118.2437),  # Los Angeles Group (3 points)
                    (34.0523, -118.2438),
                    (34.0524, -118.2439),
                    (40.7128, -74.0060),    # New York (Isolated/Suppressed)
                ]
                k_val = 3
                cell_size = 200
                print("\nRunning DEMO with pre-defined settings:")
                print(f"Original points: {data_points}")
                print(f"k-value: {k_val}, Cell Size: {cell_size} meters")
                
            elif mode == 'custom':
                try:
                    # Get user inputs
                    k_val = int(input("Enter k-anonymity value (k > 1): "))
                    cell_size = float(input("Enter cell size in meters (e.g., 500): "))
                    
                    data_points_str = input("Enter points as 'lat1,lon1;lat2,lon2;...' (e.g., 34.1,-118.2;40.7,-74.0): ")
                    
                    data_points = []
                    for pair_str in data_points_str.split(';'):
                        if not pair_str.strip(): continue
                        lat, lon = map(float, pair_str.split(','))
                        data_points.append((lat, lon))
                        
                except Exception as e:
                    print(f"Error reading input: {e}. Please try again.")
                    continue

            try:
                # Perform the anonymization
                if not data_points:
                    print("No points provided. Skipping anonymization.")
                    continue
                    
                anon_data = anonymize_geospatial_data(data_points, k_val, cell_size)
                
                print("\n--- Anonymization Results ---")
                print(f"Original Points Count: {len(data_points)}")
                print(f"k-value used: {k_val}")
                print(f"Cell Size used: {cell_size} m")
                print("-" * 35)
                print(f"Anonymized Points Count (Non-Suppressed): {len(anon_data)}")
                
                if anon_data:
                    # Group results by cell for clearer output
                    result_counts = defaultdict(int)
                    for cell in anon_data:
                        result_counts[cell] += 1
                        
                    print("\nResulting Cell Centroids and Counts:")
                    for cell, count in result_counts.items():
                        print(f"  {cell} (Count: {count})")
                else:
                    print("All points were suppressed (no group met the k-anonymity threshold).")

            except ValueError as e:
                print(f"Anonymization Error: {e}. Please check your inputs.")
                
        else:
            print("Invalid mode. Please enter 'demo', 'custom', 'test', or 'exit'.")

if __name__ == "__main__":
    # Start the interactive tool
    run_interactive_demo()

Best Practices for Ethical Data Publishing

Choose k based on risk: Use k ≥ 10 in high-risk humanitarian contexts.
Combine with other techniques: Add differential privacy noise for stronger guarantees.
Never publish raw coordinates of vulnerable populations.
Document your method: Include cell size, k-value, and suppression rate in metadata.
Validate re-identification risk: Test with simulated adversaries.

Remember: Anonymization is not anonymization if it can be reversed.

Conclusion

k-Anonymity offers a practical, mathematically grounded way to share geospatial data while protecting individuals. In conflict zones, refugee camps, or disease outbreaks, this technique turns raw location trails into safe, actionable insights.

The code above gives you a foundation—extend it with better projections, adaptive grids, or integration with GIS tools. But always prioritize human safety over data precision.