Patent ID: 9165042
Filing Date: 2015-10-20
Classification: G06F,G16C

Abstract:
1. A method of searching structural data in a database against one or more structural queries, the method comprising the steps of: specifying a desired minimum degree of similarity between the one or more structural queries and the structural data in the database, wherein each of said one or more structural queries is based on a structural representation of a graph; using a feature-graph matrix index and an edge-feature matrix index to exclude from consideration any structural data in the database that does not share the desired minimum degree of similarity with one or more of the structural queries based on said structural representation of said graph, wherein each entry of the feature-graph matrix index indicates a number of embeddings of a given feature in a given graph in the database to represent differences between a number of the one or more features present in the one or more structural queries based on said structural representation of said graph and a number of the one or more features present in the structural data in the database, and wherein the edge-feature matrix maps edges and features of the one or more structural queries and represents a limit on a minimum number of features in common between the one or more structural queries based on said structural representation of said graph and the structural data in the database based on a relaxation ratio of the one or more structural queries based on said structural representation of said graph, wherein said relaxation ratio is based on a maximum common subgraph between at least one of said structural queries and the structural data in the database, wherein said graph comprises said structural data comprising one or more features and wherein said one or more features comprise structures indexed in said structural data; and identifying the structural data in the database that shares the desired minimum degree of similarity with the one or more of the structural queries based on said structural representation of said graph.