Pith. sign in

REVIEW 4 major objections 4 minor 88 references

Random Permutation Codes: Lossless Source Coding of Non-Sequential Data

T0 review · 4 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This thesis proves that the optimal lossless code for any unordered, non-sequential data type is the entropy of its equivalence classes, and gives a coding scheme, Random Permutation Codes, that achieves it.

desk verdict Solid compilation of three real compression algorithms plus a general framework whose central theorem I could not verify — referee it, but require the missing proof and an explicit treatment of orbit-sampler complexity. read the letter →

arxiv 2411.14879 v1 pith:LZXATQKG submitted 2024-11-18 cs.IT eess.SPmath.IT

Daniel Severo This is my paper · ORCID
classification cs.ITeess.SPmath.IT MSC 94A2994A17
keywords losslesssourcecodingCombinatorialRandomVariablesPermutationCodesbits-backasymmetricnumeralsystemsequivalenceclassesmultisetcompressiongraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The thesis asks how many bits it really takes to store data whose order carries no meaning—a collection of files, rows in a database, nodes in a graph, or a dataset of images. It formalizes such an object as a Combinatorial Random Variable (CRV): the equivalence class of all sequences that represent the same non-sequential object, with the data type fixed by an equivalence relation $\sim$ on sequences. The paper's central claim is that the achievable lossless rate of a CRV is fully characterized by the equivalence relation and the data distribution, and that the optimal rate is the entropy of the equivalence-class random variable. Random Permutation Codes (RPCs) achieve this rate by using bits-back coding with asymmetric numeral systems to pick one of the many equivalent sequences at random, banking the bits saved by not transmitting the order, and recovering them exactly at decoding. If correct, the result unifies and completes earlier algorithms for multisets, clusterings, and graphs, and turns "ignore the meaningless order" from a heuristic into an exact information-theoretic limit.

What carries the argument

The central object is the equivalence class $[x^n]$: the set of all sequences that represent the same non-sequential object, whose size $|[x^n]|$ is the number of orderings being discarded. The load-bearing identity is $H(\mathbf{X}) = H(X^n) - \mathbb{E}[\log |[X^n]|]$ for exchangeable sequence distributions: the class entropy equals the sequence entropy minus the order information. Random Permutation Codes realize this identity with ANS decoding as an invertible sampler, uniformly selecting a representative of the class; the state then rises by the sequence code length and falls by $\log |[x^n]|$, netting the class entropy. The three published instantiations are ROC for multisets (sampling without replacement via a binary search tree), RCC for clusterings (using Foata's canonical cycle notation so cycles become clusters), and REC for graphs (sampling edges and vertex order under Pólya's urn).

What would settle it

A concrete test is to implement the RPC sampler for an equivalence relation not covered by the thesis, such as isomorphism classes of unlabeled graphs, and compare the code length against $H(\mathbf{X})$ on an exchangeable distribution; if for some relation the gap fails to vanish as $n$ grows, Theorem 7.3.2 would be false. A laboratory check on the covered cases is to measure ROC's code length against $nH(P)-\log(n!/\prod_x n_x!)$ and verify that the residual overhead goes to zero as the ANS state grows.

Watch

Extended reading notes

Core claim

The discovery, proved as Theorem 7.3.2 (Optimality of CRV Codes), is that for an exchangeable distribution over sequences $X^n$ and any equivalence relation $\sim$, the combinatorial random variable $\mathbf{X}=[X^n]_\sim$ has optimal asymptotic lossless rate $H(\mathbf{X})$, and this rate is attained by a Random Permutation Code. The code encodes the object by sampling one representative sequence from its equivalence class uniformly at random, encoding that representative with the underlying sequence codec, and using bits-back to subtract the $\log |[x^n]|$ bits that existed only to specify the order. The decoder reverses the steps, restoring the bits, so no information is lost. The thesis also proves a Markov property and a constructive–destructive decomposition for sequences of CRVs, showing the same rate identity holds when non-sequential objects are encoded one after another.

Load-bearing premise

The general achievability theorem assumes that for any equivalence relation one can compute the size of an equivalence class and sample one of its sequences uniformly at random using ANS arithmetic; the thesis supplies such samplers only for multisets, clusterings, and graphs, and treats the large-state initial-bits and dirty-bits overhead as negligible without a general proof.

Editorial extensions

