ºìÐÓÊÓƵ

Topic

A Differential Privacy-Preserving Data Publishing Algorithm for Bus Trajectory Analysis: A Case Study on BC Transit

Department of Computer Science

Date & location

• Friday, September 12, 2025

• 11:00 A.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Yun Lu, Department of Computer Science, University of Victoria (Supervisor)

• Dr. Alex Thomo, Department of Computer Science, UVic (Member) 

External Examiner

• Dr. Amirali Baniasadi, Department of Electrical and Computer Engineering, University of Victoria 

Chair of Oral Examination

• Dr. Kimberly Speers, School of Public Administration, UVic

   

Abstract

The increasing use of trajectory data in location-based services and public transit planning high lights the high analytical value of such data. However, legal, technical, and especially privacy related concerns have significantly limited public access to these datasets.

This thesis investigates privacy protection in trajectory databases—specifically, passenger movement data from public bus systems—under strong Differential Privacy (DP) guarantees. 

We collaborate with BC Transit to make the first publicly available, privacy-preserving analysis of BC Transit’s bus tap dataset from Victoria, British Columbia. This work reviews existing DP mechanisms and selects two practical and applicable algorithms for public transit data. These mechanisms are then adapted and optimized to suit the unique characteristics of such data. The goal is to evaluate their practical effectiveness in privacy-preserving publication of transit data while maintaining the utility required for meaningful analysis. 

The BC transit bus tap dataset (containing bus tap-ins) enables already-useful analyses such as count or sum queries (e.g., number of visits to a bus stop) used as the benchmark of several related works. However, we aim to demonstrate the power of the state-of-the-art—privacy-preserving trajectory analyses, and with approval from our collaborators at BC Transit, we construct a plausible synthetic trajectory dataset that corresponds to the original given tap dataset based on known weekly role-specific travel patterns. Two privacy-preserving algorithms are then applied: 

• Noisy Prefix Tree (Rui Chen et al., 2011): A prefix tree-based DP algorithm for sequential data.
• PPDP (Yang Li et al., 2020): An improved prefix tree algorithm tailored for transit smart card data.

We also compare the count queries on the original data using the Laplace mechanism with those on the synthetic trajectories, to evaluate how well basic utility is preserved. 

For sequential transit data, we introduce the following technical improvements to enhance the effectiveness of prefix tree-based methods: 

• A spatio-temporal dimensionality reduction technique to sample noisy nodes with better efficiency;
• An improved post-processing method for achieving consistency in the noisy prefix tree after noise injection.

In addition, A hybrid privacy budget allocation approach is employed, which balances tree depth with the actual distribution of nodes at each level in a more intuitive and effective manner. 

Experimental results—conducted on synthetic trajectories generated from real-world tap card data from the BC Transit system—demonstrate that this framework can enforce strong privacy guaran tees while answering complex transit-related analytical queries. This work serves as one of the first steps for data sharing among researchers, municipal agencies, and smart service developers, especially in BC, contributing to the design of more efficient, innovative, and human-centered public transportation systems.