Probability and Combinatorial Structures

-----------------------------------------------------------------------提案编号：DMS 9803780 PI：James Allen Fill Institution：约翰霍普金斯大学项目：概率与组合结构摘要：THIS的主题研究是用概率方法研究某些重要的组合结构。一类重要的结构是自组织数据结构，它以容易检索的顺序动态地维护记录文件，同时占用很少的存储空间，概率学家和计算机科学家已经研究了25年以上。这种自组织系统已经被应用于超大规模集成电路(VLSI)电路模拟、数据压缩、通信网络和遗传学中的问题。这项研究分析了比迄今为止所处理的更现实的复杂的概率模型，并在这样做的过程中为之前的研究提供了一个统一的框架。树形成了另一类重要的组合结构。研究人员分析了随机多元搜索树的“形状”，这是计算机科学中的基本结构，也是与自组织数据结构有关的自然产生的结构。这项工作涉及概括和分析已经很大的递归树类别，这些递归树已被用来模拟流行病的传播、古代手稿的家谱和传销计划。研究人员还建立了传销的连续时间模型，并由此推导出在相应的离散时间模型下没有得到的操作特性。这项工作的另一个方面是对不完整数字搜索树(TRIE)高度分析的推广；该推广适用于计算机网络中多个领导人的选举。这项工作显然与高性能计算和通信的联邦战略领域有关。

----------------------------------------------------------------------- Proposal Number: DMS 9803780 PI: James Allen Fill Institution: The Johns Hopkins University Project: Probability and Combinatorial Structures Abstract: The theme of the this research is the study of certain important combinatorial structures using probabilistic methods. One important class of structures is that of self-organizing data structures, which dynamically maintain a file of records in easily retrievable order while using up little memory space and which have been investigated by probabilists and computer scientists for more than 25 years. Such self-organizing systems have been applied to problems in very large-scale integration (VLSI) circuit simulation, data compression, communications networks, and genetics. The research analyzes more realistically complex probability models than have heretofore been treated, and in doing so provides a unifying framework for previous studies. Trees form another important class of combinatorial structures. The investigator analyzes the "shape" of random m-ary search trees, fundamental structures in computer science that also arise naturally in connection with self-organizing data structures. The work involves generalizing and analyzing the already large class of recursive trees, which have been used to model such things as the spread of epidemics, family trees of ancient manuscripts, and pyramid schemes. The researcher also develops a continuous-time model for pyramid schemes and derives for it operational characteristics which have not been obtained under the corresponding discrete-time model. Another facet of this work is a generalization of the analysis of the height of an incomplete digital search tree, or trie; the generalization has applications to the election of multiple leaders in a computer network. This work relates clearly to the Federal Strategic Area of high-performance computing and communi cation.