Privacy Leakage from a Thousand Words: Millipixel Location Recovery from Dot Maps

1 Introduction

• Dot maps remain widely used in sensitive fields, making privacy-risk assessment important alongside their analytical utility.Healthcare uses include disease surveillance and risk assessment; privacy breaches can threaten personal safety and cause legal, ethical, and social harms.Source: §1 · p. 1
• Earlier centroid-recovery studies reported around 100-meter average errors on limited-area maps, while methods yield errors of hundreds of meters on country- or continent-scale maps.One study recovered residential locations from a U.S. parish map with 96.38-meter average error.Source: §1 · p. 2
• AutoLocate exploits anti-aliasing boundary artifacts, whose blended colors encode sub-pixel information about dot centroids.It refines coordinates by minimizing perceptual differences between target dots and rendered candidate maps.Source: §1 · p. 2
• Approximately 1 meter of recovery error (0.0002 pixel precision) on large-region maps, with up to 200× greater recovery accuracy than existing methods.Experiments include synthetic and real population data across map configurations and visualization tools.Source: §1 · p. 2
• The paper also explores mitigation strategies and introduces a tool that recommends coordinate quantization levels using population density and a target anonymity level.The tool is intended to help practitioners evaluate and mitigate privacy risks when publishing dot maps.Source: §1 · p. 2

Widespread Use of Dot Maps

• Dot maps use visual scatter to show spatial patterns, especially density variation, and are used across government, media, and research.Source: §2 · p. 2
• A survey found published raster dot maps depicting sensitive attributes, with no surveyed publication explicitly documenting data-protection practices.Rasterization is described as supporting storage efficiency, platform compatibility, and print publication.Source: §2 · p. 3

Anti-Aliasing in Dot Maps

• Anti-aliasing blends boundary pixels with the background, and sub-pixel dot motion changes sample counts that alter pixel color.In SSAA, pixel color depends on how many sub-samples fall inside the dot.Source: §2 · p. 3
• Edge-color gradients can reveal sub-pixel dot positions, potentially at millipixel precision, without knowing the target map’s anti-aliasing algorithm.Source: §2 · p. 3

Adversary’s Capabilities

• The adversary aims to recover each dot’s latitude and longitude and is assumed to know dot properties, access raster pixels and a similar renderer, and derive a map-to-coordinate transform.The rendering process is treated as a black box; the attack does not require its internal anti-aliasing details.Source: §3 · p. 3

Attack Scenarios

• The two scenarios are background known, where the original or reproducible background is available, and background unknown, where only the final map is available.Source: §3 · pp. 3–4

Graph Representation of Raster Maps

• The raster map is modeled as a grid graph with pixels as nodes and edges to their eight spatial neighbors; dot regions are connected components of matching-color pixels.Source: §3 · p. 4

Baseline: PixelMatch

• PixelMatch estimates dot locations by finding connected components of exact dot-color pixels and mapping each component’s centroid to geographic coordinates.Source: §3 · p. 4

Missed Opportunities of Existing Approaches

• PixelMatch ignores anti-aliased boundary pixels, which distinguish sub-pixel positions, and treats merged overlapping dots as one component.Simply adding boundary pixels to the centroid calculation is also reported as ineffective for high-precision recovery.Source: §3 · p. 4

4 AutoLocate: A Framework for Automated Location Recovery from Dot Maps

• AutoLocate iteratively adjusts estimated dot locations to minimize perceptual discrepancy between the target map and a rendered candidate map.Source: §4 · p. 4, §4.1 · p. 4

4.1 Attack Method

• Boundary pixels blend dot and background colors, and their color values are sensitive to sub-pixel position; fully covered inner pixels carry no such positional information.Source: §4.1 · p. 4
• The framework initializes locations with K-Means, then repeatedly renders maps for stay, left, right, up, and down shifts and selects the lowest-loss direction for each dot.Source: Figure 3 · p. 5, §4.1 · p. 5
• The perceptual loss compares relative color deviations between target and candidate maps at each dot’s boundary pixels.Source: §4.1 · pp. 4–5
• For overlapping dots, AutoLocate estimates dot count from component area, initializes locations with K-Means, and assigns each boundary pixel to its nearest estimated centroid.Source: §4.1 · p. 5
• Because rendering is a black box with intractable gradients, Perceptual Coordinate Descent probes neighboring grid positions and selects the move that most reduces loss.Source: §4.1 · p. 5
• When the background is unknown, AutoLocate estimates boundary-pixel background colors from neighboring pixels outside the dot region, then runs the recovery process unchanged.Source: §4.1 · pp. 5–6

