Multi-source breadth-first search (MS-BFS) technique and graph processing system that applies it

Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

FIELD OF THE DISCLOSURE

This disclosure relates to graph traversal. Presented herein are techniques that minimize how much memory is needed to store measurements of logical distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS).

BACKGROUND

Graph analysis is a recently popularized way of analyzing data, which considers not only properties of entities but also relationships between them. Algorithms for graph analysis may be based on breadth-first search (BFS). BFS is a way of systematically traversing a graph from a start vertex, such that all vertices with a distance of a given number of vertex hops are visited before vertices with a greater distance. Such algorithms may need to run multiple BFSs from different start vertices in the graph in order to compute a final result. Examples of such algorithms include closeness centrality and betweenness centrality.

Some techniques for BFS-based algorithms may perform all necessary BFSs independently. Thus even if the independent BFSs are simultaneously performed, they do not leverage any shared computation between them. Consequently, many subgraph traversals are made redundantly, which may waste time and energy.

Another technique that does leverage shared computation of BFSs is referred to herein as a multi-source breadth-first search (MS-BFS). This technique enables fast computation of multiple BFSs by simultaneously performing several instances of BFS traversals in a way that is very efficient because intermediate results (common traversals of subgraphs) are shared amongst the BFS instances. Consequently, the MS-BFS technique provides tremendous performance benefits, such as acceleration.

MS-BFS may be decomposed into batches (units of work) of paths or vertices to maximize throughput. MS-BFS stores a traversal distance (path length) for each batch. That information is referred to herein as “frontier history,” which facilitates identifying the parent and children of each vertex in a traversal.

Unfortunately the memory required to store frontier history can be very significant because graph instances from real-world datasets are often very large in size (i.e. millions of vertices interconnected by billions of edges). Furthermore, pre-allocation of uninitialized data structures for frontier history involves a tradeoff between time and space. Memory space for pre-allocated frontier history may be minimized only if the diameter of a graph is known, which may be automatically discovered based on an algorithm of cubic complexity based on graph size (vertex count). Thus, saving pre-allocated memory for frontier history may take immense (cubic) time to calculate how little memory will suffice.

Alternatively, pre-allocation time may be minimized by more or less ignoring graph size and instead pre-allocating excessive memory to accommodate a possible worst case of demand for memory. Although excessive memory allocation may save preparation time, it may also cost additional time during search execution. For example, excessive memory allocation may involve using excessively large datatypes that do not encode data compactly. Such encoding sparsity and excessive memory allocation may thrash virtual memory during search execution, which entails disk latency. Alternatively, an embodiment may pre-allocate a modest amount of memory that may work for small graphs but may be inadequate for many graphs, thereby posing a risk of catastrophic malfunction, perhaps prematurely aborting an intensive graph analysis, such as after some hours of execution.

DETAILED DESCRIPTION

Embodiments are described herein according to the following outline:1.0 General Overview2.0 Example Computer2.1 Graph Traversal2.2 Concurrency2.3 Sequence of Iterations2.4 Frontier History2.5 Distance Matrix2.6 Value Encoding Into Primitive Integer Type2.7 Progressive Sequences and Types2.8 Serial Numbers3.0 Frontier History Recording Process3.1 Integer Exhaustion Detection3.2 Repeated Exhaustions by Very Large Graph3.3 Dynamic Allocation3.4 Progressive Thresholds4.0 Hardware Overview5.0 Software Overview6.0 Cloud Computing

1.0 General Overview

Techniques are provided to minimize how much memory is needed to store measurements of logical distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to a vertex of the graph. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. In response to the detecting, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

In embodiments, progressive thresholds facilitate deferral of behaviors such as allocation of matrices and selection of integer type width. That facilitates an encoding density for distances that is not achieved by conventional (pessimistic and eager) allocation of memory for matrices. By decreasing demand for memory, techniques herein may decrease virtual memory thrashing, thereby avoiding disk activity, thereby accelerating the computer.

