A probabilistic approach to the problem of automatic selection of data representations

author: Tyng-Ruey Chuang and Wen L. Hwang
publication date: May 1996
cite this with: Tyng-Ruey Chuang and Wen L. Hwang. A probabilistic approach to the problem of automatic selection of data representations. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming (ICFP), pages 190-200. Philadelphia, Pennsylvania, USA. May 1996.
link this with: http://tsm.iis.sinica.edu.tw/papers/icfp96/
copyright: all rights reserved
category: Functional Programming
full paper: postscript


The designs and implementations of efficient aggregate data structures have been important issues in functional programming. It is not clear how to select a good representation for an aggregate when access patterns to the aggregate are highly variant, or even unpredictable. Previous approaches rely on compile{time analyses or programmer annotations. These methods can be unreliable because they try to predict a program’s behavior before it is executed. We propose a probabilistic approach, which is based on Markov processes, for automatic selection of data representations. The selection is modeled as a random process moving in a graph with weighted edges. The proposed approach employs coin tossing at run{time to help choosing suitable data representations. The transition probability function used by the coin tossing is constructed in a simple and common way from a measured cost function. We show that, under this setting, random selections of data representations can be quite eective. The probabilistic approach is used to implement bag aggregates, and the performance results are compared to those of deterministic selection strategies.

papers:icfp96:home Last modified: 2007/10/26 15:12