5.1 Experimental Setup

• The evaluation uses OpenAddresses and synthetic ground-truth coordinates, varies map scale, background, resolution, format, geometry, and rendering platform, and compares AutoLocate variants with recovery baselines.The baseline comparison is restricted to isolated dots because existing approaches focus on that setting.Source: §5.1 · pp. 6–7, §5 · p. 6

5.2 Evaluation of AutoLocate (RQ1)

• Approximately 1 meter for AutoLocateBK and 2 meters for AutoLocateBU on OpenAddresses at small scale, versus baseline errors of hundreds of meters.These correspond to more than 200× and 100× improvements over the strongest baseline, respectively.Source: Table 3 · p. 7, §5.2 · p. 8
• Across backgrounds, resolutions, GSDs, dot properties, platforms, and formats, AutoLocate remains effective, though satellite complexity and JPEG compression degrade performance.At 96 DPI, AutoLocateBK remains below 5 meters; across platforms, recovery stays within 10 meters, and under JPEG compression the methods outperform baselines by nearly 50×.Source: §5.2 · pp. 8–9, Table 9 · p. 9
• With five overlapping dots, AutoLocateBK stays below 6 meters median error, while AutoLocateBU reaches as high as 27 meters; both also generalize to Mexico.On Mexico maps, AutoLocateBK recovers locations within 0.60 m and 0.73 m on OpenAddresses and Synthetic, respectively; AutoLocateBU is also sub-meter.Source: §5.2 · pp. 9–10, Table 10 · p. 9, Table 11 · p. 10

5.3 Ablation Study (RQ2)

• A large optimization step fails to converge and a small one converges slowly; the default 𝜂=0.05 reaches the lowest perceptual loss within 30 iterations.Background deviations reduce AutoLocateBK accuracy, and when the background is unknown or cannot be reproduced, the authors recommend AutoLocateBU.Source: §5.3 · p. 10, Table 12 · p. 10, Figure 5 · p. 10
• Tool mismatches leave both AutoLocate variants within 3 meters, while repeated rendering makes them slower than baselines but still practical on a laptop.Reducing input coordinate precision to four or five decimal places keeps errors below 6 meters across both datasets; extending the boundary-pixel set yields no noticeable performance difference.Source: §5.3 · pp. 10–11, Table 13 · p. 10, Table 14 · p. 11

5.4 In-depth Analysis (RQ3)

• Recovery difficulty varies across dots: many have low errors, but overlapping dots—especially those with five overlaps—show higher errors than isolated dots.The median error is under 2 meters, and some lower-quartile instances are recovered with near-perfect accuracy.Source: §5.4 · p. 11, Figure 6 · p. 11
• Tightly clustered dots are harder to localize because shared boundary pixels leave little information, whereas separated dots with clearer boundaries and simple, high-contrast backgrounds are easier.The analysis also finds both attacks remain accurate and robust across low- and high-background-complexity and contrast categories.Source: §5.4 · pp. 11–12, Table 17 · p. 12

Potential Mitigation Strategies

• Disabling anti-aliasing, geo-masking, and location quantization each raise recovery errors from around 1 meter to tens or hundreds of meters, making individual locations ineffective to identify.The authors choose these as simple, widely known representative mitigation classes rather than evaluating more sophisticated methods.Source: §6 · p. 12, Table 18 · p. 12

Privacy Risk Assessment Tool

• The assessment tool selects each location’s finest coordinate precision such that its spatial cell is expected to contain at least k residents, using population density to guide quantization.The released location is indistinguishable from those of at least k residents under the described k-anonymity approach.Source: §6 · p. 12

Effectiveness of the Assessment Tool

