Protecting participants or population? Comparison of k k -anonymous Origin-Destination matrices Journal: opticajournal
Pietro Armenante, Kai Huang, Nikhil Jha, Luca Vassio · 2025
Read Protecting participants or population? Comparison of k k -anonymous Origin-Destination matrices Journal: opticajournal by Pietro Armenante, Kai Huang, Nikhil Jha, Luca Vassio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-12950.txt.
Introduction
Pietro Armenante, Kai Huang and two co-authors ask in 2025 whether trip tables should hide persons or whole groups. Trip tables count moves between zones. Small zones show travel well but risk privacy.
Rich survey data lets the team split tables by age, work, and more. Each person stands for a weighted slice of the true crowd. That fact shifts the goal: guard the crowd, not just those asked. They test zone-merging ways and add a fast greedy method. The goal is tables that stay useful yet meet the guard rule for the full crowd.
Catalog record
| CREATOR | Pietro Armenante, Kai Huang, Nikhil Jha, Luca Vassio |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-12950
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Protecting participants or population? Comparison of k k -anonymous Origin-Destination matrices Journal: opticajournal Pietro Armenante, Kai Huang, Nikhil Jha, Luca Vassio Abstract 1 Introduction Mobility data have become increasingly accessible due to the evolution of data collection processes and the diversification of their sources, such as the widespread adoption of GPS devices and mobile phones. Human mobility refers to the study of how people move, for instance, by characterizing patterns such as commuting to work, returning home, or using public transportation. A thorough understanding of these patterns is fundamental in several domains, including epidemic control and public transportation planning. Origin-Destination (OD) matrices are a core component of research on users’ mobility and summarize how individuals move between geographical regions. OD-matrices describe the flows between origins o and destinations d . Although they represent a dramatic simplification compared to original individual movements from raw data, they are still a crucial indicator of mobility and expose privacy vulnerabilities. They are often harder to anonymise than regular relational data [ 1 ] . This work is centered around the NetMob 2025 data challenge dataset [ 2 ] . 1 1 1 https://netmob.org/www25/datachallenge , accessed on August 10, 2026 There are two added values in the provided data. Firstly, the data is extensive and contains a lot of socio-demographic information that can be used to create multiple OD matrices, based on the segments of the population. Secondly, and more peculiarly, a participant is not merely a record in the data, but a quantified statistically weighted proxy for a segment of the real population. This second aspect opens the door to a fundamental shift in the anonymization paradigm. A population-based view of privacy is central to our contribution. By adjusting our anonymization framework to account for representativeness, we are also protecting the inferred identity of the actual population, rather than survey participants alone. The generation of privacy-preserving OD matrices has already been studied from various points of view. The works in [ 3 , 1 ] use local differential privacy to compute OD-matrices. Another work [ 4 ] adapts the TopDown algorithm used in the US census [ 5 ] to generate differentially private hierarchical OD data with high utility. Our approach builds upon the approach and insights from Matet et al. [ 1 ] , which propose an Adaptative Tree Generalisation (ATG) approach to anonymize OD matrices, optimizing the hierarchy generalization and comparing it with OIGH and Mondrian. Unlike these approaches, which primarily address the privacy aspects of the given datasets, we aim to contribute to the generation of privacy-preserving OD matrices enriched with socio-demographic segmentation that achieves k -anonymity on the actual population. The challenge addressed in this work is to produce and compare OD matrices that are k -anonymous for survey participants and for the whole population. Put briefly, k -anonymity [ 6 ] is a privacy property of the data: a dataset is k -anonymous if every record cannot be distinguished among at least k-1 others—in our case, if there exist at least k trips from the same origin to the same destination. We compare the OD matrices obtained by several traditional methods of anonymization to reach k -anonymity by generalizing geographical areas. These include generalization over a hierarchy (ATG and OIGH) and the classical Mondrian. To this established toolkit, we add a novel method, i.e., ODkAnon, a greedy algorithm aiming at balancing speed and quality. This novel approach is benchmarked against three well-known generalisation algorithms, evaluating both individual-level and population-level privacy through weighted mobility data. Many utility metrics are considered in the comparison. This comprehensive analysis demonstrates how significant differences may exist when considering population-protecting for OD matrices anonymization, rather than survey participant-protecting ones. Moreover, we show how these differences can even be amplified across socio-demographic segments. All the obtained results are reproducible using our open-source code available in a GitHub repository. 2 2 2 https://github.com/SmartData-Polito/ODkAnon , accessed on August 10, 2026. 2 Dataset and Methodology 2.1 Geographical area H3 hierarchy In this work, we use the well-known, Uber-developed H3 hierarchy. 3 3 3 https://h3geo.org/docs/ , accessed on August 10, 2026. In H3, data points are bucketed into hexagons. Uber decided to create H3, combining the benefits of a hexagonal global grid system with a hierarchical indexing system. Figure 1: Triangular, square, and hexagon tiles. Distance between neighbors’ centerpoints is highlighted, with hexagons neighbors’ distance being constant (image from https://www.uber.com/en-IT/blog/h3/ ). . Using a hexagon as the cell shape is critical for H3. As depicted in Figure 1 , hexagons have only one distance between a hexagon centerpoint and its neighbors’ centerpoints, compared to two distances for squares or three distances for triangles. This property greatly simplifies performing analysis and smoothing over gradients. Figure 2: Example of a H3 hierarchy of hexagons in Paris. H3 supports sixteen resolutions—we sum them up in Table 1 . Each finer resolution has cells with one seventh the area of the coarser resolution. Hexagons cannot be perfectly subdivided into seven hexagons, so the finer cells are only approximately contained within a parent cell. We show an example of how the hierarchy is organized on a portion of the Paris map in Figure 2 . Table 1: Total number of cells covering the Earth’s surface and the corresponding area in km^{2} for each level of the Uber H3 hierarchy. The levels highlighted in red are the ones taken into consideration for the NetMob 2025 Data Challenge. Resolution 4 captures the whole Île-de-France region. H3 index Number of cells Average hexagon area (km²) 0 122 4357449.416078381 1 842 609788.441794133 2 5,882 86801.780398997 3 41,162 12393.434655088 4 288,122 1770.347654491 5 2,016,842 252.903858182 6 14,117,882 36.129062164 7 98,825,162 5.161293360 8 691,776,122 0.737327598 9 4,842,432,842 0.105332513 10 33,897,029,882 0.015047502 11 237,279,209,162 0.002149643 12 1,660,954,464,122 0.000307092 13 11,626,681,248,842 0.000043870 14 81,386,768,741,882 0.000006267 15 569,707,381,193,162 0.000000895 2.2 NetMob 2025 Dataset The NetMob2025 challenge dataset [ 2 ] offers a multi-dimensional view of mobility behavior in the Île-de-France region over a continuous 7-day period. We select only participants with complete GNSS records. Then, we consider a trip completed after the absence of GNSS records for 3 minutes. Finally, we extract the origin and destination coordinates of each trip. These are anonymized, generalized to the center of the closest H3 hexagon of resolution 10. Together with origins and destinations, we employ the weight feature assigned to every trip, describing how many people the record is representative of, and three socio-demographic features (age, sex, and profession) that will allow us to build segment-specific OD matrices. The main characteristics relevant to our work are reported in Table 2 . Table 2: Challenge filtered dataset relevant characteristics. Participants with GNSS records 3,320 Represented population 9,001,164 Trips with GNSS points 81,291 H3 hexagons at resolution 10 44,011 Relevant socio-demographic features age, sex, profession The final dataset we employ is a merge of a dataset containing GNSS data and a dataset containing demographic data. Particularly, merging the two dataframes on the person_id , it is possible to obtain a structure that contains both the GPS data and the demographic data. The dataset collects data obtained between October 2022 and May 2023 and focuses on residents aged 16 to 80 in Ile-de-France (3337 participants took part in the collection).