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.