• As k rises from 10 to 100, mean anonymity set size increases from 168.25 to 1,472.24 residents, while recommended precision falls from 2.44 to 1.85 decimal places.Mean anonymity set size exceeds the target k in all settings; the greater margins arise because many dots fall in densely populated areas.Source: Table 19 · p. 12, §6 · p. 13
• The resulting quantization could reduce utility for large-scale maps but has less impact on maps intended to show broad regional trends.The study notes that two or three decimal places correspond approximately to kilometer- or hundred-meter-scale precision, while one decimal place is about ten-kilometer scale.Source: §6 · p. 13

Privacy Risks with Dot Maps

• Prior studies report re-identification from dot maps, including over 26% of locations on presentation maps and over 79% on publication maps, alongside documented disclosure of home addresses.The cited work also raises ethical and security concerns for people with stigmatized conditions.Source: §7 · p. 13
• Most prior recovery work targets limited-area maps, leaving broader-region dot maps and anti-aliasing-based recovery comparatively unexplored.The paper studies how rendering techniques can be leveraged to recover high-precision location information.Source: §7 · p. 13

Image Vectorization and Deblurring

• Image-vectorization methods also recognize sub-pixel information in anti-aliasing, but pursue visual reconstruction rather than geographic coordinates and often require differentiable rendering.The paper reports that Raster2Vec produces location-recovery errors orders of magnitude larger than its methods.Source: §7 · p. 13

8 Conclusion

• AutoLocate is an optimization-based framework that exploits anti-aliasing artifacts to recover precise locations across datasets and map configurations.The authors describe the work as revealing a new attack vector and opening further directions for analyzing spatial-visualization privacy risks.Source: §8 · pp. 13–14

• The artifact includes source code for the proposed attacks.Source: A Open Science · p. 15
• It also includes the benchmarks used with the work.Source: A Open Science · p. 15
• The privacy assessment tool is included in the repository at the listed GitHub address.https://github.com/PuddlesPenguin/AutoLocate/Source: A Open Science · p. 15

• The ethical assessment follows the Menlo Report framework and CCS 2026 ethical guidelines.Source: B Ethics Considerations · p. 15
• Experiments use synthetic or public datasets, and do not target specific individuals or proprietary dot maps.Source: B Ethics Considerations · p. 15
• The authors identify researchers, map creators, data subjects, software developers, and adversaries as stakeholders, noting potential malicious use to identify people or locations.Source: B Ethics Considerations · pp. 15–16
• They argue that disclosing vulnerabilities can help the research community address privacy risks before real-world exploitation.Source: B Ethics Considerations · p. 16
• The authors disclosed findings to evaluated map-platform developers and the U.S. CDC; several stakeholders engaged, and work to address the risk is ongoing.Source: B Ethics Considerations · p. 16

• The survey searches academic databases and general search engines with domain-specific queries spanning public health, criminology, ecology, social science, education, and archaeology.Source: C Literature Survey of Dot Map Usage · p. 16
• Sources are manually checked for raster dot maps representing discrete data points; the selected examples are illustrative, not a comprehensive or systematic review.The authors refer readers to for a more complete survey of spatial visualization usage in academic research.Source: C Literature Survey of Dot Map Usage · p. 16
• 287 of 306 dots (93.8%) in one map and 6 of 9 red dots (66.7%) in another are isolated, supporting applicability because AutoLocate performs strongly on isolated dots.Figure 7 shows examples of published dot maps where most dots are isolated.Source: C Literature Survey of Dot Map Usage · p. 16, Figure 7 · p. 16

• The implementations have comparable median errors for isolated and overlapping dots; per-dot improves one reported case from 27.00 m to 22.00 m but requires over an order of magnitude more runtime.The example is four overlapping dots on OpenAddresses using AutoLocateBU; the comparison is in Table 20.Source: Table 20 · p. 17, D Implementation Details · p. 17
• Batched implementation shifts all dots simultaneously for each search direction, keeping the number of rendered maps per iteration independent of dot count.Source: D Implementation Details · pp. 16–17
• Boundary identification examines four neighboring pixels around each pixel in a dot region, collecting outside pixels and assigning each to its nearest dot.The procedure returns a boundary pixel set for each estimated dot location.Source: D Implementation Details · p. 17