权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

EAGER:CCF:AF:用于近似查询的次线性数据结构

基本信息

批准号：
2137057
负责人：
Rahul Shah
金额：
$ 22.58万
依托单位：
Louisiana State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2137057&HistoricalAwards=false
关键词：
EAGER CCF AF Sublinear Data

项目摘要

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.

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