Indexing bipartite memberships in web graphs

Yusheng Xie, Zhengzhang Chen, Diana Palsetia, Ankit Agrawal, Alok 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
EditorsXindong Wu, Xindong Wu, Martin Ester, Guandong Xu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages166-173
Number of pages8
ISBN (Electronic)9781479958771
DOIs
StatePublished - Oct 10 2014
Event2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014 - Beijing, China
Duration: Aug 17 2014Aug 20 2014

Publication series

NameASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Other

Other2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014
Country/TerritoryChina
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