US-Austria Cooperative Research: Analysis of Data Structures for Digital Search

美国-奥地利合作研究：数字搜索数据结构分析

• 批准号: 8912631
• 负责人: Wojciech Szpankowski
• 金额: $ 0.93万
• 依托单位: Purdue Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-02-01 至 1993-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8912631&HistoricalAwards=false
• 关键词: US; Austria; Cooperative; Research; Analysis

This award supports Dr. Wojciech Szpankowski of Purdue University to collaborate in computer science research with Drs. Peter Kirschenhofer and Helmut Prodinger of the Department of Algebra and Discrete Mathematics of the Technical University of Vienna. They are developing theoretical methods for the analysis of algorithms and data structures, drawing from several areas of applied mathematics. They plan to apply these methods to an in-depth analysis of the average case behavior of digital search algorithms. Collaboration is necessary because the problems they want to attack require diverse expertise in several fields of mathematics. The primary responsibilities of the Austrian collaborators in this project involve their expertise in asymptotic approximation and combinatorial analysis, while Dr. Szpankowski contributes expertise in stochastic modelling and general problem formulation. The analysis of algorithms and data structures is a rapidly developing area in theoretical computer science with a strong impact on practical problems. The cost of performance of algorithms, including such factors as the storage requirements of data structures and the execution time of certain subroutines, is usually described in terms of worst case behavior and average case behavior. Digital tree search is one of the main approaches to data storage and retrieval. The proposed research on average case behavior of digital search trees will contribute to improved choice and design of data structures and the new analytical techniques will have relevance in other areas.

该奖项支持普渡大学的 Wojciech Szpankowski 博士与 Drs. Wojciech Szpankowski 进行计算机科学研究合作。维也纳技术大学代数与离散数学系的 Peter Kirschenhofer 和 Helmut Prodinger。 他们正在开发用于分析算法和数据结构的理论方法，借鉴应用数学的多个领域。 他们计划将这些方法应用于深入分析数字搜索算法的平均情况行为。 合作是必要的，因为他们想要解决的问题需要多个数学领域的不同专业知识。 奥地利合作者在该项目中的主要职责涉及渐近逼近和组合分析方面的专业知识，而 Szpankowski 博士贡献了随机建模和一般问题表述方面的专业知识。 算法和数据结构的分析是理论计算机科学中快速发展的领域，对实际问题有很大影响。 算法的性能成本，包括数据结构的存储要求和某些子例程的执行时间等因素，通常用最坏情况行为和平均情况行为来描述。 数字树搜索是数据存储和检索的主要方法之一。 所提出的对数字搜索树的平均案例行为的研究将有助于改进数据结构的选择和设计，并且新的分析技术将在其他领域具有相关性。