| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 11, 2014 |
| Latest Amendment Date: | June 11, 2014 |
| Award Number: | 1421231 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Joseph Maurice Rojas
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2014 |
| End Date: | August 31, 2019 (Estimated) |
| Total Intended Award Amount: | $490,364.00 |
| Total Awarded Amount to Date: | $490,364.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
506 S WRIGHT ST URBANA IL US 61801-3620 (217)333-2187 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
1901 S. First Street Champaign IL US 61820-7406 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| 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
New (and not so new) technologies like GPS, LIDAR, smart-phones and apps are now used to collect vast amounts of geometric and geographic data. In many such cases the data is too large to be handled by a single computer, and it needs to be broken up into small chunks, so that it can be handled by a cluster/cloud of computers. This award funds research to develop efficient algorithms for manipulating and summarizing such data. In particular, this award concentrates on the issue of how to partition such data efficiently in a balanced way, so that it can be efficiently processed.
The algorithms and insights obtained from the technical work will benefit Computer Science and related disciplines where geometric data and algorithms are widely used. The PI hopes to broaden the scope of Computer Science (and Computational Geometry) by introducing new techniques, that would lead to faster and better algorithms, and potentially new applications of geometric data.
The project will support and train at least two new PhD students in Computer Science at UIUC. The PI is committed to popularizing ideas and techniques that would be investigated by this proposal, by giving courses, publishing the research, potentially writing a new book on the topic, and use less convectional new tools to disseminate the research using blogs, social media, and online videos.
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.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This research project studied problems related to how to partition geometric data, and summarizing it. Such tasks are fundamental tasks in real world applications, ranging from web search, machine learning, data-mining and others. They are of special importance when handling big data.
We developed new algorithms addressing issues such as (i) how to partition graphs that rises out of geometric data, (ii) how to find sparse representation of data, (iii) how to separate data using as few features as possible, (iv) how to perform certain geometric tasks using little space (important in handling big data), and (v) others.
This project had resulted in a significant progress of the state of the art algorithms for geometric problems using divide and conquer techniques. Highlights of this project includes: (i) the development of separators for low density graphs, and (ii) progress on computing sparse approximation of data in high dimensions.
Maybe the highlight of this project is a new technique, called locality sensitive orderings, which dramatically simplifies several geometric algorithms. We believe this technique has the potential to have a large impact in the long run.
Several graduate students were trained as part of this grant, one of them currently hold a faculty position in a US university. Another postdoc is currently holding a faculty in a university. The research done for this project resulted in the publication of 20 papers in prestigious conferences and journals.
Last Modified: 11/02/2019
Modified by: Sariel Har-Peled
Please report errors in award information by writing to: awardsearch@nsf.gov.
