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.

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