In embodiments, encoding techniques enable a signed integer to store positive values that occupy a same range of values as an unsigned integer. Embodiments achieve concurrency with techniques such as symmetric multiprocessing (SMP), vertex batching, and work stealing. A growing series of distance matrices provides a complete frontier history for reference by threads and/or batches whose progress (current search radius) may differ.

2.0 Example Computer

FIG. 1is a block diagram that depicts an example computer100, in an embodiment. Computer100replaces a datatype of a frontier history of a multi-source breadth-first search (MS-BFS) based on an expanding search radius.

Computer100may be one or more rack servers such as blades, personal computers, mainframes, network appliances, virtual machines, smartphones, or other computing device. In embodiments, computer100accesses graph110that is stored in memory, on disk, or over a network.

Graph110is a logical graph comprised of interconnected vertices such as vertices121-123. Graph110may have disconnected subgraphs such that some vertices may be unreachable (not directly or indirectly connected) to a given vertex.

In operation, computer100performs multi-source breadth-first search (MS-BFS)130to discover interesting traversal paths through graph110that originate from given source vertices. In this example, MS-BFS130originates from source vertices121-122.

MS-BFS130is parallelizable by design. Indeed, MS-BFS130is well suited to shared-memory and task-parallel implementations, such as symmetric multiprocessing (SMP) and especially multicore. For example, computer100may simultaneously explore paths that originate from both source vertices121-122.

For example, concurrency may be achieved with multiple execution threads such as lightweight threads or heavyweight user processes. In embodiments, a separate thread traverses paths that originate from a respective subset of source vertices.

One vertex may have multiple neighboring vertices. For example, source vertex122has vertices121and123as neighbors.

Thus, fan-out is natural to breadth-first search. Fan-out may generate an amount of traversal paths that exceeds the amount of source vertices and/or execution threads.

Thus, workflow management techniques such as work stealing and/or batching of neighbor vertices to visit (traverse). In SMP embodiments, threads may be pooled, may be associated with processors or processor cores such as at a one-to-one or other ratio, and may be created according to how many processors or processor cores are available.

Batching of traversals may increase memory locality, thereby decreasing demand for memory bandwidth. Furthermore, batching is amenable to vectorization such as single instruction multiple data (SIMD).

Furthermore, underlying mechanisms of MS-BFS130may maintain a set of vertices currently being visited and a set of previously visited vertices, for each thread or batch. Thus, the status (visiting or visited) of vertices may be tracked, and these binary statuses are readily implemented as sets of bits, which are naturally amenable to SIMD on any general-purpose register-based processor.

2.3 Sequence of Iterations

Breadth-first search is iterative. Thus, MS-BFS130executes a series of iterations, which may occur as subseries of iterations such as sequence of iterations141followed by142.

2.4 Frontier History

Each sequence of iterations141-142includes a matrix data structure that computer100creates in memory. For example when computer100begins sequence of iterations141, computer100creates the matrix shown as iteration151. When computer100performs iteration151, computer100uses the matrix shown as iteration151.

Subsequently, computer100performs iteration152. However because iterations151-152are in a same sequence of iterations141, computer100reuses the matrix of iteration151again for iteration152. Thus, what is shown as separate matrices for iteration151-152is actually a same matrix being reused throughout sequence of iterations141.

However as sequence of iterations141progresses through iterations151-152, increasing amounts of actual numeric distance values are stored within the matrix. This dynamically growing progression of distance values provides a frontier history of (completely or partially) traversed paths.

In embodiments, each thread has its own copies of matrices of iterations151-154. In some distributed embodiments, computer100may be a cluster of computers, each of which has its own copies of matrices of iterations151-154shared by threads hosted on that computer. In shared memory embodiments, there is only one copy of the matrices, which all threads share. As MS-BFS130runs, the growing series of distance matrices provides a complete frontier history for reference by threads and/or batches whose progress (current search radius) may differ.

2.5 Distance Matrix

