Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"Sublinear-time algorithms"”.
-
Improved algorithms and new models in property testing
We study sublinear-time algorithms for testing fundamental properties of functions and graphs. Sublinear-time algorithms run in time sublinear in the input size and are especially useful for processing massive datasets. We investigate variants of the property testing model, which was introduced by …
-
Modern Large-Scale Algorithms for Classical Graph Problems
… inherently different from those of traditional algorithms. For instance, without having the whole input properly stored in the memory of a single machine, it is unrealistic to assume that any arbitrary location of the input can be accessed at the same cost; an assumption that is essential for …
-
Analyzing massive datasets with missing entries: models and algorithms
… study of computational models to analyze algorithms for massive datasets with missing or erased entries and study the relationship of our models with existing algorithmic models for large datasets. We focus on algorithms whose inputs are naturally represented as functions, codewords, or …
-
Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation
… constraints. As these datasets grow, traditional algorithms that assume random access to the input become increasingly infeasible. This thesis explores how to process massive graphs efficiently under modern models of computation that address these limitations. The primary focus is on the streaming …
-
Logical methods for property testing in the bounded degree model
Property testers are randomised sublinear time algorithms which infer global structure from a local view of an input. In the context of bounded degree graphs, testability of a property is tightly linked to the question of whether an approximate distribution of r-neighbourhood types of a graph is …
-
Sublinear Time Evaluation of Logically Defined Queries on Databases of Bounded Degree
… is an ever-growing need for extremely efficient algorithms to extract information from data. However, when the input data is huge, even reading the whole input once is too costly and hence many algorithms that are traditionally classified as 'efficient' (i.e. run in polynomial time) become …