Mathematical Sciences: Markov Chains and Self-Organizing Data Structures

自组织数据结构是一种动态地以易于检索的顺序维护记录文件，同时占用很少的内存空间的数据结构，概率论家和计算机科学家已经对它进行了超过25年的研究。这种自组织系统已经应用于超大规模集成电路仿真、数据压缩和通信网络中的问题。该研究项目的目标是应用分析马尔可夫链的技术，其中一些是最近才开发出来的，用于研究自组织列表和其他数据结构。工作的重点将是进一步分析清单重新排列标准办法的某些修改。其中一些修改，如“引用局部性”的马尔可夫访问模型，旨在更密切地模拟应用程序中遇到的数据的规则行为。在其他情况下，例如随机算法，规则本身被修改以提高性能。如果替换检索项的规则仅依赖于检索项的位置，则维护记录文件的结构称为自组织。其思想是文件将自我组织，经常检索的项倾向于向文件的前部倾斜。自组织结构通常用于计算机中的数据存储。概率论家和计算机科学家多年来一直在研究自组织数据结构的某些性能特征。这项研究将继续这样的调查。

Self-organizing data structures, which dynamically maintain a file of records in easily retrievable order while using up little memory space, 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, and communications networks. The goal of the proposed research project is to apply techniques for analyzing Markov chains, some only recently developed, to the study of self-organizing lists and other data structures. The work will focus on furthering the analysis of certain modifications of the standard schemes for list rearrangement. Some of these modifications, such as the Markovian access model for "locality of reference," are designed to model more closely the behavior of the rules on data encountered in applications. In other cases, such as stochastic algorithms, the rule itself is modified in an effort to improve performance. A structure for maintaining a file of records is called self-organizing if the rule for replacing a retrieved item depends only on the location from which the item was retrieved. The idea is that the file will organize itself, with frequently retrieved items tending to gravitate toward the front of the file. Self-organizing structures are commonly used for storing data in a computer. Probabilists and computer scientists have investigated certain performance characteristics of self- organizing data structures for many years. This research will continue such investigations.