Indexing bipartite memberships in web graphs
Yusheng Xie, Zhengzhang Chen, Diana Palsetia, Ankit Agrawal, Alok Choudhary · 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014) · 2014
Massive bipartite graphs are ubiquitous in real world and have important applications in social networks, biological mechanisms, etc. Consider one billion plus people on Facebook making trillions of connections with millions of organizations. Such big social bipartite graphs are often very skewed and unbalanced, on which traditional indexing algorithms do not perform optimally. In this paper, we propose Arowana, a data-driven algorithm for indexing large unbalanced bipartite graphs. Arowana achieves a high-performance efficiency by building an index tree that incorporates the semantic affinity among unbalanced graphs. Arowana uses probabilistic data structures to minimize space overhead and optimize search. In the experiments, we show that Arowana exhibits significant performance improvements and reduces space overhead over traditional indexing techniques.