Compressing Hypergraphs using Suffix Sorting

Enno Adler; Rita Hartel; Stefan B\"ottcher

arxiv: 2506.05023 · v2 · submitted 2025-06-05 · 💻 cs.DS

Compressing Hypergraphs using Suffix Sorting

Enno Adler , Stefan B\"ottcher , Rita Hartel This is my paper

Pith reviewed 2026-05-19 11:11 UTC · model grok-4.3

classification 💻 cs.DS

keywords hypergraph compressionsuffix sortingsuccinct data structuresneighbor queriesincidence queriesdata compressionhypergraph representation

0 comments

The pith

HyperCSA uses suffix sorting to compress hypergraphs to 26-79 percent of original size while supporting faster neighbor queries.

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

The paper introduces HyperCSA, a compression approach for hypergraphs that adapts suffix sorting to create a succinct representation. Hypergraphs capture multi-way relations such as group memberships or co-authorships, so compact storage and fast access matter when datasets grow large. The method is designed to keep exact support for standard operations including neighbor and incidence queries. Experiments on real-world hypergraphs show better compression than prior techniques on every large instance tested, plus the ability to handle bigger collections and query speeds improved by factors of 6 to 40.

Core claim

HyperCSA is a succinct representation of a hypergraph obtained by applying suffix sorting to an encoding of its incidences, which achieves compression ratios of 26 to 79 percent of the original file size on real-world data, scales to larger instances than existing methods, and answers neighbor queries between 6 and 40 times faster than both standard structures and other compressed formats while preserving exact query semantics.

What carries the argument

The HyperCSA structure, a compressed suffix array built over a linearized representation of hyperedges and vertices that directly supports incidence and neighbor queries on the succinct form without full decompression.

If this is right

Hypergraphs can be stored using substantially less space than existing compression schemes on large real-world instances.
The same representation scales to datasets too large for prior succinct hypergraph methods.
Neighbor queries become 6 to 40 times faster than both plain data structures and other compressed alternatives.
Applications that rely on repeated neighbor lookups, such as recommendation or social-network analysis, can operate on bigger hypergraphs within fixed memory limits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same suffix-sorting idea might apply directly to other higher-order structures such as simplicial complexes or set systems.
If construction time remains practical, the approach could be integrated into hypergraph database engines to improve both storage and query latency.
Dynamic versions that support edge insertions while keeping the suffix order updated would further broaden the range of usable applications.

Load-bearing premise

The suffix-sorted encoding of hyperedge incidences can be constructed and queried while preserving every original incidence relation exactly, with no hidden information loss or prohibitive build cost.

What would settle it

A direct comparison on any real-world hypergraph where the set of neighbors returned by HyperCSA differs from the set returned by an uncompressed incidence list.

Figures

Figures reproduced from arXiv: 2506.05023 by Enno Adler, Rita Hartel, Stefan B\"ottcher.

**Figure 1.** Figure 1: The example hypergraph H = ({0, 1, 2, 3, 4}, {{0, 1, 2, 3}, {1, 2, 3}, {2}, {0, 1, 2, 4}, {2}}) with 5 hyperedges. 0 1 4 2 3 We define the degree(v) = |{e ∈ EG : v ∈ e}| and MG = P e∈EG P rank(e) = v∈V degree(v). For the example hypergraph H, degree(2) = 5 and MH = 13. We define a string T of length |T| over an alphabet Σ as a sequence T = T[0] · T[1] · · · T[|T| − 1] of characters T[i] ∈ Σ for i < |T|. We… view at source ↗

