Authors: Jiwon Seo, Stephen Guo, Monica S. Lam
Abstract:
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.
We evaluated SociaLite by running eight graph algorithms (shortest
paths, PageRank, hubs and authorities, mutual neigh- bors, connected
components, triangles, clustering coefficients, and betweenness
centrality) on two real-life social graphs, Live- Journal and Last.fm.
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% 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, giving up only 16% for the largest
benchmark. Most importantly, being a query language, SociaLite enables
many more users who are not proficient in software engineering to make
social network queries easily and efficiently.