• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国卫生研究院文献>Springer Open Choice >Compile- and run-time approaches for the selection of efficient data structures for dynamic graph analysis
【2h】

Compile- and run-time approaches for the selection of efficient data structures for dynamic graph analysis

机译：选择编译时和运行时方法进行动态图分析的有效数据结构

代理获取
本网站仅为用户提供外文OA文献查询和代理获取服务，本网站没有原文。下单后我们将采用程序或人工为您竭诚获取高质量的原文，但由于OA文献来源多样且变更频繁，仍可能出现获取不到、文献不完整或与标题不符等情况，如果获取不到我们将提供退款服务。请知悉。
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graphs are used to model a wide range of systems from different disciplines including social network analysis, biology, and big data processing. When analyzing these constantly changing dynamic graphs at a high frequency, performance is the main concern. Depending on the graph size and structure, update frequency, and read accesses of the analysis, the use of different data structures can yield great performance variations. Even for expert programmers, it is not always obvious, which data structure is the best choice for a given scenario.In previous work, we presented an approach for handling the selection of the most efficient data structures automatically using a compile-time approach well-suited for constant workloads.We extend this work with a measurement study of seven data structures and use the results to fit actual cost estimation functions. In addition, we evaluate our approach for the computations of seven different graph metrics. In analyses of real-world dynamic graphs with a constant workload, our approach achieves a speedup of up to 5.4× compared to basic data structure configurations.Such a compile-time based approach cannot yield optimal results when the behavior of the system changes later and the workload becomes non-constant. To close this gap we present a run-time approach which provides live profiling and facilitates automatic exchanges of data structures during execution. We analyze the performance of this approach using an artificial, non-constant workload where our approach achieves speedups of up to 7.3× compared to basic configurations.
机译：图形用于建模来自不同学科的各种系统，包括社交网络分析，生物学和大数据处理。在高频下分析这些不断变化的动态图时，性能是主要问题。根据图形的大小和结构，更新频率以及分析的读取访问权限，使用不同的数据结构可能会产生很大的性能差异。即使对于专业程序员来说，哪种数据结构对于给定场景也是最佳选择也不总是很明显。在以前的工作中，我们提出了一种使用编译时方法自动处理最有效数据结构选择的方法，适用于恒定的工作量。我们通过对七个数据结构的度量研究来扩展这项工作，并使用结果来适合实际的成本估算功能。此外，我们评估了我们用于计算七个不同图形指标的方法。在分析具有恒定工作量的现实世界动态图时，与基本数据结构配置相比，我们的方法可实现高达5.4倍的加速。基于编译时的方法无法在系统行为稍后发生变化时产生最佳结果，并且工作负载变得非常不稳定。为了弥补这一差距，我们提出了一种运行时方法，该方法可提供实时性能分析并在执行过程中促进数据结构的自动交换。我们使用人为的非恒定工作负载分析此方法的性能，与基本配置相比，我们的方法可将速度提高7.3倍。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号