International Business Machines Corporation

Anastasios Kementsietsidis

Kavitha Srinivas

Achille Belly Fokoue-Nkoutche

Mihaela Ancuta Bornea

Julian Timothy Dolby

Songyun Duan

Wangchao Le

Oktie Hassanzadeh

Feifei Li

Min Wang

Michael James Ward

Lipyeow Lim

Spyros Kotoulas

Guo Tong Xie

Wen Sun

Gang Hu

Octavian Udrea

Achille Fokoue

Muhammad Mustafa Rafique

Marcelo Arenas

Gonzalo Diaz

Mudhakar Srivatsa

Alfio Massimiliano Gliozzo

Rajesh Ramkrishna Bordawekar

Aditya Anand Kalyanpur

James J Fan

Marco Luca Sbodio

Pierpaolo Tommasi

Joana M Fonseca Da Trindade

Enela Pema

Bryant Wei Lun Kok

A schema for a dataset is identified by identifying a dataset comprising data and relationships between data pairs. An original schema is identified for the dataset. This original schema comprises an organizational structure. An initial fit between the dataset and the original schema is determined. The initial fit quantifying a conformity of the data in the dataset to the organizational structure of the original schema. A plurality of additional schemas are identified. Each additional schema is a distinct organizational schema. The dataset is partitioned into a plurality of subsets. Each subset comprises a modified fit quantifying a modified conformity of subset data in each subset to one of the original schema and the additional schemas. The modified fit is greater than the original fit.

Determining the schema of a graph dataset

An apparatus and method of identifying semantically related records, including receiving input data from an input device, splitting the input data into a plurality of clusters according to semantic relationship, each of the clusters including a plurality of source terms and a plurality of target terms, transforming each of the plurality of clusters based on the transformation which includes tokenization of the plurality of clusters, for each of the plurality of clusters that are transformed, finding relatedness scores of a plurality of semantic relatedness measures with the plurality of target terms, building a vector of similarity scores for each of the plurality of target terms, and for each of the plurality of source terms, selecting a predetermined number of the plurality of target terms according to the similarity scores.

Method and apparatus for identifying semantically related records

A system for identifying a schema for storing graph data includes a database containing a graph dataset of data and relationships between data pairs and a list of storage methods that each are a distinct structural arrangement of the data and relationships from the graph data set. An analyzer module collects statistics for the graph dataset, and a data classification module uses the collected statistics to calculate metrics describing the data and relationships in the graph dataset, uses the calculated metrics to group the data and relationships into a plurality of graph dataset subsets and associates each graph dataset subset with one of the plurality of storage methods. The resulting group of storage methods associated with the plurality of graph dataset subsets includes a unique storage method for each graph dataset subset. The data and relationships in each graph dataset subset are arranged in accordance with associated storage methods.

Method and apparatus for identifying the optimal schema to store graph data in a relational store

Various embodiments virtualize data across heterogeneous formats. In one embodiment, a plurality of heterogeneous data sources is received as input. A local schema graph including a set of attribute nodes and a set of type nodes is generated for each of the plurality of heterogeneous data sources. A global schema graph is generated based on each local schema graph that has been generated. The global schema graph comprises each of the local schema graphs and at least one edge between at least one of two or more attributes nodes and two or more type nodes from different local schema graphs. The edge indicates a relationship between the data sources represented by the different local schema graphs comprising the two or more attributes nodes based on a computed similarity between at least one value associated with each of the two or more attributes nodes.

Data virtualization across heterogeneous formats

A system for storing graph data as a multi-dimensional cluster having a database with a graph dataset containing data and relationships between data pairs and a schema list of storage methods that use a table with columns and rows associated with data or relationships. An analyzer module to collect statistics of a graph dataset and a dimension identification module to identify a plurality of dimensions that each represent a column in the table. A schema creation and loading module creates a modified storage method and having a plurality of distinct table blocks and a plurality of table block indexes, one index for each table block and arranges the data and relationships in the given graph dataset in accordance with the modified storage method to create the multi-dimensional cluster.

