Access Restriction

Author Lipton, Richard J. ♦ DeMillo, Richard A. ♦ Eisenstat, Stanley C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Trees ♦ Proximity ♦ Linear lists ♦ Average proximity ♦ Graph embedding ♦ 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.
Description Affiliation: Yale Univ., New Haven, CT (Eisenstat, Stanley C.; Lipton, Richard J.) || Georgia Institute of Technology, Atlanta, GA (DeMillo, Richard A.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 3
Page Count 4
Starting Page 228
Ending Page 231

Open content in new tab

   Open content in new tab
Source: ACM Digital Library