International Business Machines Corporation

Kubilay Atasu

Christoph Hermann Hagleitner

Raphael C Polig

Silvio Dragone

Jan Van Lunteren

Akihiro Nakayama

Tong Xu

Charalampos Pozidis

Thomas Mittelholzer

Thomas P Parnell

Cesar Berrospi Ramis

Jason Raymond Baumgartner

Nikolas Ioannou

Michail Vlachos

Mitra Purandare

Frederick Ralph Reiss

Celestine Duenner

Jonathan Bruno Rohrer

Vasileios Vasileiadis

Robert R McCune

Florian Dorfler

Florian Doerfler

Two sets Xand Xof histograms of words, and a vocabulary V are accessed. Each of the two sets is representable as a sparse matrix, each row of which corresponds to a histogram. Each histogram is representable as a sparse vector, whose dimension is determined by a dimension of the vocabulary. Two phases compute distances between pairs of histograms. The first phase includes computations performed for each histogram and for each word in the vocabulary to obtain a dense, floating-point vector y. The second phase includes computing, for each histogram, a sparse-matrix, dense-vector multiplication between a matrix-representation of the set Xof histograms and the vector y. The multiplication is performed to obtain distances between all histograms of the set Xand each histogram X[j]. Distances between all pairs of histograms are obtained, based on which distances between documents can subsequently be assessed.

Low-complexity methods for assessing distances between pairs of documents

In an approach for construing similarities between datasets, a processor accesses a pair of sets of feature weights, wherein the sets of feature weights include a query dataset and comprises first weights associated to first features and a reference dataset and comprises second weights associated to second features. Based on similarities between the first features and the second features, a processor discovers flows from the first features to the second features, wherein the flows maximize an overall similarity between the pair of sets of feature weights. Based on the similarities and the flows, a processor computes pair contributions to the overall similarity in order to obtain contributive elements, wherein the pair contributions are contributions of pairs joining the first features to the second features. A processor ranks the contributive elements to obtain respective ranks. A processor returns a result comprising the contributive elements and indications to the respective ranks.

Construing similarities between datasets with explainable cognitive methods

The example embodiments of the invention notably are directed to a computer-implemented method for assessing distances between pairs of histograms. Each of the histograms is a representation of a digital object; said representation comprises bins associating weights to respective vectors. Such vectors represent respective features of said digital object. This method basically revolves around computing distances between pairs of histograms. That is, for each pair {p, q} of histograms p and q of said pairs of histograms, the method computes a distance between p and q of said each pair {p, q}. In more detail, said distance is computed according to a cost of moving p into q, so as to obtain a flow matrix F, whose matrix elements Findicate, for each pair {i,j} of bins of p and q, how much weight of a bin i of p has to flow to a bin j of q to move p into q. This is achieved by minimizing a quantity &#x3a3;F&#xb7;C, where Cis a matrix element of a cost matrix C representing said cost. Said quantity &#x3a3;F&#xb7;Cis minimized under two flow constraints, which, interestingly, include a relaxed flow constraint F&#x2264;r, in addition to a complementary flow constraint. The relaxed flow constraint F&#x2264;ris applied for at least some of the pairs {i,j}, with requal to por q, where pand qare weights associated to bins i and j of p and q, respectively, and the complementary flow constraint is either an out-flow constraint &#x3a3;F=pif r=qor an in-flow constraint &#x3a3;F=qif r=p. The invention is further directed to related computer program products.

Assessing distances between pairs of histograms based on relaxed flow constraints

A method for parallelizing a training of a model using a matrix-factorization-based collaborative filtering algorithm may be provided. The model can be used in a recommender system for a plurality of users and a plurality of items. The method includes providing a sparse training data matrix, selecting a number of user-item co-clusters, and building a user model data matrix by matrix factorization such that a computational load for executing the determining updated elements of the factorized sparse training data matrix is evenly distributed across the heterogeneous computing resources.

Load-balancing training of recommender system for heterogeneous systems

A cascaded finite-state-transducer array includes a plurality of finite-state-transducers, the finite-state-transducers being distributed in space. The finite-state-transducer array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types. Each data stream on a dedicated data transfer channel may transmit a particular data type, which may be sorted in increasing order of start offsets or token IDs.

Hardware compilation of cascaded grammars