If this is right

  • Multisets of exchangeable symbols, including collections of files or database rows, compress at the multiset's entropy with runtime independent of alphabet size.
  • Cluster assignments can be stored without ids or labels: RCC recovers the full $\log|\Pi|$ order-information saving, which is optimal for the implied cluster-size product model.
  • Graphs, including directed, undirected, non-simple, and hypergraph variants, compress at the graph's negative log-likelihood under Pólya's urn in quasi-linear time in the number of edges.
  • Any future equivalence relation with an efficient uniform orbit sampler inherits the optimality guarantee, so the framework is predictive rather than limited to the three worked examples.
  • Sequences of non-sequential objects, such as nested multisets or evolving clusterings, also achieve the optimal rate through the constructive–destructive decomposition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the practical content of the theorem is that rate-optimality reduces to sampler design: for a new data type, the only nontrivial engineering step is a uniform sampler over the equivalence class.
  • Inference: for equivalence relations whose orbits are hard to sample, such as isomorphism classes of unlabeled structures, the information-theoretic limit may be unreachable in polynomial time, so the open problem is the computational gap, not the rate.
  • Inference: because the order-saving term is independent of the symbol codec, the method stacks with any improved sequence compressor; the largest percentage gains appear where each element costs few bits, as with cluster ids, rather than where elements are already expensive, as with images.
  • Inference: a testable extension is to apply the CRV construction to data types not treated here, such as unlabeled trees or permutations modulo rotation; if a uniform orbit sampler exists, the same optimality proof should hold.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The thesis studies lossless source coding of non-sequential data, modeled as equivalence classes of sequences called Combinatorial Random Variables (CRVs). The central claim is that the achievable rate of a CRV is fully characterized by the data distribution and the equivalence relation, and that the optimal rate is achieved by Random Permutation Codes (RPCs), which use bits-back coding with ANS to sample a representative sequence uniformly from the equivalence class. Chapters 4, 5, and 6 present three instantiations: Random Order Coding (ROC) for multisets, Random Cycle Coding (RCC) for clusterings, and Random Edge Coding (REC) for graphs, with algorithmic pseudo-code, complexity analyses, and experiments. Chapter 7 is supposed to unify these under the general CRV/RPC framework and to prove the central optimality theorem (Theorem 7.3.2). The experimental sections show that the specialized codes approach or reach the stated theoretical rates (e.g., REC gap 0.0 in Table 6.1).

Significance. If the general framework is correct, the thesis would unify three previously published algorithms and give a clean information-theoretic characterization of compressing equivalence classes of sequences, with concrete algorithmic tools. The specialized chapters are a genuine strength: ROC, RCC, and REC are explicit, the bits-back constructions are well specified, the complexity claims are concrete, and the experiments support the theory for those three models. The Polya-urn model used with REC is attractive because it is integer-arithmetic only and gives competitive results on large sparse graphs. However, the significance of the claimed full characterization, as opposed to three special cases, depends entirely on Theorem 7.3.2, whose statement and proof are not present in the reviewed text; the general achievability also relies on an unproven computational premise about uniform orbit sampling for arbitrary equivalence relations. These issues prevent me from verifying the thesis-level claim at this stage.

major comments (4)
  1. [Chapter 7 / Theorem 7.3.2] The central theorem is missing. The list of theorems (p. ix) and the chapter outline promise "Theorem 7.3.2 (Optimality of CRV Codes)", and the abstract's claims of a "full characterization" and optimal rates "achieved within the family of RPCs" rest on it, but the reviewed text contains no statement or proof of this theorem. Please include the complete statement with all assumptions (discrete alphabet, finite support, the role of the equivalence relation, and whether the theorem is asymptotic or finite-block) and a full proof.
  2. [Chapter 7 / Definition 7.1.2 and Section 7.3] The general achievability result presumes that for an arbitrary equivalence relation one can compute the orbit size |[x^n]| and sample a representative uniformly from the orbit using ANS integer arithmetic. The manuscript constructs such samplers only for multisets, cycles, and edge permutations. This is not merely an efficiency gap: for an equivalence relation such as unlabeled graph isomorphism, the orbit size is n!/|Aut(G)| and computing |Aut(G)| is graph-isomorphism-hard. The paper should either state that Theorem 7.3.2 treats the orbit sampler as an oracle, or restrict the claimed characterization to equivalence relations admitting efficient uniform orbit samplers. Without one of these moves, "achieved within the family of RPCs" is established only for the three specialized relations.
  3. [Chapters 5-6 versus Chapter 7] The optimality results for RCC and REC are model-specific: RCC is optimal for the product-of-cluster-sizes model in Eq. (5.13), and REC is optimal for edge-permutation-invariant models in Definition 6.3.1. The general characterization in the abstract appears to claim optimality for arbitrary distributions over arbitrary CRVs, which is a substantially stronger statement. The bridge between these model-specific optimality proofs and the general CRV theorem is not visible in the text; please spell out how an arbitrary distribution over an equivalence-class alphabet is handled by the RPC encoder, or clarify the restricted class of distributions for which optimality is claimed.
  4. [Sections 2.2.3 and 6.3.4] The optimality statements are made in the ANS large-state regime, and Section 2.2.3 explicitly states that there is no known method guaranteed to avoid the initial-bits problem. Theorem 6.3.4 amortizes the initial-bits and log m overheads only as m tends to infinity. If Theorem 7.3.2 is an asymptotic result, this should be stated explicitly in the abstract and theorem; if a finite-length or non-asymptotic claim is intended, a finite-block length bound is needed.
