The area of sublinear algorithms aims to establish algorithmic foundations for processing big data. Sublinear algorithms produce quick, approximate answers after examining only a tiny fraction of their input. This project focuses specifically on sublinear algorithms for visual and geometric data, with the goal of laying foundations for studying such data in the sublinear context. This requires the development of new tools and will open up new connections as well as new areas of applications. Effectively exploiting big data can provide significant societal benefits. The research pursued by this project contributes the theoretical foundations necessary to take advantage of big data. It has the potential to change how visual data is processed and analyzed. The results of this research will be integrated into the investigator's graduate course on sublinear algorithms.
The primary goal of this project is a systematic investigation of visual data in the sublinear context. Whereas there are established and successful lines of research in sublinear algorithms and property testing on functions, codes (and, more generally, algebraic properties), graphs, and discrete distributions, several potential applications of sublinear algorithms require working with visual and geometric data. Specifically, sublinear algorithms that can test basic visual properties, such as symmetry, convexity, and low genus have the potential to dramatically speed up image processing applications. Some of these properties have not been studied at all in the context of sublinear algorithms. This project investigates fundamental problems in testing visual properties, considers problems in higher dimensions, and studies new computational tasks with a focus on robustness. To achieve their full potential, sublinear algorithms need to be able to handle geometric and visual data.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