In one embodiment, a computer-implemented method includes receiving a regular expression (regex) and input data. One or more spans are identified representing one or more matches in which the regex matches at least a portion of the input data. Each span corresponds to a corresponding match and includes a start offset of the corresponding match in the input data and an end offset of the corresponding match in the input data. The one or more matches are identified in a sequence. An order of the sequence of the one or more spans is modified. One or more filtered spans are generated, by a computer processor, by filtering out a subset of the one or more spans that are each contained by at least one other span in the one or more spans. The identifying, the modifying, and the filtering are performed at streaming rate.

Detecting longest regular expression matches

One or more embodiments may provide the capability to enumerate maximal cliques of graph data by constructing and traversing a search tree through a single sequential pass on an adjacency list. The adjacency list may be generated so as to enable the at least one maximal clique to be generated in one single sequential pass.

Graph data representation and pre-processing for efficient parallel search tree traversal

A method is provided for searching a graph to identify cliques using a set of processing elements (PEs), a first PE of the set of PEs having access to an adjacency list of a seed vertex of the graph, the adjacency list of the seed vertex including a set of vertices. The method includes: generating a data structure for each intermediate vertex of the set of vertices, the data structure indicating the respective intermediate vertex and an additional list of intermediate vertices of the set of vertices; storing the generated data structures; for each buffered data structure, receiving the buffered data structure and configuring the available PE to receive an adjacency list of the intermediate vertex indicated in the respective data structure and to select from the adjacency list a set of further vertices that are adjacent to the seed vertex and are part of the additional list.

Method for detecting cliques in graphs

A non-deterministic finite state machine module for use in a regular expression matching system. The system includes a computational unit implementing a non-deterministic finite state machine representing a regular expression, wherein the computational unit is configured to: receive an input data stream, wherein an occurrence of the regular expression is determined, and an activation signal; process the input data stream with respect to the non-deterministic finite state machine depending on the activation signal; and provide at least one branch data output for initializing an additional non-deterministic finite state machine module if the processing of an element of the input data stream according to the non-deterministic finite state machine results in a branching of a processing thread.

Non-deterministic finite state machine module for use in a regular expression matching system

A device for matching, in input data, a regular expression with back-references, represented by a finite-state machine (FSM). The device comprises a plurality of parallel processing elements (PPEs), an interconnection network for interconnecting the PPEs with each other, and a memory for receiving and storing input data. The PPEs process the input data stored in the memory, based on backtracking to process the back-references, and implement FA next state logic to generate new active FA configurations or mark themselves as available to receive active FA configurations. The interconnection network retrieves active FA configurations from the PPEs and allocates the active FA configurations to available PPEs. The PPEs are configured to match a regular expression in the input data.

Regular expression matching with back-references using backtracking

A system and method to hardware-accelerate finite state transducer libraries and their compilation toolchains. In an embodiment, a computer-implemented method for partitioning an UIMA-PEAR file into software-based and hardware-accelerated components may comprise creating a data-flow graph representation of the UIMA-PEAR-file, flattening hierarchies of the data-flow graph representation, and selecting the components to be hardware accelerated from the flattened hierarchies of the data-flow graph representation based on data dependencies of data types produced and consumed by each component of the flattened data-flow graph.

Accelerated content analytics based on a hierarchical data-flow-graph representation

A technique for determining scan lanes is provided. For a set of patterns, a number of scan lanes is estimated to be utilized on an accelerator. The number of the scan lanes estimated for the set of patterns is iteratively incremented to optimize a throughput of the accelerator. The set of patterns is distributed to the number of the scan lanes as a distribution, and each one of the scan lanes has a predetermined number of engines. A size of a memory space is evaluated that is needed for the distribution to distribute the set of patterns onto the number of scan lanes.

Compiling pattern contexts to scan lanes under instruction execution constraints

A method for determining correctness of a transformation between a first finite state automaton (FSA) and a second FSA, wherein the first FSA comprises a representation of a regular expression, and the second FSA comprises a transformation of the first FSA includes determining a third FSA, the third FSA comprising a cross product of the second FSA and a post-processor; determining whether the first FSA and the third FSA are equivalent; and in the event that the first FSA is determined not to be equivalent to the third FSA, determining that the transformation between the first FSA and the second FSA is not correct.

Growing community of inventors

Horgen, Switzerland

Kubilay Atasu