Search

This paper studies batch processing of core maintenance in hypergraph streams. We focus on updating the coreness of each vertex after the hypergraph evolves. Unlike existing works that mainly focus on exact coreness updates for the single hyperedge dynamic or approximate update, we propose the first known batch processing algorithms for exact core maintenance with insertions or deletions of multiple hyperedges. By proposing a hyperedge structure Joint Hyperedge Set, we tackle the challenges of quantifying the range of coreness change and finding potential vertices whose coreness may update. In addition, we accelerate coreness updates even further by finding structures that enable parallel execution. Extensive experiments illustrate the efficiency, scalability, and effectiveness of our batch core maintenance algorithms on real-world hypergraphs. It shows that our algorithms can be faster than the single hyperedge processing approaches by a factor of nearly half the number of hyperedges processed, and our parallel algorithms achieve linear acceleration with the increasing number of threads. [ABSTRACT FROM AUTHOR]