An Aid For The Selection Of Efficient Storage Structures
Frank Wm. Tompa, Raúl Ramírez · INFOR Information Systems and Operational Research · 1983
The representations used to implement data structures play a large part in determining the execution cost for most applications. Because suitable representations may be chosen from a very large class, it is important to search systematically for the efficient ones. In this paper algorithms based on dynamic programming are presented. It is assumed that an application’s behaviour is specified by means of evaluation maps that refiect the expected run time and storage space required by each component of the application’s data structure. Those maps must be searched to find representations for each component that, when composed into a single storage structure, minimize the cost for the application according to a given cost formula. The algorithms incorporate bounds on the maximum allowable run time and storage space and solve the selection problem in pseudo-polynomial time and space.