%======================================================================
\chapter{Introduction}
\label{chapter-intro}
%======================================================================
The design of efficient data structures is a classic topic within the field of theoretical computer science. Efficient data structures are fundamental to efficient algorithms, but also frequently find use in applications directly, such as in database systems. Most programming language standard libraries contain implementations of basic data structures, and frequently in production code, these libraries see extensive use. In performance-critical applications, even very minor improvements in data structure efficiency can lead to very important performance gains. For these reasons, the design of efficient data structures is uniquely important to the theory and practice of computing systems.

This thesis focuses on the study of data structures from the perspective of the theoretician. By studying data structures with worst-case guarantees, fundamental mathematical properties can be discovered. In many circumstances, these theoretically superior data structures can lead to improved practical implementations.% Further attention to practical detail is considered when relevant.
%In the cases when such practical improvements may not be implied, the matter is discussed and attention to the particular details of the practical situation are considered. In one chapter (Chapter~\ref{chapter-dynamicmodetime}), a result is discussed with purely theoretical significance. Such results are interesting because of what they may imply about the theoretical hardness of problems and because they may lead to future algorithms with greater practical relevance.

Data structures are evaluated on three metrics:
\begin{enumerate}
	\item The time complexity of the supported operations.
	\item The space complexity of the data structure.
	\item The time it takes to construct the data structure.
\end{enumerate}
This thesis will consider all three metrics. The greatest attention will be given to time complexity of supported operations. In chapters \ref{chapter-lattices}, \ref{chapter-dynamicmodespace}, and \ref{chapter-succinctmode}, the space complexity will be equally important. %In Chapter~\ref{chapter-succinctmode}, the data structure is given in an encoding model, where space costs are measured in bits, with the goal of providing a data structure that uses space close to the information-theoretic minimum.
Construction costs are analyzed in chapters~\ref{chapter-lattices}, \ref{chapter-lazysearchtrees}, and \ref{chapter-dynamicmodespace}.

Algorithms relating to data structures are also considered. In Chapter~\ref{chapter-offlineconnectivity}, an \emph{offline} data structure is given. This data structure assumes access to the entire operation sequence in advance. In Chapter~\ref{chapter-mincut}, an algorithm is given based on data structure concepts, which further abstracts necessary computation onto another data structure.

The topics discussed fall into three main categories: partial order data structures (Part~\ref{part-partialorder}), range mode data structures (Part~\ref{part-rangemode}), and graph and dynamic graph algorithms (Part~\ref{part-graph}). While the topics discussed have relatively minor overlap, the technical intuition as well as guiding principles are shared.

In general, the solutions developed value simplicity over theoretical efficiency. Most of the main ideas of this thesis can be explained at an undergraduate computer science level. Further attention is given to practicality. This affects both the algorithms developed as well as the problems considered. The problems considered are some of the most natural: representing unknown total orders, computing modes, and computing minimum cuts. The less constrained the problem, the more likely it is to be of relevance.

With regards to computation model, we use both the word RAM and the pointer machine, depending on the chapter. In the word RAM, we can compute bitwise operations on $\Theta(\log n)$-bit words in $O(1)$ time (in this thesis we will always assume a word to be $\Theta(\log n)$ bits) and have random access to memory in constant time. In the pointer machine, we lose array access, instead representing data as a node with a constant number of pointers that can be followed in constant time. In general we assume arithmetic and other reasonable functions are computable in $O(1)$ time. We use the full power of the word RAM typically only indirectly, in succinct data structures in Chapter~\ref{chapter-succinctmode} and van Emde Boas trees~\cite{Boas77} in Chapter~\ref{chapter-dynamicmodespace}. In particular, we do not make use of bit tricks to shave off partial logarithmic or doubly logarithmic factors. We do this to maintain relative practicality. The black-box data structures that do use such tricks can be substituted, if desired, with slower comparison-based data structures on the pointer machine. When the word RAM is used, most of our results give polynomial $\Omega(n^c)$ for $0 < c < 1$ improvements which are not affected by the power of word RAM, which can give at most a $\Theta(\log n)$ speedup.

