Back to search

University of British Columbia

Streaming algorithms with differential privacy guarantee

Abstract

dc:description

Given a data stream (a sequence of items), the distinct element estimation problem aims to approximate the number of unique items in the stream. We present two streaming algorithms to solve the distinct element estimation problem, and we prove that both are differentially private. The first algorithm solves the decision version of distinct element estimation, and then solves the general version by making calls to the decision version. This algorithm is conceptually simple, but somewhat inefficient due to this reduction to the decision version. We then extend this algorithm and its analysis to handle deletions. We show that the original algorithm and its extension use logarithmic space and can output a good estimate of distinct elements with high probability. The second algorithm is based on the Johnson-Lindenstrauss dimensionality reduction technique, but it replaces the Gaussian distribution with a stable distribution. With an appropriate choice of parameters, this approach can estimate distinct elements up to arbitrary multiplicative accuracy with high probability. We prove asymptotically tight upper and lower bounds for the density of these stable distributions using an infinite sum representation. Using those bounds, for the special case of dimensionality reduction to one dimension, we prove that this algorithm is differentially private.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gong, Zehui
Contributors dc:contributor
  • Harvey, Nicholas J. A.

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/89161

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gong, Zehui. Streaming algorithms with differential privacy guarantee. master's thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/89161