图 书 馆
基于草图的web尺度距离预测A Sketch-Based Distance Oracle for Web-Scale Graphs |
|
| 课程网址: | http://videolectures.net/wsdm2010_sarma_asbd/ |
| 主讲教师: | Atish Das Sarma |
| 开课单位: | 乔治亚理工学院 |
| 开课时间: | 2010-10-12 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We study the fundamental problem of computing distances between nodes in large graphs such as the web graph and social networks. Our objective is to be able to answer distance queries between pairs of nodes in real time. Since the standard shortest path algorithms are expensive, our approach moves the time-consuming shortest-path computation offline, and at query time only looks up precomputed values and performs simple and fast computations on these precomputed values. More specifically, during the offline phase we compute and store a small “sketch” for each node in the graph, and at query-time we look up the sketches of the source and destination nodes and perform a simple computation using these two sketches to estimate the distance. |
| 关 键 词: | 网络图; 社交网络; 距离查询 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-05-31：王勇彬(课程编辑志愿者) |
| 阅读次数: | 86 |