Zero-Redundancy Search for Bi-Components in Bipartite Graphs
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26
DOI: 10.1145/3802129 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Chuanyu Zong und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 52 Literaturangaben. Gefördert von: National Key R\\&D Program of China, NSFC, Key R\\&D Program of Liaoning.
Abstract (Originalsprache)
Efficiently managing and querying large bipartite graphs necessitates powerful indexing structures. A fundamental challenge lies in supporting (α,β)-component (bi-component) search, a task that encompasses retrieving all bi-components (bi-core search) or identifying the specific bi-component containing a query vertex (bi-community search). Existing index-based solutions face a time-space trade-off: single-dimensional approaches incur significant storage redundancy, while holistic approaches suffer from repeated vertex retrievals, hindering their scalability. To overcome these limitations, in this paper, we address this trade-off by introducing a novel, finer-grained cohesive unit, the (α,β,γ)- cluster ( bi-cluster ). This unit inherently captures the nested and overlapping relationships among bi-components, enabling vertex deduplication at the index level. Building on this, we propose the SGL ( Summary Graph + Location ) index, which achieves zero-redundancy in vertex retrieval during query processing. It organizes bi-components into a compact Summary Graph (SG) of interconnected SNodes. This structure, coupled with a precise Location mapping, allows our search algorithm to retrieve results without redundant vertex accesses, effectively decoupling query cost from the graph's global scale. Furthermore, we provide efficient construction and maintenance algorithms for dynamic bipartite graphs. Extensive experiments on ten real and synthetic large bipartite graphs demonstrate that our method outperforms the state-of-the-art by up to two orders of magnitude in query speed for bi-component search, while maintaining low storage, thus bridging the gap between fast but space-inefficient and compact but slower existing approaches.
Förderung
- National Key R\\&D Program of China
- NSFC
- Key R\\&D Program of Liaoning
- 111 Project
- NSF of Liaoning
Zitieren
APA
Zong, C., Meng, L., Yang, X., Wang, B., Qiu, T., & Zhu, R. (2026). Zero-Redundancy Search for Bi-Components in Bipartite Graphs. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802129
Vancouver
Zong C, Meng L, Yang X, Wang B, Qiu T, Zhu R. Zero-Redundancy Search for Bi-Components in Bipartite Graphs. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802129
BibTeX
@article{Zong2026,
author = {Zong, Chuanyu and Meng, Lingbiao and Yang, Xiaochun and Wang, Bin and Qiu, Tao and Zhu, Rui},
title = {Zero-Redundancy Search for Bi-Components in Bipartite Graphs},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--26},
doi = {10.1145/3802129}
}
EUVIMED