We discuss the specific contents of this thesis in the following three sections.

%For these reasons, the design of efficient data structures is uniquely important to the theory and practice of computing systems. This thesis is dedicated to its study, in three relevant subareas. Before we discuss them, however, we must address how we will compare related data structures.

%While data structures can be evaluated on many metrics, perhaps the most commonly-used is the standard big O notation over worst-case operation sequences. Doing so allows direct comparison of data structure implementations on a mathematically fundamental level. While constant factors are critical to the practitioner, when complexities of operations indicate growth at substantially different rates, a larger complexity will always indicate a slower algorithm on a suitably large input. Similarly, assuming a worst-case input sequence allows the performance claims to give meaningful runtime guarantees.

%Of course, theory is not practice, and theoretical performance guarantees may not indicate a more efficient algorithm. In particular, in the land of data structures, $O(\log n)$ is unlikely to exceed about $30$ 





%data structures make up more 


%showing that the study of data structures can have important tangible practical implications. For these reasons, data structure design is among the most important pursuits in computer science.

%Data structures are typically evaluated on three metrics: operation times, space complexity, and construction costs. In many domains, 


%data structures that support fast queries, small space complexities, and efficient preprocessing costs are imperative to 





%This thesis is focused on the design of efficient data structures for 

\section{Partial Order Data Structures}

The representation of partial orders is at the heart of data structure design. Binary search trees, perhaps the most fundamental data structure in computer science, represent an initially unknown total order. Directed acyclic graphs can be interpreted as representations of partial orders by their reachability relations. In algebra, we can create partial orders on common sets such as the integers, by considering divisibility relations, or subsets of a universe, ordering by inclusion. We consider data structures to represent unknown total orders in Chapter~\ref{chapter-lazysearchtrees} and data structures to represent lattices, such as those just mentioned, in Chapter~\ref{chapter-lattices}.

\subsection{Lattice Data Structures}

We first consider data structures to represent a specific type of partial order known as a lattice. A lattice is a partial order such that for every pair of elements $x$ and $y$, the set of elements greater than both $x$ and $y$ are all greater than (or equal to) a unique element $x \join y$, known as the \emph{join} of $x$ and $y$. Similarly, the set of elements less than both $x$ and $y$ are all less than (or equal to) a unique element $x \meet y$, known as the \emph{meet} of $x$ and $y$. Lattices arise in many areas of mathematics, the social sciences, and programming languages~\cite{Gra16,Wil82,Gan05,Mon03,Nie15,ABLN89, Cas93, Cas99, Kra97}. The integers, ordered by divisibility, are a lattice, as are a collection of subsets closed under intersection and union, ordered by inclusion.

The lattice problem asks to create a data structure to represent lattices that can efficiently determine if an order relation exists between two elements $x$ and $y$ and to compute the meet and join of $x$ and $y$. The goal is to use as little space as possible.

Initial work in lattice data structures was heuristic~\cite{ABLN89}. The problem was then studied theoretically by Talamo and Vocca in a series of papers in the 90's~\cite{TV94,TV97,TV99}. Unfortunately, the data structures proposed by Talamo and Vocca have a fundamental error that appears irreparable. We study the issue with their work and present a data structure that takes $O(n \sqrt{n})$ words of space ($O(n \sqrt{n} \log n)$ bits), computes order relations in $O(1)$ time, and computes meets and joins in $O(n^{3/4})$ time. Here we assume a word RAM, where our use of this model is only to get $O(1)$ time dictionary lookup. We also give time-space tradeoffs, construction costs, and a data structure with complexity characterized by a concept of degree on a minimal graph representation of the partial order. This is discussed in Chapter~\ref{chapter-lattices}.

\subsection{Lazy Search Trees}

