Indexing bipartite memberships in web graphs

Yusheng Xie, Zhengzhang Chen, Diana Palsetia, Ankit Agrawal, Alok Nidhi Choudhary

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages166-173
Number of pages8
ISBN (Electronic)9781479958771
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014 - Beijing, China
Duration: Aug 17 2014Aug 20 2014

Other

Other2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014
CountryChina
CityBeijing
Period8/17/148/20/14

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Indexing bipartite memberships in web graphs'. Together they form a unique fingerprint.

  • Cite this

    Xie, Y., Chen, Z., Palsetia, D., Agrawal, A., & Choudhary, A. N. (2014). Indexing bipartite memberships in web graphs. In ASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (pp. 166-173). [6921578] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASONAM.2014.6921578