Back to search

Georgia Institute of Technology

Hinted Data Structures with Applications to Optimization and Learning

Abstract

dc:description.abstract

This thesis investigates the interplay among data structures, graph algorithms, and machine learning, providing a fresh lens on conventional perspectives concerning worst-case scenarios and data structure performance. The thesis is divided into two main parts. The first part delves into the concept of Low Stretch Decomposition (LSD), a crucial component in graph algorithm design. The study applies LSDs to devise a nearly linear time algorithm to compute the terminal state of graph diffusions, specifically the 2-norm flow diffusion, and identify local clusters. It also pioneers the examination of LSD on dynamic graphs, leading to the creation of fully dynamic data structures for computing approximate cuts and distances. The second part of the thesis explores how data structures leverage 'hints' to enhance their efficiency. It demonstrates this by solving maximum flows and minimum-cost flow problems using dynamic LSD and an \ell1 Interior Point Method (IPM). The hints derived from the IPM updates expedite the data structure and result in an almost linear time algorithm for the problem. This section also delves into learning-augmented B-trees, which benefit from advice produced by machine learning models. Throughout the thesis, a comprehensive understanding of how optimization algorithms and machine learning models interact with data structures in non-worst-case and non-adaptive ways is pursued.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Li
Advisor dc:contributor.advisor
  • Peng, Richard
Committee members dc:contributor.committeemember
  • Vempala, Santosh
  • Singh, Mohit
  • Gupta, Swati
  • van den Brand, Jan

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72683

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Li. Hinted Data Structures with Applications to Optimization and Learning. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72683