Show simple item record

dc.contributorAtri Rudraen_US
dc.contributorBalasubramanian Kalyanasundaram Program Manageren_US
dc.contributor.authorHung Ngo Principal Investigatoren_US
dc.datestart 09/01/2013en_US
dc.dateexpiration 08/31/2016en_US
dc.date.accessioned2014-04-02T18:25:17Z
dc.date.available2014-04-02T18:25:17Z
dc.date.issued2014-04-02
dc.identifier1319402en_US
dc.identifier.urihttp://hdl.handle.net/10477/23671
dc.descriptionGrant Amount: $ 326101en_US
dc.description.abstractThe relational join is central to relational database processing, which is the dominant way data is processed today. The join also models problems in biological and social networks, coding theory, compressed sensing, machine learning, and constraint satisfaction. Recently,  the investigators described the first ever worst-case optimal algorithm (the NPRR algorithm) for join queries.  These new results open a line of new tools to attack a diverse set of fundamental problems related to the join. This project aims to further exploit the new algorithmic techniques developed for NPRR to address the following three classes of problems:<br/><br/>(1) Optimal Join algorithms. Developing algorithms that are instance optimal when the data are stored in either traditional database indexes or new indexing structures is a goal of this project. (2) Coping with and Leveraging Noise. This project will extend the latest work to handle and leverage both worst-case and statistical noise models, bridging to coding theory and compressed sensing.  (3) Expressive Query Languages. The project will explore a series of extensions to join queries that will pave the way to overcome challenges in motif finding, search, databases with functional dependencies, and more powerful classes of queries and join operations.<br/><br/>If successful, the results of this grant will apply to a variety of pattern extraction problems in modern massive, dynamic, and noisy data sets, which have a wide range of applications in complex network analysis, coding theory, and compressive sensing.en_US
dc.titleAF:III:Small:Collaborative Research: New Frontiers in Join Algorithms: Optimality, Noise, and Richer Languagesen_US
dc.typeNSF Granten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record