PhD Dissertation Proposal: An La, Data Structures for Dynamic Metric Spaces

Content

Speaker:

An La

Abstract:

We study geometric problems in a dynamic setting, where the point set evolves through insertions and deletions. The ultimate goal of a dynamic data structure is to maintain geometric objects efficiently over time. This naturally leads to two fundamental objectives: locality, where each metric update affects only a small part of the data structure, and tractability, where changes induced by an update can be identified and implemented in small running time. The representation of the metric space therefore plays a central role in algorithm design: it should preserve sufficient geometric information while guaranteeing that each insertion or deletion induces local and tractable changes to the representation itself.

In doubling metrics, net trees provide this underlying representation and serve as the backbone for several dynamic geometric applications, including nearest-neighbor search, spanners, tree covers, distance oracles, compact routing schemes, and $k$-center clustering. However, existing dynamic net-tree constructions focus on packing and covering properties. As a result, applications must handle the missing geometric information, and achieving locality and tractability in these applications becomes more challenging.

In this work, we augment dynamic net trees with additional geometric invariants. Motivated by shifted quadtrees in Euclidean metrics, we formalize the shifting property for net trees in doubling metrics, which provides a collection of net trees with different decompositions of the space. We also introduce the freshness property for dynamic net trees, which requires the net-tree representation to contain no deleted points and therefore allows applications to operate only on active points. 

Our preliminary results show that we can maintain a collection of a constant number of net trees, where the collection satisfies the shifting property, and each tree simultaneously maintains the packing, covering, and freshness properties with $O(\log n)$ update time. We then examine how freshness and shifting properties enable locality and tractability in dynamic applications of doubling metrics.

In this proposal, we investigate these properties in two challenging dynamic applications: consistent $k$-center clustering and light spanners in doubling metrics. Known algorithms for $(2+\varepsilon)$-approximate $k$-center in doubling metrics require $O(\log\Delta\log\log\Delta)$ time per update and recompute the entire set of $k$ centers for every query, where $\Delta$ is the spread of the metric. Existing dynamic constructions for $(1+\varepsilon)$-spanner of constant lightness have $O(\log\Delta)$ recourse and require $\textrm{polylog}\Delta$ time per update. These results raise the question of whether the shifting and freshness properties can yield both locality and tractability for these applications. In particular: 

1. Can we maintain a $(2+\varepsilon)$-approximate $k$-center solution with constant recourse? Can we identify and return these changes within $O(\log n)$ time per update? 
2. Can we maintain a dynamic $(1+\varepsilon)$-spanner with constant lightness and recourse? Can we update the light spanner in $O(\log n)$ time?

Advisor:

Hung Le