Paper Info
Title
High-performance analysis of filtered semantic graphs
Abstract
High performance is a crucial consideration when executing a complex analytic query on a massive semantic graph. In a semantic graph, vertices and edges carry "attributes" of various types. Analytic queries on semantic graphs typically depend on the values of these attributes; thus, the computation must either view the graph through a "filter" that passes only those individual vertices and edges of interest, or else must first materialize a subgraph or subgraphs consisting of only the vertices and edges of interest. The filtered approach is superior due to its generality, ease of use, and memory efficiency, but may carry a performance cost. In the Knowledge Discovery Toolbox (KDT), a Python library for parallel graph computations, the user writes filters in a high-level language, but those filters result in relatively low performance due to the bottleneck of having to call into the Python interpreter for each edge. In this work, we use the Selective Embedded JIT Specialization (SEJITS) approach to automatically translate filters defined by programmers into a lower-level efficiency language, bypassing the upcall into Python. We evaluate our approach by comparing it with the high-performance C++/MPI Combinatorial BLAS engine, and show that the productivity gained by using a high-level filtering language comes without sacrificing performance.
Year
DOI
Venue
2012
10.1145/2370816.2370897
PACT
Keywords
Field
DocType
massive semantic graph,python library,filtered semantic graph,performance cost,semantic graph,high-performance analysis,filters result,high performance,filtered approach,parallel graph computation,python interpreter,low performance,parallel processing,computations,value,semantics,productivity,high level languages,high performance computing,graphs,language,domain specific languages,performance engineering,graph analysis
Domain-specific language,Programming language,Vertex (geometry),Computer science,Parallel computing,Theoretical computer science,Power graph analysis,High-level programming language,Knowledge extraction,Python (programming language),Semantics,Complement graph
Conference
ISSN
ISBN
Citations 
1089-795X
978-1-5090-6609-4
2
PageRank 
References 
Authors
0.41
11
7
Name
Order
Citations
PageRank
Aydin Buluc1105767.49
Armando Fox26238524.64
John R. Gilbert32369308.81
Shoaib A. Kamil420.41
Adam Lugowski5513.40
leonid oliker61358145.15
Samuel Williams7707.37