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

计算机科学是一个快速发展的领域，随着越来越多的数据可用性和新颖的应用，它开辟了新的可能性。计算效率之所以成为一个重要问题，不仅是因为速度和硬件要求，还因为计算机消耗了世界上很大一部分能源资源。主要的挑战是有效地存储、组织和管理数据，以便人们可以实时地从数据中检索和推断智能信息。在现代应用程序中，数据位于云中，为了回答对数据的查询，人们创建数据结构索引——它驻留在本地或快速内存中。该项目考虑设计和开发亚线性数据结构，这将能够回答大量数据集上的查询。这些数据结构将作为数据库、信息检索、生物信息学和地理信息系统等领域的基石。数据结构是所有计算机科学课程的核心课程，该项目的成果将丰富研究者在LSU教授的数据结构课程。这里得出的许多结果对于参加课程的学生来说可能会成为有趣的实现和算法实验项目。路易斯安那州立大学计算机科学专业的少数族裔学生比例很高，他们将从这种接触中受益。调查员计划继续在高中和初中开展外展活动。简洁数据结构领域的主要目标是设计一种数据结构，该数据结构占用的空间相当于信息理论的最小空间，可以在多对数时间内表示数据并执行查询。通过分离原始数据空间和索引空间，本项目探索了索引部分所需空间与查询类型之间的关系。该项目将进一步探索是否可以通过允许查询答案近似来减少空间。研究者将考虑基本查询，如范围topk，范围模式和范围分位数，以及近似的不同概念，如近似值，近似秩，近似范围边界和允许近似值中的附加误差。主要目标是为一系列允许次线性边界的问题和查询实现有意义的次线性索引。研究者的尝试将是对基本问题及其上限和下限进行分类。该项目将确定有意义的模型和基本问题，这些模型和基本问题可以进一步用作更广泛问题的原语。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.