图 书 馆
社交网络的邻居查询友好压缩Neighbor Query Friendly Compression of Social Networks |
|
| 课程网址: | http://videolectures.net/kdd2010_maserrat_nqfcsn/ |
| 主讲教师: | Hossein Maserrat |
| 开课单位: | 西蒙弗雷泽大学 |
| 开课时间: | 信息不详。欢迎您在右侧留言补充。 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 社交网络; 邻居查询; 线性化; 压缩方法 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-12-26：cwx |
| 阅读次数: | 62 |