Dot maps can reveal precise locations through hidden image details
Privacy Leakage from a Thousand Words: Millipixel Location Recovery from Dot Maps
Cryptography and SecurityComputer Vision and Pattern Recognition
Summary
Dot maps show individual points over a geographic area to display sensitive data. The authors found that these maps can leak very precise location information due to small visual effects caused when the map is created. Their tool AutoLocate uses these tiny image details to accurately recover locations, sometimes within a meter. The researchers also suggest ways to protect privacy and help map makers understand the risks before sharing dot maps publicly.
dot mapsprivacy leakagelocation recoveryanti-aliasingblack-box optimizationperceptual discrepanciesmap renderingspatial datasub-pixel information
Authors
Yuntao Du, Tanishq Pauskar, Hao Wang, Jing Su, Ninghui Li
Abstract
Dot maps, which visualize individual data points as dots over a geographic region, are widely used across diverse domains to represent spatial patterns in sensitive data. However, the understanding of the privacy risks associated with dot maps remains limited, particularly for maps covering large geographic areas. In this paper, we systematically analyze these risks and present AutoLocate, an automated framework for high-precision location recovery. At its core, AutoLocate exploits anti-aliasing artifacts introduced during map rendering, which inadvertently encode sub-pixel information about dot locations. AutoLocate formulates location recovery as a black-box optimization problem, iteratively refining estimated coordinates by minimizing perceptual discrepancies over these artifacts between the target map and rendered candidate maps. Extensive experiments on both real-world and synthetic datasets, across different attack scenarios and a broad range of map configurations (e.g., map scale, background, resolution), demonstrate the effectiveness of AutoLocate. In particular, it achieves average recovery errors as low as 1 meter (approximately 0.0002 pixel precision) on small-scale maps of the United States, over 200x more accurate than existing approaches. We also propose mitigation strategies and introduce a privacy risk assessment tool to help practitioners evaluate and reduce privacy leakage when publishing dot maps.