The first iteration (151) visits source vertices121-122, which are the origins of all traversal paths. Source vertices are reachable without actually traversing to other vertices.

Thus in iteration151, the traversal paths have zero length. Thus, iteration151stores only zeros for distance values.

For example, source vertex121can be reached from itself with a path length of zero. Indeed, any source vertex can be reached from itself with a path length of zero.

Thus in this example, a distance value of zero is stored along the matrix diagonal of iteration151. Because MS-BFS has two source vertices, iteration151stores two zeros along the matrix diagonal.

However in other examples, the initial zeroes need not align along a diagonal. For example if source vertices instead were vertices121and123, then initial zeroes would not occur along a diagonal.

Likewise with a path length of zero, only each source vertex is reachable from itself. Thus, all other vertices are unreachable from a source vertex during iteration151.

For example, vertices122-123are unreachable from source vertex121during iteration151. Unreachable vertices are shown in the matrix of iteration151as shaded and without a value.

For example during iteration151, source vertex121is reachable from itself but not from source vertex122. Thus, the top matrix row of iteration151has a zero on the left and is shaded without a value on the right.

During iteration151, vertex123is unreachable from both source vertices121-122. Thus, the bottom matrix row of iteration151is entirely shaded and without values.

In a signed integer embodiment, a distance value of −1 may represent unreachability. Thus, the shaded matrix elements may each actually store −1. In unsigned embodiments, a different value indicates unreachability.

Each iteration adds more distance values to the distance values recorded in the previous iteration. Thus, computer100supplements the distance values of iteration151with additional values calculated during iteration152.

Thus, iterations151-152both have zeros along the matrix diagonal. However because each successive iteration of a breadth-first search incrementally expands the search horizon (radius), some of the shaded valueless elements of the previous iteration may receive values in the next iteration.

For example, iteration152also records paths from source vertices with a distance of one. For example, vertex123is reachable from source vertex122at a distance of one.

Thus, a one is stored in the lower right element of iteration152, even though the same element indicated unreachability in iteration151. Thus with enough iterations, MS-BFS130may or may not eventually create an iteration that stores an actual distance value in every matrix element.

2.6 Value Encoding into Primitive Integer Type

Graph110may contain billions of vertices and trillions of edges, such as in an artificial neural network. Thus, the size (memory footprint) of an iteration matrix may be immense.

Matrix size may be minimized by encoding distance values in a primitive integer datatype that has no more bytes than needed to store the largest distance value of that iteration. For example, iteration151has distance values of zero and −1, which are two values. Two values may be minimally encoded as a single bit or byte.

All iterations of a given sequence of iterations, such as141, use a same datatype for encoding distance values. For example, iterations151-152may both use a byte to store distance values.

Thus, sequence of iterations141has primitive integer type161, which may be a byte. Whereas, sequence of iterations142may have a different datatype for distance values, such as primitive integer type162, which may be something other than a byte.

A signed byte may directly store values ranging from −128 to 127. Thus, a signed byte cannot directly store a distance value for a path whose length exceeds 127. Thus, directly stored signed bytes cannot be used to fully traverse a graph whose diameter exceeds 127.

However, an embodiment may use an unsigned byte, which encodes values from 0 to 255. Value 255 may indicate unreachability, in the same way that −1 may for a signed integer.

Likewise, an embodiment may use a signed byte and subtract 127 from the distance value during encoding. For example, a distance of 1 may be encoded as −126. Likewise, a distance of 227 may be encoded as 100, which can be stored in a signed byte, even though a signed byte cannot directly store a value of 227.

2.7 Progressive Sequences and Types

Eventually, sequence of iterations141may have enough iterations to expand the search horizon (path length) beyond the capacity of a byte. Although sequence of iterations141shows only two iterations, sequence of iterations141may actually have 255 iterations before exhausting primitive integer type161as a byte.

