This paper presents a middleware framework for storing, accessing and analyzing massive-scale semantic graphs. The framework, MSSG, targets scale-free semantic graphs with O(1012) (trillion) vertices and edges. Here, we present the overall architectural design of the framework, as well as a prototype implementation for cluster architectures. The sheer size of these massive-scale semantic graphs prohibits storing the entire graph in memory even on medium- to large-scale parallel architectures. We therefore propose a new graph database, grDB, for the efficient storage and retrieval of large scale-free semantic graphs on secondary storage. This new database supports the efficient and scalable execution of parallel out-of-core graph algorithms which are essential for analyzing semantic graphs of massive size. We have also developed a parallel out-of-core breadth-first search algorithm for performance study. To the best of our knowledge, it is the first of such algorithms reported in the literature. Experimental evaluations on large real-world semantic graphs show that the MSSG framework scales well, and grDB outperforms widely used open-source out-of-core databases, such as BerkeleyDB and MySQL, in the storage and retrieval of scale-free graphs

The lack of publicly available large scale-free graphs forces researchers studying massive scale-free graphs to rely on synthetically generated graphs in testing and evaluating their algorithms. This requires a graph generator that can scale to the graphs with potentially tens and hundreds of billions of vertices and edges. We have developed two such scalable parallel graph generators in this research. The parallel Barabasi-Albert method iteratively builds scale-free graphs using two-phase preferential attachment technique in a bottom-up fashion. The parallel Kronecker method, on the other hand, constructs a graph recursively in a top-down fashion from a given seed graph using the Kronecker matrix multiplication. We show that both graph generators generate massive graphs at a very high rate. It is also shown that graphs generated by these methods have all the common properties of the real scale-free graphs such as power-law degree distribution and small-worldness.

Many emerging large-scale data science applications require searching large graphs distributed across multiple memories and processors. This paper presents a distributed breadth- first search (BFS) scheme that scales for random graphs with up to three billion vertices and 30 billion edges. Scalability was tested on IBM BlueGene/L with 32,768 nodes at the Lawrence Livermore National Laboratory. Scalability was obtained through a series of optimizations, in particular, those that ensure scalable use of memory. We use 2D (edge) partitioning of the graph instead of conventional 1D (vertex) partitioning to reduce communication overhead. For Poisson random graphs, we show that the expected size of the messages is scalable for both 2D and 1D partitionings. Finally, we have developed efficient collective communication functions for the 3D torus architecture of BlueGene/L that also take advantage of the structure in the problem. The performance and characteristics of the algorithm are measured and reported.

Any Hadamard matrix constructed by methods of R. E. A. C. Paley can be converted easily by one or two elementary matrix operations to a form sharing at least four desirable properties with standard forms of Walsh matrices: symmetry, zero trace, normal form, and the same number of 1's as −1's in every row and column except the 0th row and 0th column.

Attention is called to previous research on realization of an arbitrary switching function by a network of threshold gates (or threshold elements) and modulo-2 gates (or parity elements), establishment of greatest lower bounds on the number of gates needed, artifices that lead to further network reduction in special cases, and systematic minimization of the number of modulo-2 gates required.

The matrix form of the Walsh functions as defined in the above-mentioned short note [1] can be generated by the modulo-2 product of two generating matrices: the natural binary code, and the transpose of the bit-reversed form of the first. As a result, the coefficients of the Walsh transform occur in bit-reversed order. By simply reordering the Walsh functions themselves to correspond to generation by the product of two such code matrices, neither or both in bit-reversed form, the Walsh coefficients occur in their natural order.

The complete set of orthogonal functions of binary variables called Walsh functions can be obtained as direct products of the subclass of these functions known as Rademacher functions. The complete set of Walsh functions can be conveniently represented by a square matrix of l's and -1's, which, when normalized, is an orthogonal matrix. The correct Rademacher functions to multiply together to obtain a specified Walsh function can be determined without the use of recursion formulas by reference to a simple modification of the reflected binary code. A binary equivalent of the Walsh matrix, consisting of 0's and 1's, can be generated directly by multiplying together, modulo 2, two simpler matrices easily obtained from the reflected binary code and natural binary code, respectively. A modified Walsh matrix that has a simple recursive structure can be obtained by rearranging the rows of the fundamental Walsh matrix. A binary equlivalent of thle former can also be generated directly by multiplying together, modulo 2, two simpler matrices easily obtained from the natural binary code alone. A transformation matrix for direct conversion of the Walsh matrix from its fundamental to modified (or modified to fundamental) form can be written by observing how the rows of the natural binary code are rearranged to form the modified reflected binary code.