Preserving average proximity in arrays

ABSTRACT

Programmers and data structure designers are often forced to choose between alternative structures. In storing these structures, preserving logical adjacencies or “proximity” is usually an important consideration. The combinatorial problem of storing arrays as various kinds of list structures is examined. Embeddings of graphs are used to model the loss of proximity involved in such storage schemes, and an elementary proof that arrays cannot be stored as linear lists with bounded loss of proximity is presented. Average loss of proximity is then considered, and it is shown that arrays cannot be stored as linear lists with only bounded loss of average proximity, but can be so stored in binary trees. The former result implies, for instance, that row major order is an asymptotically optimal storage strategy for arrays.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: DeMillo, R.A., Eisenstat, S.C., and Lipton, R.J. Space-time tradeoffs in structured programming. Proc. 1976 Conf. on Inform. Sci. and Syst., Baltimore, Md., 1976, pp. 431-434.
• 3: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 4: R. J. Lipton , S. C. Eisenstat , R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures, Journal of the ACM (JACM), v.23 n.4, p.720-732, Oct. 1976 [doi>10.1145/321978.321990]
• 5: A. J. Perlis , Charles Thornton, Symbol manipulation by threaded lists, Communications of the ACM, v.3 n.4, p.195-204, April 1960 [doi>10.1145/367177.367202]
• 6: Rosenberg, A.L. Preserving proximity in arrays. SIAM J. Comptng. 4, 4 (1975), 443-460.
• 7: Arnold L. Rosenberg, Managing storage for extendible arrays (Extended Abstract), Proceedings of the sixth annual ACM symposium on Theory of computing, p.297-302, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803907]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Performance, Theory

Keywords:
arrays, average proximity, graph embedding, linear lists, proximity, trees