Rearranging data to maximize the efficiency of compression

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rearranging data to maximize the efficiency of compression

Full text

Pdf (952 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems table of contents

Cambridge, Massachusetts, United States

Pages: 78 - 90

Year of Publication: 1985

ISBN:0-89791-179-2

Authors

Frank Olken
Doron Rotem

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 11, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/6012.15407 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Bat79	D. S. Batory, On searching transposed files, ACM Transactions on Database Systems (TODS), v.4 n.4, p.531-544, Dec. 1979 [doi>10.1145/320107.320125]
	Ber72	Patrick P. Bergmans. Minimizing expected travel time on geometrical patterns by optimal probability rearrangements, informatior~ and O0atrol, :331-350, 1972.
	Bia69	T. Bially. Space-fining curves: their generation and application to bandwidth reduction. IEEE Tra~sactio~ on I~formation Theory, IT-15:658-064, November 1909.
	BK74	L.R. Ba~l and H. Kobayashi. Image data compression by predictive coding ii: encoding algorithms. IBM Journal of Research and De~dopraent, 18(2), 1974.
	But71	Arthur R. Butz. Alternative algorithm for hilbext's space filling curve. IEEE Transaction~ or~ Informatio~ Theory, IT-17:424- 426~ April 1971.
	EOS81	S. J. Eggers, F. Olk~n, and A. Shoshani. A compression technique for large statistical databases. In Proceeding8 of the International Gonference on Very Large Databases (VLDBJ, pages 424--434, 1981.
	ES80	S.J. Eggers and A. Shoshani. Efficient access of compressed data. In Proceedings of the 6th International Conference or; Very Large Databases (VLDBJ, pages 205-211, 1980.
	GGJ76	M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
	Gol66	S. W. Golomb. Run-length encoding. IEEE Tranaactiona on information Theory, IT-12:399, 1966.
	HLP52	G. H. Hardy, J. E. Littlewood, and G. Polya. l~equalities. 1952.
	HS77	H. Horowitz and S. Sahni. Fundamental8 of . Data Structures. Computer Science Press, Inc., Potomac, Md., 1977.
	PAB68	E. A. Patrick, D. R. Anderson, and F. K. Bechtel. Mapping multi-dimensional space to one dimension for computer output display. IEEE Transaction8 on Computers, C- 17:949-953, October 1968.
	Wie83	Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1983
	Won80	C. K. Wong, Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems, ACM Computing Surveys (CSUR), v.12 n.2, p.167-178, June 1980 [doi>10.1145/356810.356814]
	Won83	C. K. Wong, Algorithmic Studies in Mass Storage Systems, W. H. Freeman & Co., New York, NY, 1983

CITED BY 2

	Cher-Sheng Cheng , Chung-Ping Chung , Jean Jyh-Jiun Shann, Fast query evaluation through document identifier assignment for inverted file-based information retrieval systems, Information Processing and Management: an International Journal, v.42 n.3, p.729-750, May 2006
	H. V. Jagadish , J. Madar , Raymond T. Ng, Semantic Compression and Pattern Extraction with Fascicles, Proceedings of the 25th International Conference on Very Large Data Bases, p.186-198, September 07-10, 1999

INDEX TERMS

Classification:
E. Data
E.4 CODING AND INFORMATION THEORY
Subjects: Data compaction and compression

H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.1 Logical Design
Subjects: Data models
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.2 Information Storage
Subjects: File organization

General Terms:
Algorithms, Design, Economics, Theory, Verification

Collaborative Colleagues:

Frank Olken: colleagues

Doron Rotem: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player