论文标题
O'Reach：甚至在大图中更快的可及性
O'Reach: Even Faster Reachability in Large Graphs
论文作者
论文摘要
计算机科学中最根本的问题之一是可及性问题：鉴于有向图和两个顶点S和T，可以通过路径达到T吗？我们重新审视现有技术，并将它们与新方法相结合，以使用线性尺寸可及性指数在恒定时间内支持大部分可及性查询。我们的新算法O'Reach可以很容易地与以前开发的问题或独立运行的解决方案相结合。 在一项详细的实验研究中，我们将各种算法与它们的索引构建和查询时间以及它们在各种实例集上的记忆足迹进行了比较。我们的实验表明，查询性能通常不仅在很大程度上取决于图的类型，还取决于结果，即可触及或无法到达。此外，我们表明，在几乎所有情况下，与我们的新方法结合使用，以前的算法会大大加速。出乎意料的是，由于缓存效果，对空间的投资不一定会得到回报：在预先计算的完整可及性矩阵中，通常可以比单个内存访问更快地回答可达性查询。
One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O'Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn't necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.