minor comments (4)
  1. [Section 6.3] The text calls Polya's Urn "parameter-free" twice, but the model in Eq. (6.6) depends on a positive concentration parameter β. Please clarify whether β is fixed a priori, optimized, or transmitted, and adjust the "parameter-free" wording accordingly.
  2. [Table 5.1] The column header "1 8n log|Π|" appears to have a formatting error and should read something like "(1/8n) log |Π|" with units of bytes per element; this should be corrected for readability.
  3. [Preface and Section 3.6] The thesis says it treats "graphs" as a CRV, but REC only covers labeled graphs under edge-permutation and within-edge vertex-permutation equivalence; it does not cover vertex-relabeling/isomorphism equivalence. Please make this distinction explicit in the contributions and in the CRV examples of Chapter 7.
  4. [Section 4.8.2] There is a spelling error in "distribtuion"; the manuscript would benefit from a final proofreading pass for such typos.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the RPC rate identity is derived, not assumed; self-citations are disclosed and non-load-bearing.

full rationale

The central claim reduces to the standard orbit-size identity H([X]) = H(X^n) - E[log |[X^n]|] under a uniform representative distribution, and the paper derives this identity rather than assuming it. Section 4.2 states 'log 1/PM(M) = log 1/PX n (xn) − log M' for multisets, and Section 6.3 uses the same decomposition: 'log 1/PG(G) = log 1/PV 2m (v2m) − log|[v2m]|'. The general RPC construction in Chapter 7 applies this decomposition to an arbitrary equivalence relation, with a Shannon lower bound providing the converse. This is a theorem with a constructive bits-back achievability argument, not a parameter fit or a definitional equivalence. The specialized codes ROC, RCC, and REC are the author's prior publications, but the thesis contains their full proofs in Chapters 4-6, so Theorem 7.3.2 does not rest on an unverified self-citation. The experiments compare measured lossless code lengths to the information-content formula, and the reported zero gap is a consistency check of a code that is already proven optimal, not a fitted quantity renamed as a prediction. The only substantive caveat is that for a generic equivalence relation the paper does not provide an explicit efficient uniform-orbit sampler, only for the multiset, cycle, and edge cases; this is a computational/existential premise, not circularity, and it does not make the rate identity equivalent to its inputs.

Assumptions & free parameters 1 free parameters · 3 assumptions · 1 invented entities

The central claim depends on the exchangeability reduction, the ANS large-state approximation, and the existence of efficient orbit samplers. The only potential free parameter in the core framework is the Polya urn concentration beta, whose value is unreported in the experiments. No physical entities are postulated; the CRV is a mathematical abstraction.

free parameters (1)
  • Polya urn concentration beta
    Equation (6.6) in Section 6.3 defines the Polya Urn model with a parameter beta as the initial urn mass. The text calls the model 'parameter-free' and the experiments do not report how beta was chosen. If set to a constant (e.g., 1) it is a modeling constant; if estimated per dataset it is a free parameter.
assumptions (3)
  • domain assumption The source distribution over sequences can be replaced by an exchangeable distribution without changing the distribution over equivalence classes.
    Theorem 4.2.1 proves this for multisets; the general rate characterization in Chapter 7 presumably extends this reduction to arbitrary CRVs. All optimality claims rely on this equivalence.
  • standard math ANS operates in the large-state regime where the per-symbol state change equals the negative log-probability up to negligible overhead.
    Chapter 2 derives this (Theorems 2.1.8 and 2.1.9). The paper assumes this asymptotic regime when claiming optimal rates.
  • domain assumption Equivalence class sizes are computable and one can sample uniformly from the equivalence class using ANS decoding.
    The optimality of RPCs requires a uniform sampler over the orbit. The thesis implements such samplers for multisets, cycles, and edges, but the general framework assumes their existence for any equivalence relation.
invented entities (1)
  • Combinatorial Random Variable (CRV)
    purpose: Formalizes non-sequential data as a random variable over equivalence classes of sequences under a given equivalence relation.
    The CRV is a mathematical abstraction introduced in Definition 7.1.2. It is a definitional tool, not a falsifiable physical entity; its utility is demonstrated through the RPC framework and the three concrete coding schemes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Random Permutation Codes: Lossless Source Coding of Non-Sequential Data." pith.science (2026). https://pith.science/paper/LZXATQKG

@misc{pith2026241114879,
  author       = {Pith},
  title        = {Pith review of: Random Permutation Codes: Lossless Source Coding of Non-Sequential Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LZXATQKG}},
  note         = {Machine review of arXiv:2411.14879}
}
read the original abstract

This thesis deals with the problem of communicating and storing non-sequential data. We investigate this problem through the lens of lossless source coding, also sometimes referred to as lossless compression, from both an algorithmic and information-theoretic perspective. Lossless compression algorithms typically preserve the ordering in which data points are compressed. However, there are data types where order is not meaningful, such as collections of files, rows in a database, nodes in a graph, and, notably, datasets in machine learning applications. Compressing with traditional algorithms is possible if we pick an order for the elements and communicate the corresponding ordered sequence. However, unless the order information is somehow removed during the encoding process, this procedure will be sub-optimal, because the order contains information and therefore more bits are used to represent the source than are truly necessary. In this work we give a formal definition for non-sequential objects as random sets of equivalent sequences, which we refer to as Combinatorial Random Variables (CRVs). The definition of equivalence, formalized as an equivalence relation, establishes the non-sequential data type represented by the CRV. The achievable rates of CRVs is fully characterized as a function of the equivalence relation as well as the data distribution. The optimal rates of CRVs are achieved within the family of Random Permutation Codes (RPCs) developed in later chapters. RPCs randomly select one-of-many possible sequences that can represent the instance of the CRV. Specialized RPCs are given for the case of multisets, graphs, and partitions/clusterings, providing new algorithms for compression of databases, social networks, and web data in the JSON file format.

