{"ID":2824282,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23345","arxiv_id":"2512.23345","title":"HL-index: Fast Reachability Query in Hypergraphs","abstract":"Reachability in hypergraphs is essential for modeling complex groupwise interactions in real-world applications such as co-authorship, social network, and biological analysis, where relationships go beyond pairwise interactions. In this paper, we introduce the notion of s-reachability, where two vertices are s-reachable if there exists a sequence of hyperedges (i.e., a walk) connecting them, such that each pair of consecutive hyperedges shares at least s vertices. Moreover, we define the max-reachability query as a generalized form of the s-reachability problem, which aims to find the largest value of s that allows one vertex to reach another. To answer max-reachability queries in hypergraphs, we first analyze limitations of the existing vertex-to-vertex and hyperedge-to-hyperedge indexing techniques. We then introduce the HL-index, a compact vertex-to-hyperedge index tailored for the max-reachability problem. To both efficiently and effectively construct a minimal HL-index, we develop a fast covering relationship detection method to eliminate fruitless hypergraph traversals during index construction. A lightweight neighbor-index is further proposed to avoid repeatedly exploring neighbor relationships in hypergraphs and hence accelerate the construction. Extensive experiments on 20 datasets demonstrate the efficiency and scalability of our approach.","short_abstract":"Reachability in hypergraphs is essential for modeling complex groupwise interactions in real-world applications such as co-authorship, social network, and biological analysis, where relationships go beyond pairwise interactions. In this paper, we introduce the notion of s-reachability, where two vertices are s-reachabl...","url_abs":"https://arxiv.org/abs/2512.23345","url_pdf":"https://arxiv.org/pdf/2512.23345v1","authors":"[\"Peiting Xie\",\"Xiangjun Zai\",\"Yanping Wu\",\"Xiaoyang Wang\",\"Wenjie Zhang\",\"Lu Qin\"]","published":"2025-12-29T10:13:38Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}