Collaborative Research: Algorithms for sparse data representations

协作研究：稀疏数据表示算法

• 批准号: 0354690
• 负责人: Shanmugavelayu Muthukrishnan
• 金额: $ 27.22万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0354690&HistoricalAwards=false
• 关键词: Collaborative; Research; Algorithms; sparse; data

The investigators address the mathematical underpinnings of compressing large data sets using sparse representations over rich dictionaries and develop a foundation for classifying these problems in terms of their algorithmic complexity. The investigators also find efficient algorithms for computing high-quality sparse representations of data over sophisticated, commonly used dictionaries that provably perform as claimed with respect to both efficiency and correctness of output and are particularly well-suited for massive data set applications. The research proceeds at multiple levels of abstraction. It considers general factors of a representation class that guarantee or preclude such algorithms, it considers algorithms for specific common representation classes, and it finds algorithms for representation classes adapted to specific common (and diverse) applications, such as solutions of partial differential equations, image processing, and database query optimization.Over the past ten years there has been a dramatic increase in data gathering mechanisms, as well as an ever-increasing demand for finer data analysis in applications that rely on scientific and geometric modeling. Each day, literally millions of large data sets are generated in medical imaging, surveillance, and scientific acquisition. In addition, the internet has become a communication medium with vast capacity, generating massive traffic data sets. The usefulness of these data sets rests on our ability to process them efficiently, whether it be for storage, transmission, visual display, fast on-line graphical query, correlation, or registration against data from other modalities. The current state of the art in data processing is far from providing the efficient and faithful representations required in emerging applications. With few exceptions, previous work has not provided algorithms whose efficiency or output quality, though typically validated experimentally, has been analyzed rigorously and thoroughly. The investigators carry out fundamental mathematical and algorithmic research to significantly increase our capacity to process and manage large data sets. The research makes significant mathematical progress in providing rigorous algorithmic results that are of great need in this field. The research also makes significant improvements through highly efficient algorithms in the sizes of data sets that are analyzable and in the types of data processing tasks that can be carried out. Finally, the investigators create a library of software for massive data processing applications.

研究人员解决了在丰富的字典上使用稀疏表示压缩大型数据集的数学基础，并为根据算法复杂性对这些问题进行分类奠定了基础。 研究人员还发现了有效的算法，用于在复杂的常用字典上计算数据的高质量稀疏表示，这些字典在输出的效率和正确性方面都可以证明，并且特别适合于大规模数据集应用。 研究在多个抽象层次上进行。 它考虑表示类的保证或排除此类算法的一般因素，它考虑特定公共表示类的算法，并且它找到适用于特定公共表示类的算法。（和多样的）应用，例如偏微分方程的解、图像处理和数据库查询优化。在过去的十年中，数据收集机制已经有了急剧的增长，以及在依赖于科学和几何建模的应用中对更精细的数据分析的不断增长的需求。 每天，在医学成像、监控和科学采集中都会产生数百万个大型数据集。此外，互联网已经成为一种具有巨大容量的通信媒介，产生了大量的交通数据集。 这些数据集的有用性取决于我们有效处理它们的能力，无论是存储，传输，视觉显示，快速在线图形查询，相关性，还是与其他形式的数据配准。 目前的数据处理技术还远远不能提供新兴应用中所需的高效和可靠的表示。 除了少数例外，以前的工作还没有提供算法的效率或输出质量，虽然通常经过实验验证，已被严格和彻底的分析。 研究人员进行基础数学和算法研究，以显着提高我们处理和管理大型数据集的能力。 这项研究在提供这一领域非常需要的严格算法结果方面取得了重大的数学进展。 该研究还通过高效的算法在可分析的数据集的大小和可以执行的数据处理任务的类型方面做出了重大改进。 最后，研究人员为大规模数据处理应用程序创建了一个软件库。