| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 6, 2012 |
| Latest Amendment Date: | June 6, 2012 |
| Award Number: | 1217462 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Rahul Shah
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2012 |
| End Date: | August 31, 2017 (Estimated) |
| Total Intended Award Amount: | $489,194.00 |
| Total Awarded Amount to Date: | $489,194.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: |
201 N. Goodwin Avenue Urbana IL US 61801-2302 |
| 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
This award funds research to develop faster and better algorithms for handling data, and specifically geometric data. With the massive amount of data in the world nowadays, standard algorithms fall short. The PI and his students investigate ways to improve geometric search for nearest neighbor, clustering, data-compression, and similarity search between curves, especially for massive amount of data. Such algorithms are widely used in the real world to handle navigation tasks, pattern recognition, signature identification, etc.
The algorithms and insights obtained from the technical work will benefit Computer Science and related disciplines where geometric 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. A complementary goal is also to introduce Computer Science techniques into other fields.
The award will support and train two or more PhD students in Computer Science at UIUC. The PI is committed to popularizing ideas and techniques that will be investigated by giving courses, publishing the research, and using less convectional new tools to disseminate the research such as 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 proximity search in geometric settings - such tasks are fundamental tasks in real world applications, ranging from web search, machine learning, data-mining and others.
We developed new algorithms addressing issues such as (i) how to search on huge data-sets by efficient algorithms that work in time proportional to the data set size, (ii) how to shrink it and perform proximity search on it, (iii) finding sparse representation of data, (iv) how to model proximity for data that is randomly generated, (v) how to do proximity search on combination of input points, (vi) what kind of search can be done if we are allowed to ignore some feature in the data, and (vii) others.
This project had resulted in a significant progress of the state of the art algorithms for proximity search. Highlights of this project includes: (i) the development of the net & prune technique for solving geometric optimization problems, (ii) defined and studied the problem of proximity search in robust settings, and in particular suggested way to model noise for this purpose.
Several graduate students were trained as part of this grant, two of them currently hold faculty positions in US universities. The research done for this project resulted in the publication of 33 papers in prestigious conferences and journals.
Last Modified: 10/06/2017
Modified by: Sariel Har-Peled
Please report errors in award information by writing to: awardsearch@nsf.gov.