Binary search trees are perhaps the most fundamental data structure in computer science. Research on binary search trees (BSTs) has primarily focused on developing BSTs with efficient \emph{access} times. Specifically, dynamic optimality research looks for a BST that performs any access sequence in time within a constant factor of the offline-optimal BST. Although $\Omega(\log n)$ is the worst-case time complexity of a single access, on an operation sequence such as repeatedly accessing a single element, binary search trees can perform this sequence in about $O(1)$ time per access by storing said element at or near the root. This subarea has received vast attention~\cite{Allen78,Demaine09,Demaine07,Iacono16,Bose2020,Sleator83,Wilber89,Kozma2019,Chalermsook15,Iacono01,Badoiu06}.

Instead of focusing on efficient access times when possible, lazy search trees consider the problem of achieving efficient \emph{insertion} times when the operation sequence permits such efficiency.
%Lazy search trees focus on a different question: how can we support the operations of a BST while achieving efficient \emph{insert} times?
The main insight is that priority queues have been developed with $O(1)$ time insertion and decrease-key operations~\cite{Fredman87,Fredman86,Chan09,Brodal12,Elmasry09,Haeupler11,Brodal96,Hansen15}; thus, on certain operation sequences (like when we only query for the minimum element), it is possible to support insertion in $o(\log n)$ time. Despite the plethora of research on BSTs with efficient access times, our work is the first to ask whether a data structure supporting the operations of a BST can achieve efficient insertion time. Our data structure is not a binary search tree, however. In order to avoid $\Omega(\log n)$ insert time, we delay sorting of inserted elements, employing structures similar to those used in priority queue literature, operating over a pointer machine. We don't see this as a disadvantage; the goal of the algorithm designer is to solve \emph{problems} efficiently; in this case we observe that constraining to a model of binary search trees is an arbitrary limitation to the most efficient solutions.

We analyze the performance of our data structure based on a partition of current elements into a set of \emph{gaps} $\{\Delta_i\}$ based on rank. A query falls into a particular gap and $\emph{splits}$ the gap into two new gaps at a rank $r$ associated with the query operation (BST queries such as rank, select, membership, predecessor, successor, minimum, and maximum are supported). If we define $B = \sum_i |\Delta_i| \log_2(n/|\Delta_i|)$, our performance over a sequence of $n$ insertions and $q$ distinct queries is $O(B + \min(n \log \log n, n \log q))$. We show $B$ is a lower bound.

The bound $B$ satisfies $B = O(n \log q)$; when queries are non-uniform, better bounds are possible. In the priority queue case, our data structure achieves $O(\log \log n)$ time insertion and decrease-key operations, thus interpolating between binary search trees and priority queues. We show that we can achieve this while simultaneously achieving the desirable efficient access properties that have been studied in dynamic optimality literature. We discuss precise performance guarantees and other useful properties of lazy search trees in Chapter~\ref{chapter-lazysearchtrees}.

%The exact performance of our data structure is not easily stated. However, we adapt the rank-based bound $B$ used in multiple selection literature~\cite{Dobkin81,KMMS} to a dynamic model. We achieve $O(B + n \log \log n)$ combined insertion and query complexity. Over a sequence of $n$ insertions and $q$ queries, a bound $O(n \log q + q \log n)$ holds. When queries are non-uniform, better bounds are possible. In the priority queue case, our data structure achieves $O(\log \log n)$ time insertion and decrease-key operations, thus interpolating between binary search trees and priority queues. We show that we can achieve this while simultaneously achieving the desirable efficient access properties that have been studied in dynamic optimality literature. We discuss precise performance guarantees and other useful properties of lazy search trees in Chapter~\ref{chapter-lazysearchtrees}.

\section{Range Mode}

In the range mode problem, we are given a sequence of elements and must answer queries that request the most frequent element in a contiguous subsequence. If the problem is dynamic, we must also support insertion and deletion of elements in the sequence.