**Figure 2.** Figure 2: Example for HyperCSA data structure. It contains the edges [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Hypergraph compression sizes in relation to the original file size. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Query time of contains(v0) query, which returns all neighbors of node v0. Missing datapoints indicate that the method failed to complete in decent time. SeCo HoCo SeBi HoBi MaAn WaTr TrCl CpFr StAn AmRe CoOr 10−1 100 101 102 103 104 runtime in milliseconds per query (logarithmic) HyperCSA Array-vanilla Array-V Array-E Array-V&E incidence list incidence matrix Second, we investigate resource costs of the co… view at source ↗

**Figure 5.** Figure 5: Query times of contains(v0, . . . vk−1) query on the largest dataset CoOr. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 102 103 length of contains query k runtime in milliseconds per query (logarithmic) HyperCSA Array-vanilla incidence list Second, [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗

read the original abstract

Hypergraphs model complex, non-binary relationships like co-authorships, social group memberships, and recommendations. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26% to 79% of the original file size on real-world hypergraphs - outperforming existing methods on all large hypergraphs in our experiments. Additionally, HyperCSA scales to larger datasets than existing approaches. Furthermore, for common real-world hypergraphs, HyperCSA evaluates neighbor queries 6 to 40 times faster than both standard data structures and other hypergraph compression approaches.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

HyperCSA turns hyperedges into a sequence for suffix-array compression and reports good ratios plus faster queries, but the exact query path needs checking to confirm no hidden space or time costs.

read the letter

The main point is that this paper serializes hyperedges and builds a compressed suffix array on the result to get both smaller storage and quicker neighbor lookups than existing hypergraph compressors. They test on real data and show sizes between 26 and 79 percent of the original, with the method scaling past prior tools and delivering 6- to 40-fold speedups on common neighbor queries. That combination is the actual new piece: prior succinct representations for hypergraphs usually trade query speed for space or vice versa, and this one claims to improve both at once on practical instances. The experiments use real-world hypergraphs rather than synthetic ones, which adds some weight to the numbers. Credit is due for shipping concrete performance figures instead of just asymptotic claims. The soft spot is exactly the one the stress test flags. Standard CSA constructions store the suffix array, inverse, and often LCP or sampled pointers; if any of those sit outside the succinct part or if answering an incidence query requires scanning or decompressing, the reported space bound and the speed claim both become harder to believe. The abstract gives no concrete description of how vertices and hyperedges are turned into symbols or how a random-access neighbor list is extracted from the CSA without extra tables. If the full paper shows a construction that keeps the auxiliary data inside the same space budget and still answers queries in sublinear time, the results stand. If not, the speedups may come from a different implementation detail that is not yet clear. This work is for people who build or use data structures for hypergraphs in social networks, co-authorship graphs, or recommendation systems. A reader who already works with succinct representations or compressed indexes will get the most out of it. The paper is coherent on its own terms and presents falsifiable empirical claims, so it deserves a serious referee even if the query details need tightening in revision.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces HyperCSA, a compression method for hypergraphs that serializes the structure into a form amenable to suffix sorting and constructs a compressed suffix array (CSA) representation. The approach claims to support standard neighbor and incidence queries directly on the succinct structure. Experiments on real-world hypergraphs report compression ratios of 26% to 79% of the original file size (outperforming existing methods on all large instances), improved scalability to larger datasets, and neighbor query evaluation that is 6 to 40 times faster than both standard data structures and other hypergraph compressors.

Significance. If the central claims hold, the work would offer a practical succinct representation for hypergraphs that simultaneously reduces space and accelerates queries, which is valuable for applications involving large-scale co-authorship networks, social groups, and recommendation systems. Adapting suffix-array techniques from stringology to hypergraph incidence lists is a novel cross-domain idea, and the empirical results on real data provide concrete evidence of practicality. The absence of free parameters in the core construction (as implied by the method description) and the focus on query-preserving compression are strengths.

major comments (2)

[§3 and §4] §3 (Construction) and §4 (Query Algorithms): The description of how the serialized hyperedge list is mapped to symbols for suffix sorting and how random-access neighbor queries are resolved inside the CSA is insufficiently detailed. Standard CSA constructions require the suffix array, inverse suffix array, and often LCP or sampled pointers; it is unclear whether these are stored in compressed form or if query resolution involves linear scans or auxiliary structures that would affect the reported space bounds and 6-40× speedup.
[§5] §5 (Experimental Evaluation): The performance numbers (compression ratios, query times) are given without explicit specification of the exact baseline implementations, hypergraph dataset selection criteria, number of runs for timing, or error bars. This makes it difficult to assess whether the outperformance on large hypergraphs and the query speedup claims are robust.

minor comments (2)

[Abstract] The abstract and introduction would benefit from a short paragraph clarifying the precise hypergraph representation (e.g., incidence list vs. edge list) assumed as input.
[§2] Notation for the alphabet size and symbol mapping in the suffix array construction should be introduced earlier and used consistently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of the work's significance and for the constructive major comments. We address each point below and will incorporate clarifications to improve the manuscript.

read point-by-point responses

Referee: [§3 and §4] §3 (Construction) and §4 (Query Algorithms): The description of how the serialized hyperedge list is mapped to symbols for suffix sorting and how random-access neighbor queries are resolved inside the CSA is insufficiently detailed. Standard CSA constructions require the suffix array, inverse suffix array, and often LCP or sampled pointers; it is unclear whether these are stored in compressed form or if query resolution involves linear scans or auxiliary structures that would affect the reported space bounds and 6-40× speedup.

Authors: We appreciate the referee's request for greater precision. In the revised manuscript we will expand Sections 3 and 4 with an explicit description of the symbol alphabet construction from the serialized incidence lists and a step-by-step account of how neighbor and incidence queries are answered inside the CSA. We will state that the implementation follows a standard compressed suffix array (using compressed representations of the suffix array, inverse suffix array, and sampled LCP array via wavelet trees or equivalent structures) and that all random-access operations are performed with rank/select primitives in logarithmic time without linear scans or additional uncompressed auxiliary tables. These clarifications will confirm that the reported space bounds and query speedups remain unchanged. revision: yes
Referee: [§5] §5 (Experimental Evaluation): The performance numbers (compression ratios, query times) are given without explicit specification of the exact baseline implementations, hypergraph dataset selection criteria, number of runs for timing, or error bars. This makes it difficult to assess whether the outperformance on large hypergraphs and the query speedup claims are robust.

Authors: We agree that additional experimental details will strengthen reproducibility. In the revision we will add a dedicated paragraph specifying the exact baseline codebases and versions, the precise selection criteria and sources for each hypergraph dataset, the number of independent timing runs performed for each query measurement, and error bars (or standard deviations) on the reported query times. These additions will allow readers to better evaluate the robustness of the compression and speedup results. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical claims rest on external real-world hypergraphs

full rationale

The paper presents HyperCSA as an algorithmic construction that serializes hyperedges for suffix-array compression while claiming direct support for neighbor and incidence queries. All reported compression ratios (26-79%), scalability, and 6-40x query speedups are measured against independent external datasets rather than quantities defined in terms of the method's own parameters or self-referential fits. No equation or claim reduces by construction to a prior input, self-citation chain, or renamed empirical pattern; the central representation and query support are presented as properties of the suffix-sorting construction evaluated on outside data.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach relies on standard suffix-array construction and hypergraph incidence representations that are assumed to transfer directly; no new mathematical axioms or invented entities are introduced in the abstract.

axioms (1)

standard math Suffix sorting algorithms remain correct and efficient when applied to the chosen hypergraph encoding.
The method depends on established suffix-array primitives working as expected on the hypergraph-derived strings.

pith-pipeline@v0.9.0 · 5648 in / 1266 out tokens · 48617 ms · 2026-05-19T11:11:51.813116+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

HyperCSA builds on Sadakane’s Compressed Suffix Array (CSA) [19] and is inspired by RDFCSA [1]. ... we adjust Ψ to ensure that repeated applications of Ψ cycles within the same edge e ∈ EG.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Ψ can be stored in space proportional to the zero-order empirical entropy of T ... MG H0(T) + O(MG log(H0(T)))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 1 internal anchor

[1]

In: 2016 Data Compression Conference, DCC 2016, Snow- bird, UT, USA, March 30 - April 1, 2016

Cerdeira-Pena, A., Fariña, A., Fernández, J.D., Martínez-Prieto, M.A.: Self- indexing RDF archives. In: 2016 Data Compression Conference, DCC 2016, Snow- bird, UT, USA, March 30 - April 1, 2016. pp. 526–535 (2016). https://doi.org/10. 1109/DCC.2016.40, https://doi.org/10.1109/DCC.2016.40

work page doi:10.1109/dcc.2016.40 2016
[2]

Science Advances (2021)

Chodrow, P.S., Veldt, N., Benson, A.R.: Hypergraph clustering: from blockmodels to modularity. Science Advances (2021)

work page 2021
[3]

Clark, D.: Compact PAT trees (1997)

work page 1997
[4]

Dai, Q., Gao, Y.: Mathematical Foundations of Hypergraph, pp. 19–40. Springer Nature Singapore, Singapore (2023). https://doi.org/10.1007/978-981-99-0185-2_ 2, https://doi.org/10.1007/978-981-99-0185-2_2

work page doi:10.1007/978-981-99-0185-2_ 2023
[5]

IEEE Transactions on Mul- timedia 16(3), 796–812 (2014)

Fang, Q., Sang, J., Xu, C., Rui, Y.: Topic-sensitive influencer mining in interest- based social media networks via hypergraph learning. IEEE Transactions on Mul- timedia 16(3), 796–812 (2014)

work page 2014
[6]

ACM Trans

Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Trans. Algo- rithms 7(1), 10:1–10:21 (2010). https://doi.org/10.1145/1868237.1868248, https: //doi.org/10.1145/1868237.1868248

work page doi:10.1145/1868237.1868248 2010
[7]

Random hypergraphs and their applications

Ghoshal, G., Zlatic, V., Caldarelli, G., Newman, M.E.J.: Random hypergraphs and their applications. CoRRabs/0903.0419 (2009), http://arxiv.org/abs/0903.0419

work page internal anchor Pith review Pith/arXiv arXiv 2009
[8]

In: 13th International Symposium on Experimental Algorithms, (SEA 2014)

Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: Plug and play with succinct data structures. In: 13th International Symposium on Experimental Algorithms, (SEA 2014). pp. 326–337 (2014)

work page 2014
[9]

https://doi.org/10.1002/j.1538-7305.1982.tb03439.x

Goldstein, A.J.: Database systems: A directed hypergraph database: A model for thelocallooptelephoneplant.TheBellSystemTechnicalJournal 61(9),2529–2554 (1982). https://doi.org/10.1002/j.1538-7305.1982.tb03439.x

work page doi:10.1002/j.1538-7305.1982.tb03439.x 1982
[10]

In: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval

Hu, T., Xiong, H., Zhou, W., Sung, S.Y., Luo, H.: Hypergraph partitioning for document clustering: a unified clique perspective. In: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. p. 871–872. SIGIR ’08, Association for Computing Ma- chinery, New York, NY, USA (2008). https://doi.org/...

work page doi:10.1145/1390334.1390548 2008
[11]

In: 2015 IEEE International Conference on Data Mining

Huang, J., Zhang, R., Yu, J.X.: Scalable hypergraph learning and processing. In: 2015 IEEE International Conference on Data Mining. pp. 775–780 (2015). https: //doi.org/10.1109/ICDM.2015.33

work page doi:10.1109/icdm.2015.33 2015
[12]

In: 2008 Eighth IEEE International Conference on Data Mining

Hwang, T., Tian, Z., Kuangy, R., Kocher, J.P.: Learning on weighted hypergraphs to integrate protein interactions and gene expressions for cancer outcome predic- tion. In: 2008 Eighth IEEE International Conference on Data Mining. pp. 293–302 (2008). https://doi.org/10.1109/ICDM.2008.37

work page doi:10.1109/icdm.2008.37 2008
[13]

In: 2018 IEEE High Performance extreme Computing Conference (HPEC)

Jenkins, L., Bhuiyan, T., Harun, S., Lightsey, C., Mentgen, D., Aksoy, S., Stavc- nger, T., Zalewski, M., Medal, H., Joslyn, C.: Chapel hypergraph library (chgl). In: 2018 IEEE High Performance extreme Computing Conference (HPEC). pp. 1–6 (2018). https://doi.org/10.1109/HPEC.2018.8547520

work page doi:10.1109/hpec.2018.8547520 2018
[14]

In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining

Li, L., Li, T.: News recommendation via hypergraph learning: encapsulation of user behavior and news content. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. p. 305–314. WSDM ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/ 2433396.2433436, https://doi.org/10.1145/2433396.2433436

work page doi:10.1145/2433396.2433436 2013
[15]

Pattern Recognition 44(10), 2255–2262 (2011)

Liu, Q., Huang, Y., Metaxas, D.N.: Hypergraph with sampling for image retrieval. Pattern Recognition 44(10), 2255–2262 (2011). https://doi.org/https://doi.org/ 14 Adler et al. 10.1016/j.patcog.2010.07.014, https://www.sciencedirect.com/science/article/pii/ S0031320310003535, semi-Supervised Learning for Visual Content Analysis and Understanding

work page doi:10.1016/j.patcog.2010.07.014 2011
[16]

IEEE Trans

Liu, Y., Luo, Q., Xiao, M., Yu, D., Chen, H., Cheng, X.: Reordering and compression for hypergraph processing. IEEE Trans. Computers 73(6), 1486– 1499 (2024). https://doi.org/10.1109/TC.2024.3377915, https://doi.org/10.1109/ TC.2024.3377915

work page doi:10.1109/tc.2024.3377915 2024
[17]

In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algo- rithms, 22-24 January 1990, San Francisco, California, USA

Manber, U., Myers, G.: Suffix Arrays: A New Method for On-Line String Searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algo- rithms, 22-24 January 1990, San Francisco, California, USA. pp. 319–327 (1990), http://dl.acm.org/citation.cfm?id=320176.320218

work page arXiv 1990
[18]

F1000Research10(33) (2021)

Mölder, F., Jablonski, K., Letcher, B., Hall, M., Tomkins-Tinch, C., Sochat, V., Forster, J., Lee, S., Twardziok, S., Kanitz, A., Wilm, A., Holtgrewe, M., Rahmann, S., Nahnsen, S., Köster, J.: Sustainable data analysis with snakemake [version 2; peer review: 2 approved]. F1000Research10(33) (2021). https://doi.org/10.12688/ f1000research.29032.2

work page 2021
[19]

Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294–313 (2003). https://doi.org/10.1016/S0196-6774(03)00087- 7, https://doi.org/10.1016/S0196-6774(03)00087-7

work page doi:10.1016/s0196-6774(03)00087- 2003
[20]

Schlag, S., Heuer, T., Gottesbüren, L., Akhremtsev, Y., Schulz, C., Sanders, P.: High-quality hypergraph partitioning. ACM J. Exp. Algorithmics27 (Feb 2023). https://doi.org/10.1145/3529090, https://doi.org/10.1145/3529090

work page doi:10.1145/3529090 2023
[21]

In: PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, February 22-26, 2020

Shun, J.: Practical parallel hypergraph algorithms. In: PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, February 22-26, 2020. pp. 232–249 (2020). https://doi. org/10.1145/3332466.3374527, https://doi.org/10.1145/3332466.3374527

work page doi:10.1145/3332466.3374527 2020
[22]

In: Proceedings of the 16th ACM International Con- ference on Multimedia

Tan, H.K., Ngo, C.W., Wu, X.: Modeling video hyperlinks with hypergraph for web video reranking. In: Proceedings of the 16th ACM International Con- ference on Multimedia. p. 659–662. MM ’08, Association for Computing Ma- chinery, New York, NY, USA (2008). https://doi.org/10.1145/1459359.1459453, https://doi.org/10.1145/1459359.1459453

work page doi:10.1145/1459359.1459453 2008
[23]

ACM Trans

Tan, S., Bu, J., Chen, C., Xu, B., Wang, C., He, X.: Using rich social media infor- mation for music recommendation via hypergraph model. ACM Trans. Multime- dia Comput. Commun. Appl.7S(1) (Nov 2011). https://doi.org/10.1145/2037676. 2037679, https://doi.org/10.1145/2037676.2037679

work page doi:10.1145/2037676 2011
[24]

In: Proceedings of the AAAI Conference on Artificial Intelligence

Tan,S.,Guan,Z.,Cai,D.,Qin,X.,Bu,J.,Chen,C.:Mappingusersacrossnetworks by manifold alignment on hypergraph. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 28 (2014)

work page 2014
[25]

In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Veldt, N., Benson, A.R., Kleinberg, J.: Minimizing localized ratio cut objectives in hypergraphs. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press (2020)

work page 2020
[26]

Medaglia

Vigna, S.: Broadword implementation of rank/select queries. In: Experimental Al- gorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings. pp. 154–168 (2008). https://doi.org/10.1007/978-3- 540-68552-4_12, https://doi.org/10.1007/978-3-540-68552-4_12

work page doi:10.1007/978-3- 2008
[27]

In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics

Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. MDS ’12, Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2350190.2350193, https://doi.org/10.1145/ 2350190.2350193 Compressing Hypergraphs using Suffix Sortin...

work page doi:10.1145/2350190.2350193 2012

[1] [1]

In: 2016 Data Compression Conference, DCC 2016, Snow- bird, UT, USA, March 30 - April 1, 2016

Cerdeira-Pena, A., Fariña, A., Fernández, J.D., Martínez-Prieto, M.A.: Self- indexing RDF archives. In: 2016 Data Compression Conference, DCC 2016, Snow- bird, UT, USA, March 30 - April 1, 2016. pp. 526–535 (2016). https://doi.org/10. 1109/DCC.2016.40, https://doi.org/10.1109/DCC.2016.40

work page doi:10.1109/dcc.2016.40 2016

[2] [2]

Science Advances (2021)

Chodrow, P.S., Veldt, N., Benson, A.R.: Hypergraph clustering: from blockmodels to modularity. Science Advances (2021)

work page 2021

[3] [3]

Clark, D.: Compact PAT trees (1997)

work page 1997

[4] [4]

Dai, Q., Gao, Y.: Mathematical Foundations of Hypergraph, pp. 19–40. Springer Nature Singapore, Singapore (2023). https://doi.org/10.1007/978-981-99-0185-2_ 2, https://doi.org/10.1007/978-981-99-0185-2_2

work page doi:10.1007/978-981-99-0185-2_ 2023

[5] [5]

IEEE Transactions on Mul- timedia 16(3), 796–812 (2014)

Fang, Q., Sang, J., Xu, C., Rui, Y.: Topic-sensitive influencer mining in interest- based social media networks via hypergraph learning. IEEE Transactions on Mul- timedia 16(3), 796–812 (2014)

work page 2014

[6] [6]

ACM Trans

Ferragina, P., Venturini, R.: The compressed permuterm index. ACM Trans. Algo- rithms 7(1), 10:1–10:21 (2010). https://doi.org/10.1145/1868237.1868248, https: //doi.org/10.1145/1868237.1868248

work page doi:10.1145/1868237.1868248 2010

[7] [7]

Random hypergraphs and their applications

Ghoshal, G., Zlatic, V., Caldarelli, G., Newman, M.E.J.: Random hypergraphs and their applications. CoRRabs/0903.0419 (2009), http://arxiv.org/abs/0903.0419

work page internal anchor Pith review Pith/arXiv arXiv 2009

[8] [8]

In: 13th International Symposium on Experimental Algorithms, (SEA 2014)

Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: Plug and play with succinct data structures. In: 13th International Symposium on Experimental Algorithms, (SEA 2014). pp. 326–337 (2014)

work page 2014

[9] [9]

https://doi.org/10.1002/j.1538-7305.1982.tb03439.x

Goldstein, A.J.: Database systems: A directed hypergraph database: A model for thelocallooptelephoneplant.TheBellSystemTechnicalJournal 61(9),2529–2554 (1982). https://doi.org/10.1002/j.1538-7305.1982.tb03439.x

work page doi:10.1002/j.1538-7305.1982.tb03439.x 1982

[10] [10]

In: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval

Hu, T., Xiong, H., Zhou, W., Sung, S.Y., Luo, H.: Hypergraph partitioning for document clustering: a unified clique perspective. In: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. p. 871–872. SIGIR ’08, Association for Computing Ma- chinery, New York, NY, USA (2008). https://doi.org/...

work page doi:10.1145/1390334.1390548 2008

[11] [11]

In: 2015 IEEE International Conference on Data Mining

Huang, J., Zhang, R., Yu, J.X.: Scalable hypergraph learning and processing. In: 2015 IEEE International Conference on Data Mining. pp. 775–780 (2015). https: //doi.org/10.1109/ICDM.2015.33

work page doi:10.1109/icdm.2015.33 2015

[12] [12]

In: 2008 Eighth IEEE International Conference on Data Mining

Hwang, T., Tian, Z., Kuangy, R., Kocher, J.P.: Learning on weighted hypergraphs to integrate protein interactions and gene expressions for cancer outcome predic- tion. In: 2008 Eighth IEEE International Conference on Data Mining. pp. 293–302 (2008). https://doi.org/10.1109/ICDM.2008.37

work page doi:10.1109/icdm.2008.37 2008

[13] [13]

In: 2018 IEEE High Performance extreme Computing Conference (HPEC)

Jenkins, L., Bhuiyan, T., Harun, S., Lightsey, C., Mentgen, D., Aksoy, S., Stavc- nger, T., Zalewski, M., Medal, H., Joslyn, C.: Chapel hypergraph library (chgl). In: 2018 IEEE High Performance extreme Computing Conference (HPEC). pp. 1–6 (2018). https://doi.org/10.1109/HPEC.2018.8547520

work page doi:10.1109/hpec.2018.8547520 2018

[14] [14]

In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining

Li, L., Li, T.: News recommendation via hypergraph learning: encapsulation of user behavior and news content. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining. p. 305–314. WSDM ’13, Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/ 2433396.2433436, https://doi.org/10.1145/2433396.2433436

work page doi:10.1145/2433396.2433436 2013

[15] [15]

Pattern Recognition 44(10), 2255–2262 (2011)

Liu, Q., Huang, Y., Metaxas, D.N.: Hypergraph with sampling for image retrieval. Pattern Recognition 44(10), 2255–2262 (2011). https://doi.org/https://doi.org/ 14 Adler et al. 10.1016/j.patcog.2010.07.014, https://www.sciencedirect.com/science/article/pii/ S0031320310003535, semi-Supervised Learning for Visual Content Analysis and Understanding

work page doi:10.1016/j.patcog.2010.07.014 2011

[16] [16]

IEEE Trans

Liu, Y., Luo, Q., Xiao, M., Yu, D., Chen, H., Cheng, X.: Reordering and compression for hypergraph processing. IEEE Trans. Computers 73(6), 1486– 1499 (2024). https://doi.org/10.1109/TC.2024.3377915, https://doi.org/10.1109/ TC.2024.3377915

work page doi:10.1109/tc.2024.3377915 2024

[17] [17]

In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algo- rithms, 22-24 January 1990, San Francisco, California, USA

Manber, U., Myers, G.: Suffix Arrays: A New Method for On-Line String Searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algo- rithms, 22-24 January 1990, San Francisco, California, USA. pp. 319–327 (1990), http://dl.acm.org/citation.cfm?id=320176.320218

work page arXiv 1990

[18] [18]

F1000Research10(33) (2021)

Mölder, F., Jablonski, K., Letcher, B., Hall, M., Tomkins-Tinch, C., Sochat, V., Forster, J., Lee, S., Twardziok, S., Kanitz, A., Wilm, A., Holtgrewe, M., Rahmann, S., Nahnsen, S., Köster, J.: Sustainable data analysis with snakemake [version 2; peer review: 2 approved]. F1000Research10(33) (2021). https://doi.org/10.12688/ f1000research.29032.2

work page 2021

[19] [19]

Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294–313 (2003). https://doi.org/10.1016/S0196-6774(03)00087- 7, https://doi.org/10.1016/S0196-6774(03)00087-7

work page doi:10.1016/s0196-6774(03)00087- 2003

[20] [20]

Schlag, S., Heuer, T., Gottesbüren, L., Akhremtsev, Y., Schulz, C., Sanders, P.: High-quality hypergraph partitioning. ACM J. Exp. Algorithmics27 (Feb 2023). https://doi.org/10.1145/3529090, https://doi.org/10.1145/3529090

work page doi:10.1145/3529090 2023

[21] [21]

In: PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, February 22-26, 2020

Shun, J.: Practical parallel hypergraph algorithms. In: PPoPP ’20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, February 22-26, 2020. pp. 232–249 (2020). https://doi. org/10.1145/3332466.3374527, https://doi.org/10.1145/3332466.3374527

work page doi:10.1145/3332466.3374527 2020

[22] [22]

In: Proceedings of the 16th ACM International Con- ference on Multimedia

Tan, H.K., Ngo, C.W., Wu, X.: Modeling video hyperlinks with hypergraph for web video reranking. In: Proceedings of the 16th ACM International Con- ference on Multimedia. p. 659–662. MM ’08, Association for Computing Ma- chinery, New York, NY, USA (2008). https://doi.org/10.1145/1459359.1459453, https://doi.org/10.1145/1459359.1459453

work page doi:10.1145/1459359.1459453 2008

[23] [23]

ACM Trans

Tan, S., Bu, J., Chen, C., Xu, B., Wang, C., He, X.: Using rich social media infor- mation for music recommendation via hypergraph model. ACM Trans. Multime- dia Comput. Commun. Appl.7S(1) (Nov 2011). https://doi.org/10.1145/2037676. 2037679, https://doi.org/10.1145/2037676.2037679

work page doi:10.1145/2037676 2011

[24] [24]

In: Proceedings of the AAAI Conference on Artificial Intelligence

Tan,S.,Guan,Z.,Cai,D.,Qin,X.,Bu,J.,Chen,C.:Mappingusersacrossnetworks by manifold alignment on hypergraph. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 28 (2014)

work page 2014

[25] [25]

In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Veldt, N., Benson, A.R., Kleinberg, J.: Minimizing localized ratio cut objectives in hypergraphs. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press (2020)

work page 2020

[26] [26]

Medaglia

Vigna, S.: Broadword implementation of rank/select queries. In: Experimental Al- gorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings. pp. 154–168 (2008). https://doi.org/10.1007/978-3- 540-68552-4_12, https://doi.org/10.1007/978-3-540-68552-4_12

work page doi:10.1007/978-3- 2008

[27] [27]

In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics

Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. MDS ’12, Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2350190.2350193, https://doi.org/10.1145/ 2350190.2350193 Compressing Hypergraphs using Suffix Sortin...

work page doi:10.1145/2350190.2350193 2012