Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$41,000.00

Join Algorithms Meet New Constraints: Scalability, Latency and Privacy

FY 2024-25

Summary
Query evaluation is a fundamental problem in database systems, studying how to compute efficiently answers to questions specified in SQL. Join comes as the core operator, since many real-world analytical queries rely on the join operator to link information stored in different tables. The need to process and analyze big data has invigorated this long-running research area with new challenges. Firstly, data has grown tremendously both in size and complexity beyond a single machine's capability, which has resulted in massively parallel systems for data processing. How to scale join evaluation with thousands of machines in parallel? Existing join algorithms are limited to specific classes of queries or narrow range of optimality. Secondly, data is generated at very high speeds. How to deliver timely answers to join queries with low latency? Existing join algorithms cannot easily adapt to changes in data statistics, thus they suffer from severe delay or high maintenance overhead of auxiliary indexes. Thirdly, data is typically integrated from multiple sources and contains sensitive information, which has given rise to increasing privacy concerns. How to evaluate join queries without revealing sensitive information in the data? Unfortunately, existing join algorithms suffer from severe privacy leakage during evaluation or prohibitively high inefficiency for full obliviousness. The long-term goal of the proposed research is to establish a strong theoretical foundation for join algorithms to address the new challenges brought about by emerging data and applications. This research program will build on my current work on database theory and its applications to practical database systems. Working towards this goal, I propose the following three algorithmic objectives: (O1) to design scalability-aware join algorithms for massively parallel systems that obtain an optimal tradeoff between data transmission and synchronization cost; (O2) to design latency-aware join algorithms that are adaptive to data sequences while achieving an optimal tradeoff between the maintenance cost of auxiliary indexes and delay; (O3) to design privacy-aware join algorithms that exploit an optimal tradeoff between privacy and efficiency. These newly developed algorithms will be implemented and evaluated on real-world data analytical applications. As a result, this research program will equip researchers from computer science and other domains with powerful tools for data analytics, and further benefit the community building in Waterloo (e.g., ''Smart Waterloo Region'') as well as Canada (e.g., ''Data Science Network for the Federal Public Service''). Moreover, both graduate and undergraduate students will be trained through this research program with comprehensive skills and in-depth knowledge in big data processing, who will disseminate impact into academia and industry in the future.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-03668
Name nom
Hu, Xiao
Department département
David R. Cheriton School of Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2711
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Database management
Research subject fr
Gestion de bases de données
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Join Algorithms Meet New Constraints: Scalability, Latency and Privacy
Keywords
join query; massively parallel algorithms; dynamic algorithms; oblivious algorithms; big data; conjunctive query; worst-case optimal; instance-optimal
Application summary
Query evaluation is a fundamental problem in database systems, studying how to compute efficiently answers to questions specified in SQL. Join comes as the core operator, since many real-world analytical queries rely on the join operator to link information stored in different tables. The need to process and analyze big data has invigorated this long-running research area with new challenges. Firstly, data has grown tremendously both in size and complexity beyond a single machine's capability, which has resulted in massively parallel systems for data processing. How to scale join evaluation with thousands of machines in parallel? Existing join algorithms are limited to specific classes of queries or narrow range of optimality. Secondly, data is generated at very high speeds. How to deliver timely answers to join queries with low latency? Existing join algorithms cannot easily adapt to changes in data statistics, thus they suffer from severe delay or high maintenance overhead of auxiliary indexes. Thirdly, data is typically integrated from multiple sources and contains sensitive information, which has given rise to increasing privacy concerns. How to evaluate join queries without revealing sensitive information in the data? Unfortunately, existing join algorithms suffer from severe privacy leakage during evaluation or prohibitively high inefficiency for full obliviousness. The long-term goal of the proposed research is to establish a strong theoretical foundation for join algorithms to address the new challenges brought about by emerging data and applications. This research program will build on my current work on database theory and its applications to practical database systems. Working towards this goal, I propose the following three algorithmic objectives: (O1) to design scalability-aware join algorithms for massively parallel systems that obtain an optimal tradeoff between data transmission and synchronization cost; (O2) to design latency-aware join algorithms that are adaptive to data sequences while achieving an optimal tradeoff between the maintenance cost of auxiliary indexes and delay; (O3) to design privacy-aware join algorithms that exploit an optimal tradeoff between privacy and efficiency. These newly developed algorithms will be implemented and evaluated on real-world data analytical applications. As a result, this research program will equip researchers from computer science and other domains with powerful tools for data analytics, and further benefit the community building in Waterloo (e.g., ''Smart Waterloo Region'') as well as Canada (e.g., ''Data Science Network for the Federal Public Service''). Moreover, both graduate and undergraduate students will be trained through this research program with comprehensive skills and in-depth knowledge in big data processing, who will disseminate impact into academia and industry in the future.