...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Knowledge and Data Engineering, IEEE Transactions on >SociaLite: An Efficient Graph Query Language Based on Datalog
【24h】

SociaLite: An Efficient Graph Query Language Based on Datalog

机译：SociaLite：一种基于数据记录的高效图查询语言

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

With the rise of social networks, large-scale graph analysis becomes increasingly important. Because SQL lacks the expressiveness and performance needed for graph algorithms, lower-level, general-purpose languages are often used instead. For greater ease of use and efficiency, we propose SociaLite, a high-level graph query language based on Datalog. As a logic programming language, Datalog allows many graph algorithms to be expressed succinctly. However, its performance has not been competitive when compared to low-level languages. With SociaLite, users can provide high-level hints on the data layout and evaluation order; they can also define recursive aggregate functions which, as long as they are meet operations, can be evaluated incrementally and efficiently. Moreover, recursive aggregate functions make it possible to implement more graph algorithms that cannot be implemented in Datalog. We evaluated SociaLite by running nine graph algorithms in total; eight for social network analysis (shortest paths, PageRank, hubs and authorities, mutual neighbors, connected components, triangles, clustering coefficients, and betweenness centrality) and one for biological network analysis (Eulerian cycles). We use two real-life social graphs, LiveJournal and Last.fm, for the evaluation as well as one synthetic graph. The optimizations proposed in this paper speed up almost all the algorithms by 3 to 22 times. SociaLite even outperforms typical Java implementations by an average of 50 percent for the graph algorithms tested. When compared to highly optimized Java implementations, SociaLite programs are an order of magnitude more succinct and easier to write. Its performance is competitive, with only 16 percent overhead for the largest benchmark, and 25 percent overhead for the worst case benchmark. Most importantly, being a query language, SociaLite enables many more users who are not proficient in software engineering to perform network analysis easily and efficiently.
机译：随着社交网络的兴起，大规模图形分析变得越来越重要。由于SQL缺乏图算法所需的表达能力和性能，因此通常使用较低级别的通用语言。为了更易于使用和提高效率，我们提出了SociaLite，这是一种基于Datalog的高级图形查询语言。作为逻辑编程语言，Datalog允许许多图形算法简洁地表达。但是，与低级语言相比，它的性能没有竞争力。使用SociaLite，用户可以提供有关数据布局和评估顺序的高级提示。他们还可以定义递归集合函数，只要它们满足操作，就可以对其进行增量和有效评估。此外，递归聚合函数使实现更多无法在Datalog中实现的图形算法成为可能。我们通过总共运行九种图形算法对SociaLite进行了评估。八个用于社交网络分析（最短路径，PageRank，集线器和权限，相互邻居，连接的组件，三角形，聚类系数和中间性中心），另一个用于生物网络分析（欧拉循环）。我们使用两个真实生活的社交图，即LiveJournal和Last.fm进行评估，并使用一个合成图。本文提出的优化将几乎所有算法的速度提高了3到22倍。对于所测试的图形算法，SociaLite甚至比典型的Java实现要好50％。与高度优化的Java实现相比，SociaLite程序更简洁，更容易编写。它的性能具有竞争力，最大的基准仅需16％的开销，最坏的基准仅需25％的开销。最重要的是，作为一种查询语言，SociaLite使更多不熟悉软件工程的用户可以轻松高效地执行网络分析。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号