Figures

Figures reproduced from arXiv: 2411.14879 by the authors.

Figure 1.1
Figure 1.1. Binary trees with binary strings (left) and 2 [PITH_FULL_IMAGE:figures/full_fig_p024_1_1.png] view at source ↗
Figure 1.2
Figure 1.2. Binary tree for a prefix-free codebook {1, 00, 011} (left). Optimal codebook for |X | = 3 (right) [PITH_FULL_IMAGE:figures/full_fig_p027_1_2.png] view at source ↗
Figure 1.3
Figure 1.3. Percentage increase, with respect to the optimal, from using an extended uniform code. [PITH_FULL_IMAGE:figures/full_fig_p028_1_3.png] view at source ↗
Figures from the paper (10 more)
Figure 2.1
Figure 2.1. Figure 2.1: ANS state change under BB-ANS. Decoding proceeds in a similar fashion but in reverse order, s ′′, z = decode(s ′′′, PZ) (2.93) s ′ , x = decode(s ′′, PX | Z(· | z)), (2.94) s = encode(s ′ , QZ | X(· | x)). (2.95) BB-ANS defines codes over sequences x n ∈ X n by encod…
Figure 3.1
Figure 3.1. Figure 3.1: A non-simple directed graph (left) and simple undirected graph (right). [PITH_FULL_IMAGE:figures/full_fig_p053_3_1.png]
Figure 4.1
Figure 4.1. Figure 4.1: Example 4.3.2. Encoding M = {a, b, b} with Random Order Coding (ROC) [PITH_FULL_IMAGE:figures/full_fig_p060_4_1.png]
Figure 4.2
Figure 4.2. Figure 4.2: For the multiset {a, b, b, c, c, c, d, e}, on the top a schematic representation of the dy￾namic BST data structure which we use to represent the multiset, and on the bottom the intervals corresponding to each branch of the BST. at the root node, if s = 68 and i = 1,…
Figure 4.3
Figure 4.3. Figure 4.3: Left: Final compressed length is close to the information content for varying alphabet [PITH_FULL_IMAGE:figures/full_fig_p067_4_3.png]
Figure 4.4
Figure 4.4. Figure 4.4: Rate savings due to using our method to compress a multiset instead of treating it as [PITH_FULL_IMAGE:figures/full_fig_p068_4_4.png]
Figure 5.1
Figure 5.1. Figure 5.1: High-level description of our method, Random Cycle Coding (RCC). RCC encodes the [PITH_FULL_IMAGE:figures/full_fig_p072_5_1.png]
Figure 5.2
Figure 5.2. Figure 5.2: Maximum (left) and minimum (right) byte savings per element as a function of the [PITH_FULL_IMAGE:figures/full_fig_p078_5_2.png]
Figure 5.3
Figure 5.3. Figure 5.3: Median encoding plus decoding times, across 100 runs, for Random Order Coding [PITH_FULL_IMAGE:figures/full_fig_p079_5_3.png]
Figure 7.1
Figure 7.1. Figure 7.1: Varying the definition of the equivalence relation [PITH_FULL_IMAGE:figures/full_fig_p094_7_1.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

88 extracted references · 68 canonical work pages

  1. [1]

    An Algorithm for the Organization of Informa- tion

    Georgy Adelson-Velsky and Evgenii Landis. “An Algorithm for the Organization of Informa- tion”. In: Soviet Mathematics Doklady 3 (1962), pp. 1259–1263

    1962

  2. [2]

    Mixed membership stochastic blockmodels

    Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing. “Mixed membership stochastic blockmodels”. In: Advances in neural information processing systems 21 (2008)

    2008

  3. [3]

    A problem in combinations

    AC Aitken. “A problem in combinations”. In: Edinburgh Mathematical Notes 28 (1933), pp. xviii–xxiii

    1933

  4. [4]

    Additive quantization for extreme vector compres- sion

    Artem Babenko and Victor Lempitsky. “Additive quantization for extreme vector compres- sion”. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition . 2014, pp. 931–938

    2014

  5. [5]

    Edge-based sequential graph generation with recurrent neural networks

    Davide Bacciu, Alessio Micheli, and Marco Podda. “Edge-based sequential graph generation with recurrent neural networks”. In: Neurocomputing 416 (2020), pp. 177–189

    2020

  6. [6]

    Integer networks for data compression with latent-variable models

    Johannes Ball´ e, Nick Johnston, and David Minnen. “Integer networks for data compression with latent-variable models”. In: International Conference on Learning Representations. 2019

    2019

  7. [7]

    Predictive Coding for Loss- less Dataset Compression

    Madeleine Barowsky, Alexander Mariona, and Flavio P. Calmon. “Predictive Coding for Loss- less Dataset Compression”. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2021, pp. 1545–1549

    2021

  8. [8]

    Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms

    Rudolf Bayer. “Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms”. In: Acta Informatica 1.4 (1972), pp. 290–306

    1972

Show all 88 references
  1. [9]

    Idf++: Analyzing and improving integer discrete flows for lossless compression

    Rianne van den Berg, Alexey A Gritsenko, Mostafa Dehghani, Casper Kaae Sønderby, and Tim Salimans. “Idf++: Analyzing and improving integer discrete flows for lossless compression”. In: arXiv preprint arXiv:2006.12459 (2020)

    2020 arXiv

  2. [10]

    Probabilistic symmetries and invariant neural networks

    Benjamin Bloem-Reddy and Yee Whye Teh. “Probabilistic symmetries and invariant neural networks”. In: The Journal of Machine Learning Research 21.1 (2020), pp. 3535–3595

    2020

  3. [11]

    Random Walk Models, Preferential Attachment, and Se- quential Monte Carlo Methods for Analysis of Network Data

    Benjamin Michael Bloem-Reddy. “Random Walk Models, Preferential Attachment, and Se- quential Monte Carlo Methods for Analysis of Network Data”. PhD thesis. Columbia Univer- sity, 2017

    2017

  4. [12]

    Partition and Code: learning how to compress graphs

    Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael Bronstein. “Partition and Code: learning how to compress graphs”. In: Advances in Neural Information Processing Sys- tems 34 (2021), pp. 18603–18619

    2021

  5. [13]

    Convex optimization

    Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. 91 BIBLIOGRAPHY 92

    2004

  6. [14]

    Edge-exchangeable graphs and spar- sity

    Diana Cai, Trevor Campbell, and Tamara Broderick. “Edge-exchangeable graphs and spar- sity”. In: Advances in Neural Information Processing Systems 29 (2016)

    2016

  7. [15]

    Sparse graphs using exchangeable random measures

    Fran¸ cois Caron and Emily B Fox. “Sparse graphs using exchangeable random measures”. In: Journal of the Royal Statistical Society. Series B, Statistical Methodology 79.5 (2017), p. 1295

    2017

  8. [16]

    Approximate nearest neighbor search by resid- ual vector quantization

    Yongjian Chen, Tao Guan, and Cheng Wang. “Approximate nearest neighbor search by resid- ual vector quantization”. In: Sensors 10.12 (2010), pp. 11259–11273

    2010

  9. [17]

    On compressing social networks

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Pan- conesi, and Prabhakar Raghavan. “On compressing social networks”. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining . 2009, pp. 219–228

    2009

  10. [18]

    Elements of information theory

    Thomas M Cover. Elements of information theory . John Wiley & Sons, 1999

    1999

  11. [19]

    Edge exchangeable models for interaction networks

    Harry Crane and Walter Dempsey. “Edge exchangeable models for interaction networks”. In: Journal of the American Statistical Association 113.523 (2018), pp. 1311–1326

    2018

  12. [20]

    Hierarchical network models for exchange- able structured interaction processes

    Walter Dempsey, Brandon Oselio, and Alfred Hero. “Hierarchical network models for exchange- able structured interaction processes”. In: Journal of the American Statistical Association (2021), pp. 1–18

    2021

  13. [21]

    Asymmetric numeral systems

    Jarek Duda. “Asymmetric numeral systems”. In: arXiv preprint arXiv:0902.0271 (2009)

    2009 arXiv

  14. [22]

    Probability: theory and examples

    Rick Durrett. Probability: theory and examples . Vol. 49. Cambridge university press, 2019

    2019

  15. [23]

    On the evolution of random graphs

    Paul Erd˝ os, Alfr´ ed R´ enyi, et al. “On the evolution of random graphs”. In:Publ. Math. Inst. Hung. Acad. Sci 5.1 (1960), pp. 17–60

    1960

  16. [24]

    A New Data Structure for Cumulative Frequency Tables

    Peter M. Fenwick. “A New Data Structure for Cumulative Frequency Tables”. In: Software: Practice and Experience 24.3 (1994), pp. 327–336

    1994

  17. [25]

    On the Netto inversion number of a sequence

    Dominique Foata. “On the Netto inversion number of a sequence”. In: Proceedings of the American Mathematical Society 19.1 (1968), pp. 236–240

    1968

  18. [26]

    Bayesian Networks for Pattern Classification, Data Compression, and Chan- nel Coding

    Brendan J. Frey. “Bayesian Networks for Pattern Classification, Data Compression, and Chan- nel Coding”. PhD thesis. University of Toronto, 1997

    1997

  19. [27]

    Free energy coding

    Brendan J Frey and Geoffrey E Hinton. “Free energy coding”. In: Proceedings of Data Com- pression Conference-DCC’96. IEEE. 1996, pp. 73–81

    1996

  20. [28]

    GraphGen: a scalable approach to domain-agnostic labeled graph generation

    Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. “GraphGen: a scalable approach to domain-agnostic labeled graph generation”. In: Proceedings of The Web Conference 2020 . 2020, pp. 1253–1263

    2020

  21. [29]

    Tight and simple web graph compression for forward and reverse neighbor queries

    Szymon Grabowski and Wojciech Bieniecki. “Tight and simple web graph compression for forward and reverse neighbor queries”. In: Discrete Applied Mathematics 163 (2014), pp. 298– 306

    2014

  22. [30]

    Compressing multi- sets using tries

    Vincent Gripon, Michael Rabbat, Vitaly Skachek, and Warren J. Gross. “Compressing multi- sets using tries”. In: 2012 IEEE Information Theory Workshop . 2012, pp. 642–646

    2012

  23. [31]

    Deep mod- els of interactions across sets

    Jason Hartford, Devon Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh. “Deep mod- els of interactions across sets”. In: International Conference on Machine Learning . PMLR. 2018, pp. 1909–1918. BIBLIOGRAPHY 93

    2018

  24. [32]

    Bench- marking Generative Latent Variable Models for Speech

    Jakob D Havtorn, Lasse Borgholt, Søren Hauberg, Jes Frellsen, and Lars Maaløe. “Bench- marking Generative Latent Variable Models for Speech”. In: arXiv preprint arXiv:2202.12707 (2022)

    2022 arXiv

  25. [33]

    Stochastic blockmodels: First steps

    Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. “Stochastic blockmodels: First steps”. In: Social networks 5.2 (1983), pp. 109–137

    1983

  26. [34]

    Integer discrete flows and lossless compression

    Emiel Hoogeboom, Jorn Peters, Rianne Van Den Berg, and Max Welling. “Integer discrete flows and lossless compression”. In: Advances in Neural Information Processing Systems 32 (2019)

    2019

  27. [35]

    A method for the construction of minimum-redundancy codes

    David A Huffman. “A method for the construction of minimum-redundancy codes”. In: Pro- ceedings of the IRE 40.9 (1952), pp. 1098–1101

    1952

  28. [36]

    Resid- ual Quantization with Implicit Neural Codebooks

    Iris Huijben, Matthijs Douze, Matthew Muckley, Ruud van Sloun, and Jakob Verbeek. “Resid- ual Quantization with Implicit Neural Codebooks”. In:arXiv preprint arXiv:2401.14732 (2024)

    2024 arXiv

  29. [37]

    Product quantization for nearest neigh- bor search

    Herve Jegou, Matthijs Douze, and Cordelia Schmid. “Product quantization for nearest neigh- bor search”. In: IEEE transactions on pattern analysis and machine intelligence 33.1 (2010), pp. 117–128

    2010

  30. [38]

    Searching in one bil- lion vectors: re-rank with source coding

    Herv´ e J´ egou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. “Searching in one bil- lion vectors: re-rank with source coding”. In: 2011 IEEE International Conference on Acous- tics, Speech and Signal Processing (ICASSP) . IEEE. 2011, pp. 861–864

    2011

  31. [39]

    Lossless Data Compression with Bit-back Coding on Massive Smart Meter Data

    Heehun Jeong, Giup Seo, and Euiseok Hwang. “Lossless Data Compression with Bit-back Coding on Massive Smart Meter Data”. In: 2022 IEEE International Conference on Big Data (Big Data) . IEEE. 2022, pp. 6667–6669

    2022

  32. [40]

    Billion-scale similarity search with GPUs

    Jeff Johnson, Matthijs Douze, and Herv´ e J´ egou. “Billion-scale similarity search with GPUs”. In: IEEE Transactions on Big Data 7.3 (2019), pp. 535–547

    2019

  33. [41]

    An intro- duction to variational methods for graphical models

    Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. “An intro- duction to variational methods for graphical models”. In: Machine learning 37 (1999), pp. 183– 233

    1999

  34. [42]

    Variational diffusion models

    Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. “Variational diffusion models”. In: Advances in neural information processing systems 34 (2021), pp. 21696–21707

    2021

  35. [43]

    Auto-encoding variational bayes

    Diederik P Kingma and Max Welling. “Auto-encoding variational bayes”. In: arXiv preprint arXiv:1312.6114 (2013)

    2013 arXiv

  36. [44]

    Donald E. Knuth. The Art of Computer Programming, Volume 3 . Addison Wesley Longman Publishing Co., Inc., 1998

    1998

  37. [45]

    SNAP Datasets: Stanford Large Network Dataset Collection

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection . http://snap.stanford.edu/data. June 2014

    2014

  38. [46]

    Slashburn: Graph compression and mining beyond caveman communities

    Yongsub Lim, U Kang, and Christos Faloutsos. “Slashburn: Graph compression and mining beyond caveman communities”. In: IEEE Transactions on Knowledge and Data Engineering 26.12 (2014), pp. 3077–3089

    2014

  39. [47]

    Least squares quantization in PCM

    Stuart Lloyd. “Least squares quantization in PCM”. In: IEEE transactions on information theory 28.2 (1982), pp. 129–137. BIBLIOGRAPHY 94

    1982

  40. [48]

    Anomalous Edge Detection in Edge Exchangeable Social Network Models

    Rui Luo, Buddhika Nettasinghe, and Vikram Krishnamurthy. “Anomalous Edge Detection in Edge Exchangeable Social Network Models”. In: arXiv preprint arXiv:2109.12727 (2021)

    2021 arXiv

  41. [49]

    P´ olya urn models

    Hosam Mahmoud. P´ olya urn models. CRC press, 2008

    2008

  42. [50]

    Revisiting additive quantization

    Julieta Martinez, Joris Clement, Holger H Hoos, and James J Little. “Revisiting additive quantization”. In: Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II 14 . Springer. 2016, pp. 137–153

    2016

  43. [51]

    Hats: A hierarchical sequence-attention framework for inductive set-of-sets embeddings

    Changping Meng, Jiasen Yang, Bruno Ribeiro, and Jennifer Neville. “Hats: A hierarchical sequence-attention framework for inductive set-of-sets embeddings”. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . 2019, pp. 783–792

    2019

  44. [52]

    An Improved Data Structure for Cumulative Probability Tables

    Alistair Moffat. “An Improved Data Structure for Cumulative Probability Tables”. In: Soft- ware: Practice and Experience 29.7 (1999), pp. 647–659

    1999

  45. [53]

    Networks

    Mark Newman. Networks. Oxford university press, 2018

    2018

  46. [54]

    Exchangeable variable models

    Mathias Niepert and Pedro Domingos. “Exchangeable variable models”. In: International Con- ference on Machine Learning . PMLR. 2014, pp. 271–279

    2014

  47. [55]

    Generating diverse high-fidelity images with vq-vae-2

    Ali Razavi, Aaron van den Oord, and Oriol Vinyals. “Generating diverse high-fidelity images with vq-vae-2”. In: Advances in Neural Information Processing Systems . 2019, pp. 14866– 14876

    2019

  48. [56]

    Coding of sets of words

    Yuriy A. Reznik. “Coding of sets of words”. In: 2011 Data Compression Conference (DCC) . IEEE. 2011, pp. 43–52

    2011

  49. [57]

    Results of a prototype television bandwidth compression scheme

    A Harry Robinson and Colin Cherry. “Results of a prototype television bandwidth compression scheme”. In: Proceedings of the IEEE 55.3 (1967), pp. 356–364

    1967

  50. [58]

    The network data repository with interactive graph analytics and visualization

    Ryan Rossi and Nesreen Ahmed. “The network data repository with interactive graph analytics and visualization”. In: Proceedings of the AAAI conference on artificial intelligence . Vol. 29

  51. [59]

    Improving lossless compression rates via monte carlo bits-back coding

    Yangjun Ruan, Karen Ullrich, Daniel S Severo, James Townsend, Ashish Khisti, Arnaud Doucet, Alireza Makhzani, and Chris Maddison. “Improving lossless compression rates via monte carlo bits-back coding”. In: International Conference on Machine Learning . PMLR. 2021, pp. 9136–9147

    2021

  52. [60]

    PixelCNN++: Improving the PixelCNN with discretized logistic mixture likelihood and other modifications

    Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma. “PixelCNN++: Improving the PixelCNN with discretized logistic mixture likelihood and other modifications”. In: ICLR. 2017

    2017

  53. [61]

    Com- pressing multisets with large alphabets

    Daniel Severo, James Townsend, Ashish Khisti, Alireza Makhzani, and Karen Ullrich. “Com- pressing multisets with large alphabets”. In: IEEE Journal on Selected Areas in Information Theory (2023)

    2023

  54. [62]

    One-Shot Compres- sion of Large Edge-Exchangeable Graphs using Bits-Back Coding

    Daniel Severo, James Townsend, Ashish J Khisti, and Alireza Makhzani. “One-Shot Compres- sion of Large Edge-Exchangeable Graphs using Bits-Back Coding”. In: International Confer- ence on Machine Learning . PMLR. 2023, pp. 30633–30645. BIBLIOGRAPHY 95

    2023

  55. [63]

    Your dataset is a multiset and you should compress it like one

    Daniel Severo, James Townsend, Ashish J Khisti, Alireza Makhzani, and Karen 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

    2021

  56. [64]

    Model-based edge clustering

    Daniel K Sewell. “Model-based edge clustering”. In: Journal of Computational and Graphical Statistics 30.2 (2020), pp. 390–405

    2020

  57. [65]

    A mathematical theory of communication

    Claude Elwood Shannon. “A mathematical theory of communication”. In: The Bell system technical journal 27.3 (1948), pp. 379–423

    1948

  58. [66]

    Compressing combinatorial objects

    Christian Steinruecken. “Compressing combinatorial objects”. In: 2016 Data Compression Conference (DCC). IEEE. 2016, pp. 389–396

    2016

  59. [67]

    Compressing Sets and Multisets of Sequences

    Christian Steinruecken. “Compressing Sets and Multisets of Sequences”. In: IEEE Transactions on Information Theory 61.3 (2015), pp. 1485–1490

    2015

  60. [68]

    Lossless Data Compression

    Christian Steinruecken. “Lossless Data Compression”. PhD thesis. University of Cambridge, 2014

    2014

  61. [69]

    A tutorial on the range variant of asymmetric numeral systems

    James Townsend. “A tutorial on the range variant of asymmetric numeral systems”. In: arXiv preprint arXiv:2001.09186 (2020)

    2020 arXiv

  62. [70]

    Lossless compression with latent variable models

    James Townsend. “Lossless compression with latent variable models”. In: arXiv preprint arXiv:2104.10544 (2021)

    2021 arXiv

  63. [71]

    HiLLoC: Lossless Im- age Compression with Hierarchical Latent Variable Models

    James Townsend, Thomas Bird, Julius Kunze, and David Barber. “HiLLoC: Lossless Im- age Compression with Hierarchical Latent Variable Models”. In: International Conference on Learning Representations (ICLR). 2020

    2020

  64. [72]

    Practical lossless compression with latent variables using bits back coding

    James Townsend, Tom Bird, and David Barber. “Practical lossless compression with latent variables using bits back coding”. In: arXiv preprint arXiv:1901.04866 (2019)

    2019 arXiv

  65. [73]

    j-towns/craystack: ver- sion v0.2

    Jamie Townsend, Tom Bird, Julius Kunze, Daniel Severo, and Conzel. j-towns/craystack: ver- sion v0.2. Aug. 2021. doi: 10.5281/zenodo.5180977 . url: https://doi.org/10.5281/ zenodo.5180977

    2021 doi

  66. [74]

    Nvae: A deep hierarchical variational autoencoder

    Arash Vahdat and Jan Kautz. “Nvae: A deep hierarchical variational autoencoder”. In: NeurIPS. 2020

    2020

  67. [75]

    WaveNet: A Generative Model for Raw Audio

    Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. “WaveNet: A Generative Model for Raw Audio”. In: arXiv e-prints , arXiv:1609.03499 (Sept. 2016), arXiv:1609.03499. arXiv: 1609.03...

    2016 arXiv

  68. [77]

    Toward a source coding theory for sets

    Lav R Varshney and Vivek K Goyal. “Toward a source coding theory for sets”. In: Data Compression Conference (DCC’06). IEEE. 2006, pp. 13–22

    2006

  69. [78]

    Zuckerli: A new com- pressed representation for graphs

    Luca Versari, Iulia-Maria Comsa, Alessio Conte, and Roberto Grossi. “Zuckerli: A new com- pressed representation for graphs”. In: IEEE Access 8 (2020), pp. 219233–219243

    2020

  70. [79]

    Nonparametric Network Models for Link Prediction

    Sinead A. Williamson. “Nonparametric Network Models for Link Prediction”. In: Journal of Machine Learning Research 17.202 (2016), pp. 1–21. url: http://jmlr.org/papers/v17/16- 032.html. BIBLIOGRAPHY 96

    2016

  71. [80]

    Arithmetic coding for data compression

    Ian H Witten, Radford M Neal, and John G Cleary. “Arithmetic coding for data compression”. In: Communications of the ACM 30.6 (1987), pp. 520–540

    1987

  72. [81]

    Compression and predictive distributions for large alpha- bet iid and Markov models

    Xiao Yang and Andrew R. Barron. “Compression and predictive distributions for large alpha- bet iid and Markov models”. In: 2014 IEEE International Symposium on Information Theory . 2014, pp. 2504–2508

    2014

  73. [82]

    Minimax compression and large alphabet approximation through poissonization and tilting

    Xiao Yang and Andrew R. Barron. “Minimax compression and large alphabet approximation through poissonization and tilting”. In:IEEE Transactions on Information Theory 63.5 (2017), pp. 2866–2884

    2017

  74. [83]

    Improving inference for neural image com- pression

    Yibo Yang, Robert Bamler, and Stephan Mandt. “Improving inference for neural image com- pression”. In: arXiv preprint arXiv:2006.04240 (2020)

    2020 arXiv

  75. [84]

    An Introduction to Neural Data Compression

    Yibo Yang, Stephan Mandt, and Lucas Theis. “An Introduction to Neural Data Compression”. In: Foundations and Trends® in Computer Graphics and Vision 15.2 (2023), 113–200. issn: 1572-2759. doi: 10.1561/0600000107. url: http://dx.doi.org/10.1561/0600000107

    2023 doi

  76. [85]

    Graphrnn: Gen- erating realistic graphs with deep auto-regressive models

    Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. “Graphrnn: Gen- erating realistic graphs with deep auto-regressive models”. In: International conference on machine learning. PMLR. 2018, pp. 5708–5717

    2018

  77. [86]

    Pool Compression for Undirected Graphs

    Muhammad Irfan Yousuf and Suhyun Kim. “Pool Compression for Undirected Graphs”. In: IEEE Access (2022)

    2022

  78. [87]

    Deep sets

    Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. “Deep sets”. In: Advances in neural information processing systems 30 (2017)

    2017

  79. [88]

    Node-level community detection within edge exchange- able models for interaction processes

    Yuhua Zhang and Walter Dempsey. “Node-level community detection within edge exchange- able models for interaction processes”. In: arXiv preprint arXiv:2208.08539 (2022)

    2022 arXiv

  80. [89]

    A survey on deep graph generation: Methods and applications

    Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. “A survey on deep graph generation: Methods and applications”. In:arXiv preprint arXiv:2203.06714 (2022)

    2022 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.