NDLI: A general-purpose compression scheme for large collections

Content Provider	ACM Digital Library
Author	Williams, Hugh E. Cannane, Adam
Copyright Year	2002
Abstract	Compression of large collections can lead to improvements in retrieval times by offsetting the CPU decompression costs with the cost of seeking and retrieving data from disk. We propose a semistatic phrase-based approach called xray that builds a model offline using sample training data extracted from a collection, and then compresses the entire collection online in a single pass. The particular benefits of xray are that it can be used in applications where individual records or documents must be decompressed, and that decompression is fast. The xray scheme also allows new data to be added to a collection without modifying the semistatic model. Moreover, xray can be used to compress general-purpose data such as genomic, scientific, image, and geographic collections without prior knowledge of the structure of the data. We show that xray is effective on both text and general-purpose collections. In general, xray is more effective than the popular gzip and compress schemes, while being marginally less effective than bzip2. We also show that xray is efficient: of the popular schemes we tested, it is typically only slower than gzip in decompression. Moreover, the query evaluation costs of retrieval of documents from a large collection with our search engine is improved by more than 30% when xray is incorporated compared to an uncompressed approach. We use simple techniques for obtaining the training data from the collection to be compressed and show that with just over 4% of data the entire collection can be effectively compressed. We also propose four schemes for phrase-match selection during the single pass compression of the collection. We conclude that with these novel approaches xray is a fast and effective scheme for compression and decompression of large general-purpose collections.
Starting Page	329
Ending Page	355
Page Count	27
File Format	PDF
ISSN	10468188
e-ISSN	15582868
DOI	10.1145/568727.568730
Volume Number	20
Issue Number	3
Journal	ACM Transactions on Information Systems (TOIS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Phrase-based compression Random access Sampling
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications Information Systems Business, Management and Accounting

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Access control for large collections

A General SIMD-Based Approach to Accelerating Compression Algorithms

A transient hypergraph-based model for data access

A text compression scheme that allows fast searching directly in the compressed file

Compression, information theory, and grammars: a unified approach

Fast phrase querying with combined indexes

A knowledge-based message management system

Query-based sampling of text databases

A federated architecture for information management

A general-purpose compression scheme for large collections

Similar Documents

Access control for large collections

A General SIMD-Based Approach to Accelerating Compression Algorithms

A transient hypergraph-based model for data access

A text compression scheme that allows fast searching directly in the compressed file

Compression, information theory, and grammars: a unified approach

Fast phrase querying with combined indexes

A knowledge-based message management system

Query-based sampling of text databases

A federated architecture for information management

A general-purpose compression scheme for large collections