The mode is one of the three fundamental data statistics, along with median and mean, and range mode is one of few basic range problems that have not been solved optimally. Indeed, upper bounds remain quite large: linear space static range mode requires time about $O(\sqrt{n})$ per query and dynamic range mode about $O(n^{2/3})$ per operation~\cite{C14}, compared to range problems such as sum, minimum, median, or majority, which permit logarithmic time static solutions and polylogarithmic time or better dynamic solutions, even when space is restricted to $O(n)$ words~\cite{GBT84,Brodal11,elm11,mih10,chan17,HMN11,gag17,elm11}.

We consider a dynamic range mode data structure that slightly improves operation time while simultaneously improving space usage in Chapter~\ref{chapter-dynamicmodespace}. In Chapter~\ref{chapter-dynamicmodetime}, we break the $O(n^{2/3})$ time per operation barrier for dynamic range mode. In Chapter~\ref{chapter-succinctmode}, we consider succinct data structures for approximate static range mode, approximate dynamic range mode, and approximate static range selection. All data structures in this part of the thesis operate on the word RAM. In Chapter~\ref{chapter-dynamicmodespace}, we use only standard operations with constant time array access as well as more powerful blackbox word RAM data structures non-central to our results. In Chapter~\ref{chapter-dynamicmodetime} we measure performance ignoring logarithmic factors, so this distinction is not important. Chapter~\ref{chapter-succinctmode} requires the word RAM model more centrally.

\subsection{Space-Efficient Dynamic Range Mode}

The first dynamic range mode data structure was proposed by Chan et al.~\cite{C14} and operated on a time-space continuum, achieving $O(n^{3/4} \log n / \log \log n)$ worst-case time query and $O(n^{3/4} \log \log n)$ amortized expected time update at $O(n)$ words of space and $O(n^{2/3} \log n / \log \log n)$ worst-case time query and amortized expected time update at $O(n^{4/3})$ words of space.

We improve both operation time and space usage by providing a data structure with $O(n^{2/3})$ worst-case time query and update while occupying $O(n)$ words of space. Our data structure can also be generalized to find the least frequent element in a range or an element of a particular frequency, with some restrictions. We discuss these data structures in Chapter~\ref{chapter-dynamicmodespace}.

\subsection{Faster Dynamic Range Mode}

Several different approaches can achieve a dynamic range mode data structure with $\tilde{O}(n^{2/3})$ time operations, where the $\tilde{O}(\cdot)$ notation hides logarithmic factors. A conditional lower bound from the online matrix-vector multiplication problem~\cite{Henzinger15} states that a dynamic range mode data structure taking $O(n^{1/2-\epsilon})$ time per operation for $\epsilon > 0$ is not possible with current knowledge~\cite{C14}. This leaves a gap of about $\Theta(n^{1/6})$ between the lower and upper bound.

We tighten this gap and break the $O(n^{2/3})$ time per operation barrier by presenting a data structure with per-operation complexity of about $\tilde{O}(n^{.656})$. Our result reduces to a Min-Plus product, which in turn reduces to fast matrix multiplication. We discuss this work in Chapter~\ref{chapter-dynamicmodetime}.

\subsection{Approximate Succinct Range Mode and Range Selection}

For any $\eps \in (0,1)$, fixed at construction time, a $(1+\eps)$-approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor $(1+\eps)$ smaller than the true mode. The best static approximate range mode data structure prior to our work was a result by Greve et al.~\cite{GJLT10} which achieves $O(\log(1/\epsilon))$ query time while using $O(n/\eps)$ words of space. We improve this result by moving to a succinct encoding model, where we build the data structure off the input, then require only the data structure to answer queries. Our data structure achieves $O(\log(1/\epsilon))$ query time while using only $O(n/\eps)$ \emph{bits} of space, which is a $\Theta(\log n)$ factor reduction in space usage.

We also consider dynamic approximate range mode. Our data structure is the first dynamic approximate range mode data structure. For any fixed constant $\eps$, it achieves $O(\log n/\log \log n)$ query time, $O(\log n)$ update time, and occupies $O(n)$ words of space. Finally, we consider approximate range selection. We discuss these results in Chapter~\ref{chapter-succinctmode}.

\section{Graph and Dynamic Graph Algorithms}

