International Business Machines Corporation

Ilie G Tanase

Ching-Yung Lin

Toyotaro Suzumura

Mark Richard Nutter

Mauricio J Serrano

Jason L Crawford

Jie Lu

Danny L Yeh

Chun-Fu Chen

Manoj N Kumar

Jose Eduardo Moreira

Pratap Chandra Pattnaik

Joefon Jann

Ettore Tiotto

William Pettit Horn

Kattamuri Ekanadham

Hao Yu

Gheorghe Almasi

Barnaby Dalton

Hanhong Xue

Tsai-Yang Jea

Serban C Maerean

Yaxun Liu

Wei Tan

Jinho Lee

Yinglong Xia

Yanbin Liu

Lifeng Nai

Warut Vijitbenjaronk

A novel distributed graph database is provided that is designed for efficient graph data storage and processing on modern computing architectures. In particular a single node graph database and a runtime & communication layer allows for composing a distributed graph database from multiple single node instances.

Distributed graph databases that facilitate streaming data insertion and queries by efficient throughput edge addition

Allocating distributed data structures and managing allocation of a symmetric heap can include defining, using a processor, the symmetric heap. The symmetric heap includes a symmetric partition for each process of a partitioned global address space (PGAS) system. Each symmetric partition of the symmetric heap begins at a same starting virtual memory address and has a same global symmetric break. One process of a plurality of processes of the PGAS system is configured as an allocator process that controls allocation of blocks of memory for each symmetric partition of the symmetric heap. Using the processor executing the allocator process, isomorphic fragmentation among the symmetric partitions of the symmetric heap is maintained.

Allocation of distributed data structures

Distributed graph databases that facilitate streaming data insertion and queries by reducing number of messages required to add a new edge by employing asynchronous communication

Distributed graph databases that facilitate streaming data insertion and low latency graph queries

A fine-grained scalable time-versioning support for large-scale property graph databases includes receiving a request, wherein the request includes an entity identifier (ID) and reference time information, and searching entries of a first table using the entity ID as a first key. Matching an entry is performed corresponding to the first key in the first table, determining the entry is valid based at least in part on comparing the reference time information of the request with stored time information for the entry, and responsive to the determination, creating a second key, wherein the second key concatenates an ID associated with the entity ID with the reference time information of the request. Searching a second table is performed having entries based at least in part on the second key, and responsive to searching the second table, retrieving data associated with the second key.

Fine-grained scalable time-versioning support for large-scale property graph databases

A data storage and retrieval system for a computer memory includes a stream graph engine extracting graph data from streaming data, the graph data occupying a sliding window and comprising a plurality of slices representing a set of contiguous graphs, and where each slice of the plurality of slices corresponds to a given graph structure and its properties at a particular time, the stream graph engine causing the computer memory to store an on-disk portion of the graph data including a key table, a timestamp table and a plurality of property files, wherein the key table comprises a plurality of pointers to corresponding entries of the timestamp table, wherein each of the entries of the timestamp table comprise a corresponding timestamp and a pointer to the properties files, wherein the properties files comprise properties of a corresponding graph of the set of contiguous graphs, an in-memory portion of the graph data having a cache data structure storing a subset of the key table, and a versioning control module storing evolving changes in the graph data in the computer memory.

Efficient property graph storage for streaming/multi-versioning graphs

Various embodiments execute a program with improved cache efficiency. In one embodiment, a first subset of operations of a program is performed on a plurality of objects stored in one or more data structures. The first subset of operations has a regular memory access pattern. After each operation in the first subset of operations has been performed, results of the operation are stored in one of the plurality of queues. Each queue in the plurality of queues is associated with a different cacheable region of a memory. A second subset of operations in the program is performed utilizing at least one queue in the plurality of queues. The second subset of operations utilizes results of the operations in the first subset of operations stored in the queue. The second subset of operations has an irregular memory access pattern that is regularized by localizing memory locations accessed by the second subset of operations to the cacheable region of memory associated with the at least one queue. Results of each operation performed in the second subset of operations are stored in memory.

Reducing memory access latency in scatter/gather operations

Techniques for determining connected components of a graph via incremental graph analysis algorithms are provided. In one example, a computer-implemented method comprises analyzing, by a system operatively coupled to a processor, a first differential value representing an initial incremental difference of elements between selected initial elements of an initial vector and selected input elements of an input vector associated with a graph. The method further comprises recurringly analyzing, by the system, a second differential value representing a subsequent incremental difference of elements between selected updated elements of an updated initial vector and selected additional elements of another input vector associated with the graph until the second differential value is zero.

Switching matrix representation for an incremental algorithm computing connected components

A graph processing system includes a graph API (Application Programming Interface), as executed by a processor on a computer, and that includes a plurality of graph operators to create graphs and to execute graph analytic applications on the created graphs, the graph operators supporting a creation and manipulation of multi-dimensional properties of graphs. A run-time system is executed by the processor and implements routines that dynamically adjust a plurality of representations and algorithms to execute sequences of operations on graph data. A library is accessible to the run-time system and stores a specification of calling signatures for the graph operators such that the graph operators can be called from any of various computer programming languages such that top-level algorithms received in an input graph application can be understood in the graph processing system when received in any of the various computer programming languages. Thereby the top-level algorithms written to the graph API are portable across multiple implementations.

Sophisticated run-time system for graph processing

Growing community of inventors

Somers, NY, United States of America

Ilie G Tanase