Sublinear Property Testing of Large Collections of Data Objects

Case Western Reserve University, Cleveland OH

Investigators

Abstract

With increasing data processing needs, many applications belonging to areas such as communication networks, computational biology, e-commerce, etc. require the processing of very large data sets under time and space limitations. This need makes it necessary to seek new, more efficient algorithmic models involving resource restrictions. The main objective of this project is to explore the tradeoffs between limiting the computing resources (time, space, access to input) available to an algorithm and the resulting loss in accuracy and effectiveness. By testing quantitative properties as well as qualitative ones, the link between the efficiency/effectiveness of property testing and those of approximation algorithms can be investigated. To this end, this project involves devising sublinear algorithms for checking combinatorial properties of various types of large data objects such as sequences, graphs, and sets. This task can be achieved through intelligent random sampling of the data, minimizing the number of bits of the input that the algorithm needs to access through either reusing samples or choosing samples carefully so that each accessed bit yields as much information as possible about the input. The broader impact of this project is in improving the understanding of resource-bounded computation on different types of large data. The new meta-techniques developed are expected to apply to a variety of problems in different application areas which now see the processing of input as a major bottleneck. For students of computer science, these techniques bring a new point of view to understanding the possibilities and limitations of computation as well as an understanding of data-related limitations and bottlenecks of certain types of applications that need to be addressed via unconventional models.