International Business Machines Corporation

Ching-Tien Ho

Rakesh Agrawal

Lucian Popa

Jehoshua Bruck

Oktie Hassanzadeh

Mauricio Antonio Hernandez-Sherrington

Yunyao Li

Ramakrishnan Srikant

Robert E Cypher

Mauricio A Hernandez

Nimrod Megiddo

Shivakumar Vaithyanathan

Hovey Raymond Strong

Cynthia Dwork

Mary Ann Roth

Roberto Javier Bayardo

Huaiyu Zhu

John Christopher Shafer

Lingling Yan

Benny Kimelfeld

Dimitrios Gunopulos

Mohammed J Zaki

Sunita Sarawagi

Sebastian Johannes Blohm

Wook-Shin Han

Vivian Yaw-Wen Chu

Shlomo Kipnis

Mandayam T Raghunath

Haifeng Jiang

Data records are linked across a plurality of datasets. Each dataset contains at least one data record, and each data record is associated with an entity and includes one or more attributes of that entity and a value for each attribute. Values associated with attributes are compared across datasets, and matching attributes having values that satisfy a predetermined similarity threshold are identified. In addition, linkage points between pairs of datasets are identified. Each linkage point links one or more pairs of data records. Each data record in the pair of data records is contained in one of a given pair of datasets, and each pair of data records is associated with a common entity having matching attributes in the given pair of datasets. Data records associated with the common entities are linked across datasets using the identified linkage points.

Discovery of linkage points between data sources

Methods and systems for discovery of linkage points between data sources

A method includes receiving one or more natural language dependency parse trees as input. A hardware processor is used for processing the dependency parse trees by creating a mapping from nodes of the one or more dependency parse trees into actions, roles and contextual predicates. The mapping is used for information extraction. The actions include the verbs along with attributes of the verbs. The roles include arguments for the verbs. The contextual predicates include modifiers for the verbs.

Facilitating information extraction via semantic abstraction

Various embodiments of a method, system and article of manufacture to discover relationships among a first set of elements and a second set of elements are provided. At least one metric algorithm is identified based on a metric selection parameter. A raw result is determined based on the at least one metric algorithm, a first specified structural description of the first set of elements and a second specified structural description of the second set of elements. The raw result comprises a plurality of relationship measurements and the raw result is ordered. In some embodiments, a balanced result is produced based on the raw result and a matching strategy algorithm. In other embodiments, the matching strategy algorithm is identified based on a matching strategy selection parameter.

Tolerant and extensible discovery of relationships in data using structural information and data analysis

A computer-implemented method for use with an extensible markup language (XML) document includes inputting a high-level mapping specification for a schema mapping; and generating a target XML document based on the mapping. The method may perform schema mapping-based XML transformation as a three-phase process comprising tuple extraction, XML-fragment generation, and data merging. The tuple extraction phase may be adapted to handle streamed XML data (as well as stored/indexed XML data). The data merging phase may use a hybrid method that can dynamically switch between main memory-based and disk-based algorithms based on the size of the XML data to be merged.

Scalable algorithms for mapping-based XML transformation

Described herein are methods, systems, apparatuses and products for automatically discovering patterns in a text corpus. An aspect provides extracting at least one context string related to at least one annotator from the at least one text corpus; analyzing the at least one context string for at least one sequence, the at least one sequence comprised of at least one subsequence; determining at least one sequence signature for each at least one sequence by applying applicable rules to the at least one sequence; and grouping the at least one sequence signature into at least one group.

Systems and methods for information extraction using contextual pattern discovery

A method and system for generating a query implementing a schema mapping. A mapping M is provided from a schema S to a schema T, where M relates S to T, and M includes a plurality of constraints. Schemas S and T each include one or more elements, and T includes at least one set type element. Mapping M is expressed in terms of at least one nested tuple-generating dependency. A query Q is generated where Q is capable of applying M to an input instance I to result in an output instance J, where I conforms to S, J conforms to T, and I and J satisfy the plurality of constraints. Instance J is in partitioned normal form (i.e., satisfies minimal union semantics) and includes no duplicate element instances.

Mapping-based query generation with duplicate elimination and minimal union

A user can easily organize computerized document folders by associating a few sample documents in the document database with each folder. The present invention learns folder profiles based on the sample documents and moves the remaining documents into the folders accordingly. In this way, the user can construct new folders, or rearrange existing folders, or cause the computer to automatically rearrange and maintain the folders. This is particularly useful for managing a database of perhaps thousands of emails.