Even though the iterations of MS-BFS130may still continue beyond the exhaustion of primitive integer type161, sequence of iterations141will have no additional iterations. Additional iterations instead occur in sequence of iterations142with primitive integer type162that is bigger (has more bytes) than primitive integer type161. Thus, sequence of iterations142accommodates search horizons that are too big for sequence of iterations141.

In embodiments, when transitioning from sequence of iterations141to142, computer100regenerates the iteration matrices (151-152) of sequence of iterations141using primitive integer type162instead of161. Such regeneration may involve upcasting, such as a widening primitive conversion.

For example, byte values may be upcasted to short values. By upcasting the distance values of previous sequences of iterations, computer100may maintain all iteration matrices (151-154) with a same datatype, such as primitive integer type162.

Eventually primitive integer type162may also be exhausted. Computer100may create a third sequence of iterations (not shown) with an even bigger distance datatype (not shown).

For example in Java, computer100may successively use a byte, a short, an int, and a long as primitive integer types to store distance values. A long can encode distances of a graph having a diameter bigger than any graph ever loaded into computer memory.

2.8 Serial Numbers

In embodiments, every iteration has a zero-based serial number. For example, iteration151may have a serial number of zero. Likewise, iteration152may have a serial number of one.

The same serial numbering continues across all iterations, regardless of which iteration belongs to which sequence of iterations. The zero-based serial number of an iteration exactly matches the search horizon distance of the iteration.

For example, iteration151has a serial number of zero and search horizon of zero. Thus, recording a new distance value into a matrix element of an iteration may entail recording the serial number of the iteration.

3.0 Frontier History Recording Process

FIG. 2is a flow diagram that depicts an example process that replaces a datatype of a frontier history of a multi-source breadth-first search (MS-BFS) based on an expanding search radius.FIG. 2is discussed with reference toFIG. 1.

Although not shown, before step202, computer100creates a distance matrix for sequence of iterations141using a first primitive integer type. Steps202and204are performed for each iteration of sequence of iterations141. For example, computer100performs steps202and204for iteration151, and subsequently performs steps202and204again for iteration152.

Step202populates a distance matrix of a current sequence of iterations using a first primitive integer type. For example, computer100populates the matrix for iteration151in memory using primitive integer type161to encode distance values.

3.1 Integer Exhaustion Detection

Step204detects whether or not the first sequence of iterations has enough iterations to exceed a threshold. The threshold is based on the maximum distance value that primitive integer type161can encode.

For example if primitive integer type161is a byte, then the threshold is 254. Thus in step204, computer100detects whether sequence of iterations141has grown to include 255 (exceeds 254) iterations.

If step204detects that the threshold is not yet exceeded, then computer100repeats steps202and204for another iteration. Thus, the number of iterations in sequence of iterations141grows incrementally (until the threshold is exceeded).

If step204detects that the threshold is exceeded, then computer100has finished sequence of iterations141and begins sequence of iterations142by proceeding to step206. In step206a second distance matrix using a second primitive integer type is created for a next sequence of iterations. Computer100may copy (and upcast) values from the first distance matrix into the second distance matrix.

Step208performs all of the iterations of sequence of iterations142. For each iteration during step208, the second distance matrix populated using the second primitive integer type to encode distances. For example, computer100successively populates the second distance matrix during iterations153-154using primitive integer type162.

3.2 Repeated Exhaustions by Very Large Graph

FIGS. 1-2show that MS-BFS130has two sequence of iterations (141-142). For example, sequence of iteration142uses primitive integer type162that may be a short that can encode distance values for a graph having a diameter of at most 64,000 approximately.

However if the graph diameter exceeds approximately 64,000, then a third sequence of iterations (not shown) with a third primitive integer type (not shown) would be necessary.FIG. 3shows the same process asFIG. 2, but with an additional (third) sequence of iterations to accommodate a larger graph.

In the same way, additional sequence of iterations can be accommodated by expanding the process flow with similar additional steps. Thus,FIG. 3appears to expand uponFIG. 2.

Such expansion may be repeated arbitrarily to create a longer process flow that accommodates more sequences of iterations for bigger search horizons. Such expansion is limited only by available primitive integer types of various widths.

