Article

Free access

Managing storage for extendible arrays (Extended Abstract)

Author:

Arnold L. RosenbergAuthors Info & Claims

STOC '74: Proceedings of the sixth annual ACM symposium on Theory of computing

Pages 297 - 302

https://doi.org/10.1145/800119.803907

Published: 30 April 1974 Publication History

PDF eReader

Abstract

Efficient storage utilization by schemes which allocate storage for extendible arrays is studied. A minimax lower bound on efficiency of storage use by such schemes is derived; and a scheme which achieves this bound is exhibited. When arrays are constrained to expand according to a preassigned finite set of shapes, the general lower bound can be lowered dramatically; in fact, if a single shape for expansion is chosen, one can devise a scheme which utilizes storage perfectly for arrays of that shape.

References

[1]

E.d.S. de Villiers and L.B. Wilson, Hash coding methods for sparse matrices, Tech. Rpt. 45, Univ. of Newcastle upon Tyne (Computing Lab.) 1973.

Google Scholar

[2]

D.E. Knuth, "The Art of Computer Programming I: Fundamental Algorithms," Addison-Wesley, Reading, Mass., 1968.

Digital Library

Google Scholar

[3]

A.L. Rosenberg, Allocating storage for extendible arrays, J.ACM, to appear; see also IBM Report RC-4306, 1973.

Digital Library

Google Scholar

[4]

A.L. Rosenberg, Managing storage for extendible arrays, SICOMP, to appear; see also IBM Reports RC-4433, RC-4450, 1973.

Google Scholar

[5]

W. Sierpinski, "Elementary Theory of Numbers," Panstwowe Vydawnictwo Nankowe, Warsaw, 1964.

Google Scholar

[6]

L.J. Stockmeyer, Extendible array realizations with additive traversal, IBM Report RC-4578, 1973.

Google Scholar

Cited By

View all

Otoo ENimako GOhene-Kwofie D(2013)Chunked extendible dense arrays for scientific data storageParallel Computing10.1016/j.parco.2013.08.00639:12(802-818)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.parco.2013.08.006
Nimako GOtoo EOhene-Kwofie D(2012)Chunked Extendible Dense Arrays for Scientific Data StorageProceedings of the 2012 41st International Conference on Parallel Processing Workshops10.1109/ICPPW.2012.9(38-47)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPPW.2012.9
DeMillo REisenstat SLipton R(1978)Preserving average proximity in arraysCommunications of the ACM10.1145/359361.35944721:3(228-231)Online publication date: 1-Mar-1978
https://dl.acm.org/doi/10.1145/359361.359447

Index Terms

Managing storage for extendible arrays (Extended Abstract)
1. Information systems
  1. Information retrieval
    1. Evaluation of retrieval results
  2. Information storage systems
    1. Record storage systems
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies

Recommendations

Managing Storage for Extendible Arrays

Schemes which allocate storage for extendible arrays cannot utilize storage as efficiently as can their nonextendible counterparts. Relative to formal notions of array scheme and (extendible) array realization, a formal way of gauging efficiency of ...
Storage schemes for boundedly extendible arrays

The high costs of extendibility in array realizations can be reduced dramatically by placing a bound on how big the arrays of interest will grow. Whereas extendible array realizations require order of p · log p storage locations to store two-...
Chunked Extendible Dense Arrays for Scientific Data Storage
ICPPW '12: Proceedings of the 2012 41st International Conference on Parallel Processing Workshops

Several meetings of the Extremely Large Databases Community for large scale scientific applications, advocate the use of multidimensional arrays as the appropriate model for representing scientific databases. Scientific databases gradually grow to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '74: Proceedings of the sixth annual ACM symposium on Theory of computing

April 1974

352 pages

ISBN:9781450374231

DOI:10.1145/800119

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 1974

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

STOC '74 Paper Acceptance Rate 35 of 95 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Otoo ENimako GOhene-Kwofie D(2013)Chunked extendible dense arrays for scientific data storageParallel Computing10.1016/j.parco.2013.08.00639:12(802-818)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.parco.2013.08.006
Nimako GOtoo EOhene-Kwofie D(2012)Chunked Extendible Dense Arrays for Scientific Data StorageProceedings of the 2012 41st International Conference on Parallel Processing Workshops10.1109/ICPPW.2012.9(38-47)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPPW.2012.9
DeMillo REisenstat SLipton R(1978)Preserving average proximity in arraysCommunications of the ACM10.1145/359361.35944721:3(228-231)Online publication date: 1-Mar-1978
https://dl.acm.org/doi/10.1145/359361.359447

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Managing Storage for Extendible Arrays

Storage schemes for boundedly extendible arrays

Chunked Extendible Dense Arrays for Scientific Data Storage