System and method for organizing repositories of semi-structured documents such as email

A method and system for generating a decision-tree classifier in parallel in a shared-memory multiprocessor system is disclosed. The processors first generate in the shared memory an attribute list for each record attribute. Each attribute list is assigned to a processor. The processors independently determine the best splits for their respective assigned lists, and cooperatively determine a global best split for all attribute lists. The attribute lists are reassigned to the processors and split according to the global best split into the lists for child nodes. The split attribute lists are again assigned to the processors and the process is repeated for each new child node until each attribute list for the new child nodes includes only tuples of the same record class or a fixed number of tuples.

Parallel classification for data mining in a shared-memory multiprocessor system

A method for performing a range max/min query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: partitioning the data cube into multi-level multi-dimensional blocks which are represented by a tree structure; determining the index to the maximum or minimum value for each block; generating a range max/min result from the values of the cells selected from the cells in the query region Q, and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q, using the tree structure and determined cell indexes. A branch-and-bound method is used to repeatedly reduce the size of the query region from a cell within the region, based on sub-trees whose roots are cells in the region. To further improve the method performance, one or more reference arrays may also be used to quickly traverse the tree in determining the max/min cell indexes.

Method and system for performing range max/min queries on a data cube

Disclosed is a method and system for performing a partial-sum query in a database in which the data is represented as a multi-dimensional data cube. The data cube is partitioned into multi-dimensional blocks. One or more covering codes are then selected for each block, and a group of partial-sums is computed for each block based on its covering codes. At query time, the query result is generated by combining the partial-sums for those blocks that intersect with the query subset. To improve the query response time and reduce system storage requirements, the covering codes are preferably augmented as single-weight extended covering codes or composition-extended covering codes. Also, a second partial-sum may also be computed for each block to efficiently find its partial sum, based on the block's first partial-sums and the bit-position differences between selected codewords for the block and bit strings representing the cell indexes of the blocks intersecting with the query subset.

Method and system for performing partial-sum queries on a data cube

A method for performing a range-sum query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: selecting a subset of the dimensions of the data cube; computing a set of prefix-sums along the selected dimensions, based on the aggregate values in the cube corresponding the queried ranges; and generating a range-sum result based on the computed prefix-sums. Two d-dimensional arrays A and P are used for representing the data cube and the prefix-sums of the data cube, respectively. By maintaining the prefix-sum array P of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query, using the inverse binary operator of the SUM operator. Alternatively, only auxiliary information for any user-specified fraction of the size of the d-dimensional data cube is maintained, to minimize the required system storage. The answer to a range query may now require access to some cells of the data cube in addition to the auxiliary information, but the average time complexity is still reduced significantly.

Method and system for performing range-sum queries on a data cube

A method and apparatus are disclosed for achieving collective consistency in the detection and reporting of failures in a distributed computing system having multiple processors. Each processor is capable of being called by a parallel application for system status. Initially, each processor sends the other processors its view on the status of the processors. It then waits for similar views from other processors except those regarded as failed in its own view. If the received views are identical to the view of the processor, the processor returns its view to the parallel application. In a preferred embodiment, if the views are not identical to its view, the processor sets its view to the union of the received views and its current view. The steps are then repeated. Alternately, the steps are repeated if the processor does not have information that each of the processors not regarded as failed in its view forms an identical union view. In another preferred embodiment, the method is terminated if a quorum is not formed by the processors which are not regarded as failed. Alternatively, after sending its view, the processor waits for an exit condition. Depending on the exit condition, the processor sets its view to a quorum view and sends a 'DECIDE' message to the other processors. In another embodiment, the processor updates its view and the method steps are repeated.

Method and system for achieving collective consistency in detecting

A matrix transpose method for transposing any size matrix on a 2-dimensional mesh multi-node system with circuit-switched-like routing in the iterative and recursive forms. The matrix transpose method involves a two-level decomposition technique of first partitioning each mesh on a diagonal axis into four submeshes and then further partitioning each of the four submeshes on the diagonal axis into four submeshes. The transposition of all off-diagonal submatrices can be performed concurrently and the transposition of all successive on-diagonal submatrices can be performed iteratively or recursively.

Growing community of inventors

San Jose, CA, United States of America

Ching-Tien Ho