Differentially Private Range Counting in General Metric Spaces

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Differentially Private Range Counting in General Metric Spaces"

by

CHEN Shr-en

Abstract:

Range counting under differential privacy has been studied extensively in 
Euclidean spaces, but existing methods rely on coordinate structure and 
degrade with ambient dimension, precluding their use on non-Euclidean data 
such as graphs or high-dimensional embeddings. We propose DP-GNAT and DP-VP 
Tree, two metric-tree-based algorithms for differentially private approximate 
range counting in general metric spaces, operating in the public-assisted 
setting under the fuzzy query model. Experiments on synthetic Gaussian data, 
real-world 384-dimensional text embeddings, and a non-Euclidean road network 
show that DP-GNAT consistently achieves lower fuzzy relative error than all 
Euclidean baselines, with the accuracy gap widening in higher dimensions. On 
the road network—where no Euclidean baseline applies—both methods produce 
meaningful estimates, confirming the generality of the metric-space approach. 
Formal runtime and utility guarantees remain open, as general metric spaces 
lack the structural properties needed for a complexity analysis.

Date            : 30 April 2026 (Thursday)

Time            : 15:00 - 15:40

Venue           : Room 2131B (near Lift 19), HKUST

Advisor         : Prof. YI Ke

2nd Reader      : Dr. ARYA Sunil