Algorithm Overviews

This page presents a brief overview of differentially private algorithms for answering range queries in 1- and 2-dimensions.

Name Dimensionality Year Proposed Data Independent Scale-Epsilon Exchangeable Consistent
Identity Any 2006 Y Y Y
Hb Any 2013 Y Y Y
Uniform Any Baseline N Y Y
MWEM Any 2012 N Y N
MWEM* Any 2016 N N N
AHP Any 2014 N Y Y
AHP* Any 2016 N Y Y
DPCube Any 2014 N Y Y
DAWA 1D, 2D 2014 N Y Y
QuadTree 2D 2012 N Y N
UGrid 2D 2013 N Y Y
AGrid 2D 2013 N Y Y
PHP 1D 2012 N Y N
EFPA 1D 2012 N Y Y
StructureFirst 1D 2013 N N Y