Title: Corpus-compressed Streaming and the Spotify Problem,
Abstract: In this work, we describe a problem which we refer to as the \textbf{Spotify
problem} and explore a potential solution in the form of what we call
corpus-compressed streaming schemes.
Inspired by the problem of constrained bandwidth during use of the popular
Spotify application on mobile networks, the Spotify problem applies in any
number of practical domains where devices may be periodically expected to
experience degraded communication or storage capacity. One obvious solution
candidate which comes to mind immediately is standard compression. Though
obviously applicable, standard compression does not in any way exploit all
characteristics of the problem; in particular, standard compression is
oblivious to the fact that a decoder has a period of virtually unrestrained
communication. Towards applying compression in a manner which attempts to
stretch the benefit of periods of higher communication capacity into periods of
restricted capacity, we introduce as a solution the idea of a corpus-compressed
streaming scheme.
This report begins with a formal definition of a corpus-compressed streaming
scheme. Following a discussion of how such schemes apply to the Spotify
problem, we then give a survey of specific corpus-compressed scheming schemes
guided by an exploration of different measures of description complexity within
the Chomsky hierarchy of languages.