2010 NeighborQueryFriendlyCompressio

• (Maserrat et al., 2010) ⇒ Hossein Maserrat, and Jian Pei. (2010). “Neighbor Query Friendly Compression of Social Networks.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835873

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Neighbor+query+friendly+compression+of+social+networks%22+2010
• http://portal.acm.org/citation.cfm?id=1835873&preflayout=flat#citedby

Quotes

Abstract

Compressing social networks can substantially facilitate mining and advanced analysis of large social networks. Preferably, social networks should be compressed in a way that they still can be queried efficiently without decompression. Arguably, neighbor queries, which search for all neighbors of a query vertex, are the most essential operations on social networks. Can we compress social networks effectively in a neighbor query friendly manner, that is, neighbor queries still can be answered in sublinear time using the compression? In this paper, we develop an effective social network compression approach achieved by a novel Eulerian data structure using multi-position linearizations of directed graphs. Our method comes with a nontrivial theoretical bound on the compression rate. To the best of our knowledge, our approach is the first that can answer both out-neighbor and in-neighbor queries in sublinear time. An extensive empirical study on more than a dozen benchmark real data sets verifies our design.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 NeighborQueryFriendlyCompressio	Jian Pei Hossein Maserrat			Neighbor Query Friendly Compression of Social Networks		KDD-2010 Proceedings		10.1145/1835804.1835873		2010