International Business Machines Corporation

University of California

Andrey Balmin

John Sismanis

Yuanyuan Tian

Joel Leonard Wolf

Peter Haas

Kirsten Weale Hildrum

Vuk Ercegovac

Kevin Scott Beyer

Berthold Reinwald

Fatma Ozcan

Deepak Rajan

Rohit Madhukar Khandekar

Heasoo Hwang

Calisto Paul Zuzarte

Yannis Papakonstantinou

Anshul Dawra

Daniele Costante Zilio

Sauraj Goswami

Ashraf Aboulnaga

Evangelos Christidis

Fei Yen Chiang

Bin Bi

Erik Nijkamp

Liping Peng

Iman Elghandour

Wenlei Xie

Mir Hamid Pirahesh

Shirish Tatikonda

John A McPherson, Jr

Marcel Kutsch

Tam Minh Dai Tran

Viswanath Nagarajan

Jesse E Jackson

Konstantinos Karanasos

Chunyang Xia

Romulo Antonio Pereira Goncalves

Jonas Traub

Severin A Corsten

Rares Vernica

A method that includes generating, in a query pre-processor, a set of pre-computed materialized sub-graphs by executing a pre-processing dynamic random-walk based search for a bin of terms. The method also includes receiving, in a query processor, a search query having at least one search query term. In response to receiving the search query, the method includes accessing the set of pre-computed materialized sub-graphs. The accessing includes accessing a text index based on the search query term to retrieve a corresponding term group identifier and accessing the corresponding pre-computed materialized sub-graph based on the term group identifier. The method also includes executing a dynamic random-walk based search on only the corresponding pre-computed materialized sub-graph and based on the executing, retrieving nodes in the dataset and transmitting the nodes as results of the query.

Scaling dynamic authority-based search using materialized subgraphs

A computer-implemented method, according to one embodiment, includes: generating two or more sample graphs by sampling edges of a current snapshot of a dynamic graph, generating two or more partial results by executing an algorithm on the two or more sample graphs, combining the partial results into a final result, and incrementally maintaining the sample graphs. Edges included in the current snapshot of a dynamic graph and which were added to the dynamic graph in a most recent update thereto are included in each of the generated two or more sample graphs. Moreover, incrementally maintaining the sample graphs includes: subsampling each of the edges of each of the sample graphs at a given time by applying a Bernoulli trial, and combining a result of the subsampling with new edges received in a batch corresponding to the given time to form new sample graphs.

Dynamic interaction graphs with probabilistic edge decay

In one general embodiment, a computer-implemented method is provided for analyzing a dynamic graph. The computer-implemented method includes generating two or more sample graphs by sampling edges of a current snapshot of a dynamic graph. Additionally, the computer-implemented method includes generating two or more partial results by executing an algorithm on the sample graphs. Still yet, the computer-implemented method includes combining the partial results, from executing the algorithm on the sample graphs, into a final result.

A computer determines social media influencers in a specific topic by receiving a dataset of information associated with a website, the information including a first list of users of the website and a list of content that each user posts on the website, wherein each user is associated with other users from the first list of users. The computer determines initial values representing variables of the dataset of information on the website, wherein the variables include one or more topics for the list of content that each user from the first list of users posts on the website. The computer performs an iteration of Gibbs Sampling utilizing the initial values. The computer determines the one or more new values representing variables of the dataset represent a distribution of the one or more topics for the list of content that each user from the first list of users posts.

Identifying influencers for topics in social media

In one embodiment, a computer-implemented method includes selecting one or more sub-expressions of a query during compile time. One or more pilot runs are performed by one or more computer processors. The one or more pilot runs include a pilot run associated with each of one or more of the selected sub-expressions, and each pilot run includes at least partial execution of the associated selected sub-expression. The pilot runs are performed during execution time. Statistics are collected on the one or more pilot runs during performance of the one or more pilot runs. The query is optimized based at least in part on the statistics collected during the one or more pilot runs, where the optimization includes basing cardinality and cost estimates on the statistics collected during the pilot runs.

Dynamic query optimization with pilot runs

Stratified sampling of a plurality of records is performed. A plurality of records are partitioned into a plurality of splits, wherein each split includes at least a portion of the plurality of records. The split of the plurality of splits is provided to a mapper. The mapper assigns at least a portion the records of the at least one split to a group based on a strata of the assigned records, and filters the records of the group based on a comparison of the weights of the records to a local threshold of the mapper. The mapper updates the local threshold of the mapper by communicating with a coordinator. The mapper shuffles the group to a reducer, where the reducer filters the records of the group based on the weights of the records. The reducer provides a stratified sampling of the plurality of records based on the group.

Stratified sampling using adaptive parallel data processing

