| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | January 16, 2020 |
| Latest Amendment Date: | September 20, 2023 |
| Award Number: | 1941086 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Karl Wimmer
kwimmer@nsf.gov (703)292-2095 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2020 |
| End Date: | September 30, 2026 (Estimated) |
| Total Intended Award Amount: | $600,000.00 |
| Total Awarded Amount to Date: | $600,000.00 |
| Funds Obligated to Date: |
FY 2021 = $115,490.00 FY 2022 = $247,351.00 FY 2023 = $130,085.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1500 SW JEFFERSON AVE CORVALLIS OR US 97331-8655 (541)737-4933 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
Corvallis OR US 97331-2140 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01002122DB NSF RESEARCH & RELATED ACTIVIT 01002223DB NSF RESEARCH & RELATED ACTIVIT 01002324DB NSF RESEARCH & RELATED ACTIVIT 01002425DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Measuring similarity between objects is a fundamental problem prevalent in many applications, including registration in medical image processing, function detection in protein modeling, reconstructing evolutionary trees in phylogenomics, and finding recurrent patterns in data analysis. Different measures of similarity have been studied for a range of problems in engineering and computer science, ranging from very accurate but hard to compute to less accurate but efficiently computable. This project studies different similarity measures from the computability and effectiveness point of view. It views all similarity measures as maps between objects, and considers different geometric and topological representations of the objects.
Specifically, the research of this award focuses on the following dichotomy. On one hand, it is often hard to compute or even approximate mathematically accurate similarity measures, studied abstractly as geometric shape matching and metric embedding problems in computational geometry and topology. On the other hand, there are faster heuristics engineered for specific applications that lack theoretical guarantees, hence are not generalizable. In dichotomy is opportunity ? this project will use parameterized complexity to create a finer understanding of the complexity of computing similarity measures between metric spaces using different representations and properties. If successful, the research of this award will result in new algorithms with new performance guarantees, in particular, for cases of practical interest.
Measuring similarity between geometric objects is a fundamental problem with numerous applications, so this project, and the students that it trains, will have significant impact on theory and practice in many areas.
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.
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.
