US Patent No. 10,191,998

METHODS OF DATA REDUCTION FOR PARALLEL BREADTH-FIRST SEARCH OVER GRAPHS OF CONNECTED DATA ELEMENTS


Patent No. 10,191,998
Issue Date January 29, 2019
Title Methods Of Data Reduction For Parallel Breadth-first Search Over Graphs Of Connected Data Elements
Inventorship Paul Burkhardt, North Potomac, MD (US)
Assignee The United States of America, as represented by the Director, National Secu...

Claim of US Patent No. 10,191,998

1. A computer-implemented method of constructing a logical pathway between an initial search frontier and a target data element in an undirected graph of data elements, in a system comprising 1) a plurality of parallel processors each having a local memory, 2) an inter-processor communication (IPC) network, and 3) a master controller having a local memory and logically coupled to the plurality of parallel processors via the IPC network, the method comprising:receiving, at the master controller in the local memory, a data structure defining a symmetric matrix having size n×n, wherein the value of each matrix element corresponds to one of 1) a presence of, and 2) an absence of, an undirected edge between a pair of data elements in the graph of data elements defined by a row and a column of the matrix element;
receiving, at the master controller in the local memory, a first vector of length n, wherein the value of each element in the vector corresponds to one of 1) a presence of, and 2) an absence of, a data element of the graph of data elements in the initial search frontier;
at the master controller in the local memory, initializing 1) a counter variable and 2) a tracking array, wherein the tracking array contains array elements that are configured to track dimensionality reduction parameters for the matrix;
repeatedly performing the operations of:
multiplying a subset of the matrix defined by the array element corresponding to the counter variable, by a subset of the first vector defined by the array element corresponding to the counter variable, to generate a second vector corresponding to an updated search frontier corresponding to the counter variable, wherein multiplying the subset of the matrix by the subset of the first vector comprises:
providing, from the master controller via the IPC network to a first processor of the plurality of parallel processors, the first vector and at least one first portion of the matrix;
at the first processor in the first processor's local memory, multiplying the first vector by the at least one first portion of the matrix to produce a first result;
providing, from the first processor via the IPC network to the master controller, the first result;
providing, from the master controller via the IPC network to a second processor of the plurality of parallel processors, the first vector and at least one second portion of the matrix;
at the second processor in the second processor's local memory, multiplying the first vector by the at least one second portion of the matrix to produce a second result;
providing, from the second processor via the IPC network to the master controller, the second result; and
combining, at the master controller in the local memory, the first result and the second result to generate the second vector corresponding to the updated search frontier;
incrementing the counter variable;
updating the first vector based on the updated search frontier; and
updating an array element in the tracking array corresponding to the counter variable based on the non-zero values of the first vector, such that the updated array element corresponds to a larger dimensionality reduction of the matrix than the previously used array element;
until 1) the updated search frontier contains a non-zero element corresponding to the target data element, or 2) the matrix is reduced to a minimum dimension; and
constructing the logical pathway based on the tracking array.