Bicriteria Data Compression

DOI10.1137/17M1121457zbMath1493.68136OpenAlexW2983159758WikidataQ118165406 ScholiaQ118165406MaRDI QIDQ5242925

Rossano Venturini, Andrea Farruggia, Antonio Frangioni, Paolo Ferragina

Publication date: 8 November 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1121457

zbMATH Keywords

data compressionapproximation algorithmPareto optimizationLempel-Ziv 77

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25)

Uses Software

• Hadoop
• Bigtable
• LZ77

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing and indexing repetitive sequences
• On optimally partitioning a text to improve its compression
• The uniform memory hierarchy model of computation
• Algorithms for parallel memory. II: Hierarchical multilevel memories
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• String matching in Lempel-Ziv compressed strings
• Generalized substring compression
• On the Bit-Complexity of Lempel--Ziv Compression
• A model of sequential computation with Pipelined access to memory
• The Cutting-Plane Method for Solving Convex Programs
• Linear work suffix array construction
• Boosting textual compression in optimal linear time
• Online Sorted Range Reporting
• A dual algorithm for the constrained shortest path problem
• Universal codeword sets and representations of the integers
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Bicriteria Network Design Problems
• An analysis of the longest match and the greedy heuristics in text encoding
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Lempel-Ziv Factorization: Simple, Fast, Practical
• Run-length encodings (Corresp.)
• A Simplex Method for Function Minimization
• On Information and Sufficiency
• String Processing and Information Retrieval

This page was built for publication: Bicriteria Data Compression