Back to search

University of Waterloo

Parallel Efficient Secure DBSCAN Approximation

Abstract

dc:description.abstract

Machine learning has permeated every part of our data lives. With the prevalence of machine learning comes an insatiable need for data, including sensitive personal data. As a result, the need arose to develop techniques for machine learning tasks that preserve individual privacy while providing high utility by learning from private data somehow. An important class of machine learning tasks is clustering, which can potentially be used to study diseases by identifying clusters of patients. As patient information is private, private clustering algorithms would help us infer patterns among patients while protecting their data. DBSCAN is a clustering algorithm that is widely used to detect clusters of arbitrary shape among the data points. Existing private implementations of DBSCAN either exhibit significant leakage, are highly sequential, or are asymptotically inefficient both in runtime and communication cost. In this thesis, we present an efficient approximation of DBSCAN that takes O(log²n) parallel time and O(nlog²n) total work, breaking the quadratic barrier in Secure Multiparty implementations of DBSCAN algorithms and reducing the communication rounds asymptotically from O(n²) to O(log²n).

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shehata, Mohannad

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/23689

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shehata, Mohannad. Parallel Efficient Secure DBSCAN Approximation. University of Waterloo, 2026. https://hdl.handle.net/10012/23689