| NSF Org: |
IIS Division of Information & Intelligent Systems |
| Recipient: |
|
| Initial Amendment Date: | September 11, 2009 |
| Latest Amendment Date: | September 11, 2009 |
| Award Number: | 0916565 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Frank Olken
IIS Division of Information & Intelligent Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2009 |
| End Date: | August 31, 2013 (Estimated) |
| Total Intended Award Amount: | $336,456.00 |
| Total Awarded Amount to Date: | $336,456.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
7 LEBANON ST HANOVER NH US 03755-2170 (603)646-3007 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
7 LEBANON ST HANOVER NH US 03755-2170 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
DATA-INTENSIVE COMPUTING, COMPLEXITY & CRYPTOGRAPHY |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
The modern, highly digitized world is replete with human activities that generate copious streams of data on a seemingly-continuous basis. There is knowledge to be gained by suitably analyzing, mining and monitoring the wealth of information in these data streams. However, due to the sheer scale of the data involved, traditional algorithmic thinking is inadequate and one needs data streaming algorithms that can process inputs memory-efficiently in one, or a few, scanning passes, ideally operating in sync with data generation.
The area of data streaming algorithms, though dating back to about 1980, has truly come alive only in the last decade or so, with a wealth of algorithms having been developed for, e.g., various statistical analyses, geometric problems and graph-theoretic problems. An area rich with algorithmic ideas deserves sound theoretical underpinnings. Accordingly, this project shall investigate a number of fundamental questions in this area, focusing on the delineation of what can and cannot be achieved in this important computational model. By investigating foundational questions, rather than focusing too much on particular applications, the project's approach shall be that of algorithms-and-complexity theory.
Some representative research goals of this project are as follows. (1) Refining our understanding of the space complexity of various statistical measures, especially in the multi-pass setting. (2) Understanding the power of randomness in order-dependent streaming problems. (3) Proving lower bounds in stronger variants (extensions) of the basic stream model. (4) Attacking fundamental questions in communication complexity that lie at the heart of current open questions in data stream complexity.
Results obtained in the course of the project will be disseminated at international conferences, workshops and seminars at various institutions. The project's educational component shall consist of the development of a graduate-level course on data stream algorithms, covering the basics of the field and leading up to the most significant recent discoveries.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
Please report errors in award information by writing to: awardsearch@nsf.gov.
