|
|
|
 |
 National Science
Foundation Award #0311548 |
 |
|
|
Sublinear Property Testing of Large Collections of Data Objects |
| |
| Investigator(s): |
Jing Li (PI)
|
| Sponsor: |
Case Western Reserve University, OH 44106 2163684510
|
| Start Date/Expiration Date |
2003-07-01 to 2005-06-30 (amended 2005-07-14) |
| Awarded Amount to Date: |
$110,707 |
| Abstract: With increasing data processing needs, many applications belonging
to areas such as communication networks, computational biology,
e-commerce, etc. require the processing of very large data sets under
time and space limitations. This need makes it necessary to seek
new, more efficient algorithmic models involving resource restrictions.
The main objective of this project is to explore the tradeoffs between
limiting the computing resources (time, space, access to input) available
to an algorithm and the resulting loss in accuracy and effectiveness.
By testing quantitative properties as well as qualitative ones, the link
between the efficiency/effectiveness of property testing and those of
approximation algorithms can be investigated. To this end, this project
involves devising sublinear algorithms for checking combinatorial
properties of various types of large data objects such as sequences,
graphs, and sets. This task can be achieved through intelligent random
sampling of the data, minimizing the number of bits of the input that
the algorithm needs to access through either reusing samples or choosing
samples carefully so that each accessed bit yields as much information
as possible about the input.
The broader impact of this project is in improving the understanding
of resource-bounded computation on different types of large data. The
new meta-techniques developed are expected to apply to a variety of
problems in different application areas which now see the processing of
input as a major bottleneck. For students of computer science, these
techniques bring a new point of view to understanding the possibilities
and limitations of computation as well as an understanding of data-related
limitations and bottlenecks of certain types of applications that need to
be addressed via unconventional models. |
|
| NSF Org: |
CCF - Division of Computer and Communication Foundations |
| Award Number: |
0311548 |
| Award Instrument: |
Continuing grant |
| Program Manager: |
Ding-Zhu Du
CCF Division of Computer and Communication Foundations
CSE Directorate for Computer & Information Science & Engineering
|
| NSF Program(s): |
THEORY OF COMPUTING |
| Field Application(s): |
|
| Program Reference Code(s): |
ADVANCED SOFTWARE TECH & ALGOR, 9216 |
| Program Element Code(s): |
2860 |
|
|
| |
 |
|
|
|
|
|
|
|