A computer-implemented method includes partitioning a plurality of records into a plurality of splits. Each split includes at least a portion of the plurality of records. The method further includes providing at least one split of the plurality of splits to a mapper. The mapper scans the input data set, transforms each input record using a map function, and extracts a grouping key in parallel. The method further includes assigning at least a portion the records of the at least one split to a group. Each assignment to the group is based on a strata of the assigned record, and filtering the records of the group. Each filtering is based on a comparison of a weight of a record to a local threshold of the mapper. The method further includes shuffling the group to a reducer and providing a stratified sampling of the plurality of records based on the group.

A method, computer-implemented system, and computer program product for creating indexes over XML data managed by a database system are provided. The method, computer-implemented system, and computer program product provide for receiving a workload for the XML data, the workload including one or more database statements, utilizing an optimizer of the database system to enumerate a set of one or more path expressions by creating a virtual universal index based on the workload received and matching a path expression to the virtual universal index, and recommending one or more path expressions from the set of one or more candidate path expressions to create the indexes over the XML data.

Index selection for XML database systems

Scheduling mechanisms for assigning data in a distributed file system to database workers are provided. In one embodiment, a method of and computer program product for assignment of data blocks to database workers are provided. A request for table data is received. Metadata for a plurality of blocks in a file system is retrieved from a metadata store. Each of the plurality of blocks contains a subset of the table data. A request for work is received from a requestor. An assignment of one or more of the plurality of blocks is provided to the requestor.

Adaptive fragment assignment for processing file data in a database

A computer determines social media influencers in a specific topic. The computer receives a dataset of information on a website, the information including a list of users of the website and a list of content that each user posts, wherein each user is associated with one or more other users. The computer identifies a plurality of variables associated with the dataset, wherein the plurality of variables represent the information of the dataset on the website. The computer executes a topic specific search based on the plurality of variables, the topic search providing at least another list of users representing influencers in a specific topic.

Embodiments relate to subgraph-based distributed graph processing. An aspect includes receiving an input graph comprising a plurality of vertices. Another aspect includes partitioning the input graph into a plurality of subgraphs, each subgraph comprising internal vertices and boundary vertices. Another aspect includes assigning one or more respective subgraphs to each of a plurality of workers. Another aspect includes initiating processing of the plurality of subgraphs by performing a series of processing steps comprising: processing the internal vertices and boundary vertices internally within each of the subgraphs; detecting that a change was made to a boundary vertex of a first subgraph during the internal processing; and sending a message from a first worker to which the first subgraph is assigned to a second worker to which a second subgraph is assigned in response to detecting the change that was made to the boundary vertex of the first subgraph.

Subgraph-based distributed graph processing

Techniques, systems, and articles of manufacture for automated scheduling management of MapReduce flow-graph applications. A method includes determining a job schedule of MapReduce jobs within each of multiple MapReduce flows in a cluster environment, wherein said job schedule does not violate a precedence relationship within the corresponding MapReduce flow and reduces makespan of the corresponding MapReduce flow, determining a flow schedule for the multiple MapReduce flows based on consideration of a given metric, wherein said flow schedule comprises a number of slots allotted to each of the multiple MapReduce flows, and wherein said number of slots is less than or equal to a number of the one or more MapReduce jobs within each corresponding MapReduce flow, and transforming each job schedule into the flow schedule to allocate resources for the multiple MapReduce flows in the cluster environment without violating a precedence constraint of the multiple MapReduce flows.

Automated scheduling management of MapReduce flow-graph applications

According to one embodiment of the present invention, a method for processing a query is provided. The method includes generating a set of pre-computed materialized sub-graphs from a dataset and receiving a search query having one or more search query terms. A particular one of the pre-computed materialized sub-graphs is accessed and a dynamic authority-based keyword search is executed on the particular one of the pre-computed materialized sub-graphs. Nodes in the dataset are then retrieved based on the executing, and a response to the search query is provided which includes the retrieved nodes.

Described herein are methods, systems, apparatuses and products for adaptive parallel data processing. An aspect provides providing a map phase in which at least one map function is applied in parallel on different partitions of input data at different mappers in a parallel data processing system; providing a communication channel between mappers using a distributed meta-data store, wherein said map phase comprises mapper data processing adapted responsive to communication with said distributed meta-data store; and providing data accessible by at least one reduce phase node in which at least one reduce function is applied. Other embodiments are disclosed.

Adaptive parallel data processing

Techniques for scheduling one or more MapReduce jobs in a presence of one or more priority classes are provided. The techniques include obtaining a preferred ordering for one or more MapReduce jobs, wherein the preferred ordering comprises one or more priority classes, prioritizing the one or more priority classes subject to one or more dynamic minimum slot guarantees for each priority class, and iteratively employing a MapReduce scheduler, once per priority class, in priority class order, to optimize performance of the one or more MapReduce jobs.

Growing community of inventors

San Jose, CA, United States of America

Andrey Balmin