Method and apparatus for storing sparse graph data as multi-dimensional cluster

Embodiments include methods, systems and computer program products for storing graph data for a directed graph in a relational database. Aspects include creating a plurality of relational tables for the graph data, using a processor on a computer, the plurality of relational tables including adjacency tables and attribute tables. Each row of the attribute tables is dedicated to a subject of the graph data in the dataset and stores a JavaScript Object Notation (JSON) object corresponding to the subject. Each row of the adjacency tables includes a hashtable containing properties and values of the subject for that row.

Storing graph data in a relational database

Various embodiments of the invention relate to optimizing storage of schema-less data. At least one of a schema-less dataset including a plurality of resources one or more query workloads associated with the plurality of resources is received. Each resource is associated with at least a plurality of properties. At least one set of co-occurring properties from the plurality of properties is identified. A graph including a plurality of nodes is generated. Each of the nodes represents a unique property in the set of co-occurring properties. The graph further includes an edge connecting each node representing a pair of co-occurring properties. A schema is generated based on the graph that assigns a column identifier from a table to each unique property represented by one of the nodes in the graph.

Optimizing sparse schema-less data in data stores

Data elements from data sources and having a data value set are linked by using hash functions to determine a dimensionally reduced instance signature for each data element based on all data values associated with that data element to yield a plurality of dimensionally reduced instance signatures of equivalent fixed size such that similarities among the data values in the data value sets across all data elements is maintained among the plurality of instance signatures. Candidate pairs of data elements to link are identified using the plurality of instance signatures in locality sensitive hash functions, and a similarity index is generated for each candidate pair using a pre-determined measure of similarity. Candidate pairs of data elements having a similarity index above a given threshold are linked.

Linking data elements based on similarity data values and semantic annotations

Multiquery optimization is performed in the context of RDF/SPARQL. Heuristic algorithms partition an input batch of queries into groups such that each group of queries can be optimized together. The optimization incorporates an efficient algorithm to discover the common sub-structures of multiple SPARQL queries and an effective cost model to compare candidate execution plans. No assumptions are made about the underlying SPARQL query engine. This provides portability across different RDF stores.

Scalable multi-query optimization for SPARQL

A method for query evaluation comprises receiving a query over a set of distributed data sources, decomposing the query into a set of sub-queries of the query, evaluating each sub-query in the set of sub-queries with respect to each data source in the set of distributed data sources, wherein evaluating comprises determining which data sources in the set of distributed data sources are capable of answering each sub-query and at what cost, computing a set of distributed plans by composing one or more of the sub-queries in one or more of the data sources, evaluating each plan in the set of distributed plans, selecting a sub-set of plans from the set of distributed plans to be executed for responding to the query, executing the selected sub-set of plans, and returning results of the query.

Systems and methods for query evaluation over distributed linked data stores

Methods and systems for determining schema element types are shown that include pooling potential annotations for an element of an unlabeled schema from a plurality of heterogeneous sources, scoring the pool of potential annotations according to relevancy using information using instance information from the plurality of heterogeneous sources to produce a relevancy score, and annotating the element of the unlabeled schema using the most relevant potential annotations.

Annotating schema elements based on associating data instances with knowledge base entities

Systems and methods for optimizing a query, and more particularly, systems and methods for finding optimal plans for graph queries by casting the task of finding the optimal plan as an integer programming (ILP) problem. A method for optimizing a query, comprises building a data structure for a query, the data structure including a plurality of components, wherein each of the plurality of components corresponds to at least one graph pattern, determining a plurality of flows of query variables between the plurality of components, and determining a combination of the plurality of flows between the plurality of components that results in a minimum cost to execute the query.

Growing community of inventors

New York, NY, United States of America

Anastasios Kementsietsidis