The Flajolet-Martin Sketch Itself Preserves
           Differential Privacy:
      Private Counting with Minimal Space

   Adam Smith          Shuang Song             Abhradeep Thakurta
  Boston University    Google Research, Brain Team       Google Research, Brain Team
  ads22@bu.edu       shuangsong@google.com          athakurta@google.com

                        Abstract
     We revisit the problem of counting the number of distinct elements F0 (D) in a data
     stream D, over a domain [u]. ...