UC Irvine

As modern systems grapple with massive amounts of data, traditional algorithms requiring polynomial or even linear time and space have become prohibitively expensive for some critical applications. Examples include document deduplication, link prediction, and data analytics. This has motivated research into approximation algorithms characterized by a sub-linear time or space complexity. This dissertations covers approximation algorithms, particularly those leveraging sketching and dimensionality reduction, that trade a marginal loss in precision for substantial gains in efficiency. These algorithms have formal bounds on their error and success probability, and often achieve an optimal tradeoff between accuracy and cost. Collectively, these insights provide a robust framework for the design of algorithms in the big data era. Chapter 2 covers approximation algorithms for set similarity metrics. Set similarity metrics are a core aspect of several data mining tasks. To remove duplicate results in a Web search, for example, a common approach looks at the Jaccard index between all pairs of pages. In social network analysis, a much-celebrated metric is the Adamic-Adar index, widely used to compare node neighborhood sets in the important problem of predicting links. However, with the increasing amount of data to be processed, calculating the exact similarity between all pairs can be intractable. The challenge of working at this scale has motivated research into efficient estimators for set similarity metrics. The two most popular estimators, MinHash and SimHash, are indeed used in applications such as document deduplication and recommender systems where large volumes of data need to be processed. Chapter 2 describes a novel method, called DotHash, which is an unbiased estimator for the weighted intersection size of two sets. DotHash can be used to estimate the Jaccard index and is the first method that can also estimate the Adamic-Adar index and a family of related metrics. This family of metrics is formally defined, theoretical bounds on the probability of estimate errors are provided, and its empirical performance is analyzed. The empirical results indicate that DotHash is more accurate than the other estimators in link prediction and detecting duplicate documents with the same complexity and similar comparison time. Chapter 3 covers approximation algorithms in the streaming data setting. With the increasing rate of data generated by critical systems, estimating functions on streaming data has become essential. This demand has driven numerous advancements in algorithms designed to efficiently query and analyze one or more data streams while operating under memory constraints. The primary challenge arises from the rapid influx of new items, requiring algorithms that enable efficient incremental processing of streams in order to keep up. A prominent algorithm in this domain is the AMS sketch. Originally developed to estimate the second frequency moment of a data stream, it can also estimate the join size of the equi-join between two relations. Since then, two important advancements are the count sketch, a method which significantly improves upon the sketch update time, and secondly, an extension of the AMS sketch to accommodate multi-join queries. However, combining the strengths of these methods to maintain sketches for multi-join queries while ensuring fast update times is a non-trivial task, and has remained an open problem for decades. Chapter 3 describes the UCI sketch, a novel sketching method that successfully addresses this problem and has fast updates, even for sketches capable of accurately estimating the join size of complex multi-join queries. The estimator is unbiased and has the same error guarantees as the AMS-based method. Empirical results confirm the significant improvement in update time complexity, resulting in orders of magnitude faster estimates, with equal or better estimation accuracy. Chapter 4 generalizes and improves upon the results from Chapter 3. Specifically, Chapter 4 shows that join size estimation is equivalent to approximating a tensor network contraction, which is a fundamental mathematical operation that generalizes the dot product and matrix multiplication. It finds applications in numerous domains besides database systems, such as graph theory, machine learning, probability theory, and quantum mechanics. Tensor network contractions are computationally expensive, in general requiring exponential time and space. The prior sketching methods for tensor network contraction, however, only support acyclic tensor networks. Chapter 4 describes the first method capable of approximating arbitrary tensor network contractions, including those of cyclic tensor networks. Additionally, the prior sketching methods require a computational complexity that grows exponentially with the number of contractions. Chapter 4 describes a second method, for acyclic tensor networks, whose space and time complexity depends only polynomially on the number of contractions.