EAGER:CCF:AF:Sublinear Data Structures for Approximate Queries

Louisiana State University, Baton Rouge LA

Investigators

Abstract

Computer science is a fast growing field which has opened up new possibilities with more and more availability of data and novel applications. Efficiency in computing becomes an important issue not only due to speed and hardware requirements but also because computers consume a significant chunk of world’s energy resources. The main challenge is to efficiently store, organize and manage data so that one can retrieve and infer intelligent information from the data in real time. In modern applications, data lies in the cloud, and to answer queries on the data one makes data structural index – which resides locally or in fast memory. This project considers design and development of sublinear data structures which will enable answering of queries on massive data sets. These data structures will serve as building blocks for fields like databases, information retrieval, bioinformatics and geographic information systems. Data structures being a core course in all computer science curricula, the outcomes of this project will be enrich the course on data structures that the investigator teaches at LSU. Many of the results worked out here could become interesting implementation and algorithmic experimentation projects for the students taking the course. LSU Computer Science has high percentage of minority students who will benefit from this exposure. The investigator plans to continue high school and middle school outreach activities. Main goal in the field of succinct data structures is to design a data structure which takes the space equivalent to information theoretic minimum space required to represent the data and execute queries in polylogarithmic time. By separating the space for raw data and the space for indexing, this project explores the relationship between the space required for the indexing part and query type. The project will further explores if the space can be reduced by allowing the query answers to be approximate. The investigator will be considering fundamental queries like range-topk, range mode, and range quantiles along with different notions of approximations like approximate values, approximate ranks, approximate range boundaries and allowing additive errors in approximations. The main goal is to achieve meaningful sublinear indexes for an overarching range of problems and queries for which allow sublinear bounds. The investigator's attempt will be to categorize fundamental problems along with their upper and lower bounds. The project will identify meaningful models and fundamental problems which can be further used as primitives for wider range of problems. 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.