Implicit data structures (Preliminary Draft)

ABSTRACT

We consider representations of data structures in which the relative ordering of the values stored is implicit in the pattern in which the elements are retained, rather than explicit in pointers. Several implicit schemes for storing data are introduced to permit efficient implementation of the instructions insert, delete and find. &thgr;(@@@@N) basic operations are shown to be necessary and sufficient, in the worst case, to perform these instructions provided that the data elements are kept in some fixed partial order. We demonstrate, however, that further improvements can be made if an arrangement other than a fixed partial order is used. A structure, based on a fixed partial order, is introduced to facilitate multiple key searches. This structure, together with the retrieval scheme based upon it, is shown to be within a constant factor of the optimal one based on a partial order.

REFERENCES

• 1: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 2: Bentley, J.L., D. Detig, L. Guibas, J. Saxe, "An Optimal Data Structure for Minimal-Storage Dynamic Member Searching", unpublished manuscript.
• 3: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 4: Hakim, J.K., Personal Communication.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Snyder, L., "On Uniquely Representable Data Structures", Proc. 18th IEEE Symp. on FOCS (1977), pp. 142-146.
• 7: Williams, J.W.J., "Algorithm 232: Heapsort", CACM 7 (1964), pp. 347-348.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Measurement, Theory