An adaptive packed-memory array

ABSTRACT

The packed-memory array (PMA) is a data structure that maintains a dynamic set of N elements in sorted order in a Θ(N)-sized array. The idea is to intersperse Θ(N) empty spaces or gaps among the elements so that only a small number of elements need to be shifted around on an insert or delete. Because the elements are stored physically in sorted order in memory or on disk, the PMA can be used to support extremely efficient range queries. Specifically, the cost to scan L consecutive elements is O(1+L/B) memory transfers.This paper gives the first adaptive packed-memory array (APMA), which automatically adjusts to the input pattern. Like the original PMA, any pattern of updates costs only O(log² N) amortized element moves and O(1+(log² N)/B) amortized memory transfers per update. However, the APMA performs even better on many common input distributions achieving only O(logN) amortized element moves and O(1+(logN)/B) amortized memory transfers. The paper analyzes sequential inserts, where the insertions are to the front of the APMA, hammer inserts, where the insertions "hammer" on one part of the APMA, random inserts, where the insertions are after random elements in the APMA, and bulk inserts, where for constant α∈[0,1], N^α elements are inserted after random elements in the APMA. The paper then gives simulation results that are consistent with the asymptotic bounds. For sequential insertions of roughly 1.4 million elements, the APMA has four times fewer element moves per insertion than the traditional PMA and running times that are more than seven times faster.

REFERENCES

• 1: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton, Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy, Proceedings of the 10th Annual European Symposium on Algorithms, p.139-151, September 17-21, 2002
• 2: M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
• 3: Michael A. Bender , Erik D. Demaine , Martin Farach-Colton, Cache-Oblivious B-Trees, SIAM Journal on Computing, v.35 n.2, p.341-358, 2005 [doi>10.1137/S0097539701389956]
• 4: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
• 5: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Journal of Algorithms, v.53 n.2, p.115-136, November 2004 [doi>10.1016/j.jalgor.2004.04.014]
• 6: Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142385]
• 7: M. A. Bender, M. Farach-Colton, and M. Mosteiro. Insertion sort is O(n log n). In Proc. 3rd International Conference on Fun with Algorithms (FUN), pages 16--23, 2004.
• 8: Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Bradley C. Kuszmaul, Concurrent cache-oblivious b-trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074009]
• 9: Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
• 10: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 11: Paul F. Dietz , Joel I. Seiferas , Ju Zhang, A Tight Lower Bound for On-line Monotonic List Labeling, Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, p.131-142, July 06-08, 1994
• 12: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 13: Paul F. Dietz , Ju Zhang, Lower Bounds for Monotonic List Labeling, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory, p.173-180, July 11-14, 1990
• 14: Alon Itai , Alan G. Konheim , Michael Rodeh, A Sparse Table Implementation of Priority Queues, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.417-431, July 13-17, 1981
• 15: I. Katriel. Implicit data structures based on local reorganizations. Master's thesis, Technion -- Israel Inst. of Tech., Haifa, May 2002.
• 16: Vijayshankar Raman, Locality preserving dictionaries: theory & application to clustering in databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.337-345, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304009]
• 17: Athanasios K. Tsakalidis, Maintaining order in a generalized linked list, Acta Informatica, v.21 n.1, p.101-112, May 1984 [doi>10.1007/BF00289142]
• 18: Dan E. Willard, Maintaining dense sequential files in a dynamic environment (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.114-121, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802183]
• 19: Dan E. Willard, Good worst-case algorithms for inserting and deleting records in dense sequential files, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.251-260, May 28-30, 1986, Washington, D.C., United States
• 20: Dan E. Willard, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Information and Computation, v.97 n.2, p.150-204, April 1992 [doi>10.1016/0890-5401(92)90034-D]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.0 General

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays; Lists, stacks, and queues
  E.5 FILES
      Subjects: Sorting/searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
adaptive packed-memory array, cache oblivious, locality preserving, packed-memory array, range query, rebalance, sequential file maintenance, sequential scan, sparse array