The final part of this thesis is dedicated to graph and dynamic graph algorithms. There has been a large amount of recent work on data structures to compute queries in dynamic graphs, particularly connectivity queries~\cite{Eppstein94,Eppstein97,Eppstein06,KKM13,HolmLT98,HRT18,Huang17,KaczmarzL15,LackiS13,Thorup00,Wulff-Nilsen17}. Connectivity has been studied both because it is fundamental and simple, with the latter property permitting efficient dynamic solutions. Connectivity can be extended to $c$-edge connectivity, which queries the existence of $c$ edge-disjoint paths between two vertices of a graph, or $c$-vertex connectivity, which queries the existence of $c$ vertex-disjoint paths. Algorithms and data structures for these higher versions of connectivity are related to the notion of a \emph{graph cut}, which is a set of edges or vertices whose removal disconnects a graph. Graph cuts are fundamental to the minimum cut problem, to which an algorithm we originally devised for a dynamic graph data structure provides a simpler near-linear time weighted minimum cut algorithm. We study an offline dynamic data structure for $c \leq 3$ edge and vertex connectivity in Chapter~\ref{chapter-offlineconnectivity} and a simpler algorithm for the minimum cut problem in Chapter~\ref{chapter-mincut}.

\subsection{Offline Dynamic Higher Connectivity}

Consider the problem of answering $2$- and $3$-edge and vertex connectivity queries in a graph undergoing edge insertion and deletion. In the typical data structure model, a query must be answered before the next operation is given. In this setting, known as the \emph{online} model, data structures for $3$-edge and $3$-vertex connectivity require $O(n^{2/3})$ and $O(n)$ time per update, respectively~\cite{Eppstein97}. Consider, however, a situation where the complete sequence of updates and queries is known in advance. This may happen directly, when data about a dynamic network is collected but not analyzed until a later point in time, or indirectly, if the algorithm is used as a subroutine of a different algorithm. In this setting, known as the \emph{offline} setting, simpler and more efficient algorithms are possible. We give such an offline data structure for $2,3$-edge/vertex connectivity that takes $O(\log n)$ time per operation, which is optimal due to the dynamic connectivity lower bound of Patrascu and Demaine~\cite{DemaineP04}. We discuss this in Chapter~\ref{chapter-offlineconnectivity}.

\subsection{Minimum Cuts}

The weighted minimum cut problem on an undirected graph $G$ asks to partition the vertices of $G$ into two sets such that the total weight of edges crossing the partition is minimized. This problem is fundamental in graph optimization and has seen vast attention~\cite{Karger00,Gabow91,Plotkin92,Karger93a,Karger96,GoranciHT16,Thorup07,Junger00,Chekuri97,Henzinger18,Chalermsook04,Karger99,Geissmann18,Kawarabayashi19,Henzinger17,Daga19,Geissmann17,Nanongkai14,Stoer97,Ghaffari13}.

At the time of our first study of the problem, the state-of-the-art weighted minimum cut algorithm was a result of Karger which finds a minimum cut on a graph with $n$ vertices and $m$ edges in $O(m \log^3 n)$ time~\cite{Karger00}. Karger's algorithm leverages random sampling and tree packing to reduce the problem to finding a minimum cut that cuts at most two edges of a spanning tree $T$ of a graph $G$. Karger then employs a complicated dynamic program which solves the reduced problem in $O(m \log^2 n)$ time.

We observed that a routine we originally devised for dynamic graph data structures simplified Karger's dynamic program to a straightforward edge iteration utilizing heavy-light decomposition~\cite{Sleator83}. With the use of a top tree~\cite{AlstrupHLT2005}, we achieve $O(m \log^2 n)$ complexity on the subroutine, matching Karger's approach. If we want to avoid the use of advanced data structures, heavy-light decomposition can be used a second time with a standard augmented binary search tree to achieve $O(m \log^3 n)$ time complexity. We further condense Karger's algorithm to a self-contained version and implement it. We discuss this in Chapter~\ref{chapter-mincut}.