Fetching the paper…
Reading the bibliography…
Current methods which compress multisets at an optimal rate have computational complexity that scales linearly with alphabet size, making them too slow to be practical in many real-world settings.
G. Adelson-Velsky and E. Landis, “An algorithm for the organization of information,” Soviet Mathematics Doklady , vol. 3, pp. 1259–1263, 1962
1962
Earlier work this paper cites.
A. H. Robinson and C. Cherry, “Results of a prototype television bandwidth compression scheme,” Proceedings of the IEEE , vol. 55, no. 3, pp. 356–364, 1967
1967
Earlier work this paper cites.
R. Bayer, “Symmetric binary B-Trees: Data structure and maintenance algorithms,” Acta Informatica , vol. 1, no. 4, pp. 290–306, 1972
1972
Earlier work this paper cites.
P. M. Fenwick, “A new data structure for cumulative frequency tables,” Software: Practice and Experience , vol. 24, no. 3, pp. 327–336, 1994
1994
Earlier work this paper cites.
B. J. Frey and G. E. Hinton, “Free energy coding,” in Proceedings of Data Compression Conference-DCC’96 . IEEE, 1996, pp. 73–81
1996
Earlier work this paper cites.
B. J. Frey, “Bayesian networks for pattern classification, data compression, and channel coding,” Ph.D. dissertation, University of Toronto, 1997
1997
Earlier work this paper cites.
D. E. Knuth, The Art of Computer Programming, Volume 3 . Addison Wesley Longman Publishing Co., Inc., 1998
1998
Earlier work this paper cites.
A. Moffat, “An improved data structure for cumulative probability tables,” Software: Practice and Experience , vol. 29, no. 7, pp. 647–659, 1999
1999
Earlier work this paper cites.
L. Varshney and V. Goyal, “Toward a source coding theory for sets,” in 2006 Data Compression Conference (DCC) . IEEE, 2006, pp. 13–22
2006
Earlier work this paper cites.
J. Duda, “Asymmetric numeral systems,” arXiv:0902.0271 [cs, math] , 2009
2009
Earlier work this paper cites.
Y. A. Reznik, “Coding of sets of words,” in 2011 Data Compression Conference (DCC) . IEEE, 2011, pp. 43–52
2011
Cited alongside, same era.
V. Gripon, M. Rabbat, V. Skachek, and W. J. Gross, “Compressing multisets using tries,” in 2012 IEEE Information Theory Workshop , 2012, pp. 642–646
2012
Cited alongside, same era.
C. Steinruecken, “Lossless data compression,” Ph.D. dissertation, University of Cambridge, 2014
2014
Cited alongside, same era.
X. Yang and A. R. Barron, “Compression and predictive distributions for large alphabet iid and markov models,” in 2014 IEEE International Symposium on Information Theory , 2014, pp. 2504–2508
2014
Cited alongside, same era.
F. Giesen, “Interleaved entropy coders,” arXiv:1402.3392 [cs, math] , 2014
2014
Cited alongside, same era.
F. H. Kingma, P. Abbeel, and J. Ho, “Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables,” in International Conference on Machine Learning , Oct. 2019
2019
Later among the works it cites.
2020
Later among the works it cites.
J. Townsend, T. Bird, J. Kunze, and D. Barber, “HiLLoC: Lossless image compression with hierarchical latent variable models,” in International Conference on Learning Representations (ICLR) , 2020
2020
Later among the works it cites.
D. Severo, J. Townsend, A. J. Khisti, A. Makhzani, and K. Ullrich, “Your dataset is a multiset and you should compress it like one,” in NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications , 2021. [Online]. Available: https://openreview.net/forum?id=vjrsNCu8Km
2021
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
C. Steinruecken, “Compressing Sets and Multisets of Sequences,” IEEE Transactions on Information Theory , vol. 61, no. 3, pp. 1485–1490, 2015
2015
Cited alongside, same era.
C. Steinruecken, “Compressing Combinatorial Objects,” in 2016 Data Compression Conference (DCC) . IEEE, 2016, pp. 389–396
2016
Cited alongside, same era.
——, “Minimax compression and large alphabet approximation through poissonization and tilting,” IEEE Transactions on Information Theory , vol. 63, no. 5, pp. 2866–2884, 2017
2017
Cited alongside, same era.
J. Townsend, T. Bird, and D. Barber, “Practical lossless compression with latent variables using bits back coding,” in International Conference on Learning Representations (ICLR) , 2019
2019
Cited alongside, same era.
M. Barowsky, A. Mariona, and F. P. Calmon, “Predictive coding for lossless dataset compression,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2021, pp. 1545–1549
2021
Closest in time.
2021
Closest in time.
J. Townsend and I. Murray, “Lossless compression with state space models using bits back coding,” in Neural Compression: From Information Theory to Applications – Workshop at ICLR , 2021
2021
Closest in time.
Y. Ruan, K. Ullrich, D. Severo, J. Townsend, A. Khisti, A. Doucet, A. Makhzani, and C. J. Maddison, “Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding,” in International Conference on Machine Learning , 2021
2021
Closest in time.
D. Severo, J. Townsend, A. Khisti, A. Makhzani, and K. Ullrich, “Compressing multisets with large alphabets,” in 2022 Data Compression Conference (DCC) , 2022, pp. 322–331
2022
Closest in time.