For example, Java provides primitive integer types having widths of 1, 2, 4, and 8 bytes. Thus, the width doubles for each successively larger primitive integer type. Thus, the encoding range of distance values grows geometrically.

3.3 Dynamic Allocation

How many sequences of iterations are needed to fulfill MS-BFS130depends on how big is the diameter of graph110. However, computer100need not calculate the diameter of graph110before or during MS-BFS130, thereby avoiding a calculation whose complexity is a cubic (very expensive) function of graph size (vertex count).

Instead, computer100dynamically creates additional sequences of iterations on demand (just in time). When a current primitive integer type is exhausted, computer100dynamically switches to the next bigger primitive integer type, creates another distance matrix using that next integer type, and begins a next sequence of iterations. In this way, the selection of integer type width is deferred (not finalized when MS-BFS130starts).

An aspect ofFIG. 3that does not appear inFIG. 2is that steps302and304use different thresholds. Step304uses a threshold that is bigger than the threshold of step302. That is because sequence of iterations142uses primitive integer type162that encodes a range of distance values that is bigger than the value range for primitive integer type161of sequence of iterations141. Although not shown, immediately before each sequence of iterations, computer100creates another distance matrix using a next integer type.

4.0 Hardware Overview

The received code may be executed by processor404as it is received, and/or stored in storage device46, or other non-volatile storage for later execution.

5.0 Software Overview

FIG. 5is a block diagram of a basic software system500that may be employed for controlling the operation of computing system400. Software system500and its components, including their connections, relationships, and functions, is meant to be exemplary only, and not meant to limit implementations of the example embodiment(s). Other software systems suitable for implementing the example embodiment(s) may have different components, including components with different connections, relationships, and functions.

Software system500is provided for directing the operation of computing system400. Software system500, which may be stored in system memory (RAM)106and on fixed storage (e.g., hard disk or flash memory)110, includes a kernel or operating system (OS)510.

The OS510manages low-level aspects of computer operation, including managing execution of processes, memory allocation, file input and output (I/O), and device I/O. One or more application programs, represented as502A,502B,502C . . .502N, may be “loaded” (e.g., transferred from fixed storage110into memory106) for execution by the system500. The applications or other software intended for use on computer system400may also be stored as a set of downloadable computer-executable instructions, for example, for downloading and installation from an Internet location (e.g., a Web server, an app store, or other online service).

Software system500includes a graphical user interface (GUI)515, for receiving user commands and data in a graphical (e.g., “point-and-click” or “touch gesture”) fashion. These inputs, in turn, may be acted upon by the system500in accordance with instructions from operating system510and/or application(s)502. The GUI515also serves to display the results of operation from the OS510and application(s)502, whereupon the user may supply additional inputs or terminate the session (e.g., log off).

OS510can execute directly on the bare hardware520(e.g., processor(s)104) of computer system400. Alternatively, a hypervisor or virtual machine monitor (VMM)530may be interposed between the bare hardware520and the OS510. In this configuration, VMM530acts as a software “cushion” or virtualization layer between the OS510and the bare hardware520of the computer system400.

VMM530instantiates and runs one or more virtual machine instances (“guest machines”). Each guest machine comprises a “guest” operating system, such as OS510, and one or more applications, such as application(s)502, designed to execute on the guest operating system. The VMM530presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems.

In some instances, the VMM530may allow a guest operating system to run as if it is running on the bare hardware520of computer system500directly. In these instances, the same version of the guest operating system configured to execute on the bare hardware520directly may also execute on VMM530without modification or reconfiguration. In other words, VMM530may provide full hardware and CPU virtualization to a guest operating system in some instances.

In other instances, a guest operating system may be specially designed or configured to execute on VMM530for efficiency. In these instances, the guest operating system is “aware” that it executes on a virtual machine monitor. In other words, VMM530may provide para-virtualization to a guest operating system in some instances.

6.0 Cloud Computing