Low-Complexity Compression with Random Access

Kamparaju, Srikanth and Mastan, Shaik and Vatedka, Shashank (2022) Low-Complexity Compression with Random Access. In: 14th IEEE International Conference on Signal Processing and Communications, SPCOM 2022, 11 July 2022 through 15 July 2022, Bangalore.

[img] Text
SPCOM_2022.pdf - Published Version
Restricted to Registered users only

Download (331kB) | Request a copy

Abstract

We investigate the problem of variable-length compression with random access for stationary and ergodic sources, wherein short substrings of the raw file can be extracted from the compressed file without decompressing the entire file. It is possible to design compressors for sequences of length n that achieve compression rates close to the entropy rate of the source, and still be able to extract individual source symbols in time θ(1) under the word-RAM model. In this article, we analyze a simple well-known approach used for compression with random access. We theoretically show that this is suboptimal, and design two simple compressors that simultaneously achieve entropy rate and constant-time random access. We then propose dictionary compression as a means to further improve performance, and experimentally validate this on various datasets. © 2022 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashankhttps://orcid.org/0000-0003-2384-9392
Item Type: Conference or Workshop Item (Paper)
Additional Information: The work of S. Vatedka was supported by a seed grant from IIT Hyderabad and and a Start-up Research Grant (SRG/2020/000910) from SERB, India.
Uncontrolled Keywords: Compressed files; Compression rates; Entropy rates; Ergodic sources; Lower complexity; Random access; Simple++; Stationary sources; Sub-strings; Variable length
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 01 Sep 2022 10:19
Last Modified: 01 Sep 2022 10:19
URI: http://raiith.iith.ac.in/id/eprint/10380
Publisher URL: http://doi.org/10.1109/SPCOM55316.2022.9840790
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10380 Statistics for this ePrint Item