# US 2024/0004933 A1 · Minhash signatures as vertices for fuzzy string match on graph

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0004933 A1
- Document ID: US20240004933A1
- Status: Published application
- Kind: A1
- Application number: 17/852,901
- Filed: 2022-06-29
- Published: 2024-01-04
- Earliest claimed: 2022-06-29
- Assignees: TigerGraph, Inc.
- Applicants: TigerGraph, Inc.
- Inventors: Xinyu Chang; Yiming Pan; Thong Nguyen
- Web page: https://patentgrep.com/patent/US20240004933A1

## CPC

- G06F 16/90344: {by using string matching techniques}
- G06F 16/9014: {hash tables}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Utilizing a MinHash approach during a graph loading process, vertices with similar string property values can be indirectly connected through common intermediary vertices whose identifications (IDs) are the MinHash signature values. A method for fuzzy match on a graph comprises constructing a graph using a hashing technique, determining a similarity of hash signatures of at least two properties on the graph, and using the similarity in an application. The hashing technique may be MinHash, for example. Determining the similarity may comprise using Jaccard similarity or Levenshtein distance, for example. The application may be entity resolution or text search, for example.

## Claims

### Claim 1

A method for fuzzy match on a graph having at least one vertex and at least one edge, each vertex defining at least one property, the method comprising:
constructing a graph using a hashing technique;
determining a similarity of hash signatures of at least two properties on the graph; and
using the similarity in an application.

### Claim 2 (depends on 1)

The method of claim 1, wherein constructing the graph comprises determining the hash signatures of the at least two properties on the graph and storing the hash signatures on the graph as vertices.

### Claim 3 (depends on 2)

The method of claim 2, further comprising determining that the vertices have similar properties responsive to determining that the hash signatures of the at least two properties are similar.

### Claim 4 (depends on 1)

The method of claim 1, wherein the hashing technique is MinHash.

### Claim 5 (depends on 1)

The method of claim 1, wherein determining the similarity comprises using Jaccard similarity.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the similarity comprises using Levenshtein distance.

### Claim 7 (depends on 1)

The method of claim 1, wherein the application is entity resolution.

### Claim 8 (depends on 1)

The method of claim 1, wherein the application is text search.

### Claim 9 (depends on 1)

The method of claim 1, further comprising storing the graph in a storage.

### Claim 10

A method for fuzzy match on a graph having at least one vertex and at least one edge, each vertex defining at least one property, the method comprising:
constructing a graph using a hashing technique and a loading job;
performing a fuzzy match between vertices of the graph; and
using results of the fuzzy match in an application.

### Claim 11 (depends on 10)

The method of claim 10, further comprising defining the graph prior to constructing the graph.

### Claim 12 (depends on 10)

The method of claim 10, wherein constructing the graph comprises converting strings to be matched into a plurality of hash signature values.

### Claim 13 (depends on 10)

The method of claim 10, wherein constructing the graph comprises connecting edges of the entity that has a string property with hash signatures of the string value.

### Claim 14 (depends on 10)

The method of claim 10, wherein the hashing technique is MinHash.

### Claim 15 (depends on 10)

The method of claim 10, wherein performing the fuzzy match comprises using Jaccard similarity.

### Claim 16 (depends on 10)

The method of claim 10, wherein performing the fuzzy match comprises using Levenshtein distance.

### Claim 17 (depends on 10)

The method of claim 10, wherein the application is entity resolution.

### Claim 18 (depends on 10)

The method of claim 10, wherein the application is text search.

### Claim 19

A system comprising:
a schema definition engine configured to define a graph with hash signature vertices;
a loading logic engine configured to define a loading job to construct the graph;
a data ingestion engine configured to construct the graph using the loading job; and
a fuzzy matching engine configured to perform fuzzy matching on the graph.

### Claim 20 (depends on 19)

The system of claim 19, wherein the hash signature vertices are generated using MinHash, and the fuzzy matching uses one of Jaccard similarity or Levenshtein distance.
