# US 2026/0093703 A1 · 1-hop sub-query result caches for graph databases

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

- Number: US 2026/0093703 A1
- Document ID: US20260093703A1
- Status: Published application
- Kind: A1
- Application number: 19/009,020
- Filed: 2025-01-03
- Published: 2026-04-02
- Earliest claimed: 2024-09-27
- Assignees: eBay Inc.; University of Southern California
- Applicants: eBay Inc.; University of Southern California
- Inventors: Hieu Trung NGUYEN; Shahram GHANDEHARIZADEH; Jun LI
- Web page: https://patentgrep.com/patent/US20260093703A1

## CPC

- G06F 16/24552: {Database cache management}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Some aspects relate to technologies for graph databases with 1-hop sub-query result caching. In accordance with some aspects, cache entries are generated that comprise key-value pairs, each having a cache key based on a vertex identifier of a vertex from a 1-hop sub-query instance and a value based on results of a 1-hop graph traversal from the vertex based on the 1-hop sub-query instance. A cache key can also be based on a property value of a predicate from a 1-hop sub-query instance. During graph query processing, a 1-hop sub-query instance is obtained based on the graph query. A cache key is generated using a vertex identifier for the vertex from the 1-hop sub-query instance. A lookup is performed in the cache data using the cache key, and an output is provided using one or more leaf vertex identifiers from a value of a cache entry having the cache key.

## Claims

### Claim 1

One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations, the operations comprising:
obtaining a 1-hop sub-query instance corresponding to a 1-hop graph traversal from a vertex in a graph database, wherein the 1-hop sub-query instance includes a predicate on an edge property or a leaf vertex property;
generating a cache key using a vertex identifier for the vertex from the 1-hop sub-query instance and a property value from the predicate;
performing a lookup in cache data using the cache key, the cache data comprising cache entries, each cache entry comprising a key-value pair;
responsive to identifying a cache entry having the cache key, obtaining one or more leaf vertex identifiers from a value of the cache entry; and
providing an output using the one or more leaf vertex identifiers.

### Claim 2 (depends on 1)

The one or more computer storage media of claim 1, wherein the operations further comprise:
receiving a graph query;
analyzing the graph query to identify a sequence of sub-queries; and
identifying the 1-hop sub-query instance based on a first sub-query from the sequence of sub-queries.

### Claim 3 (depends on 2)

The one or more computer storage media of claim 2, wherein the 1-hop sub-query instance is identified by determining the first sub-query matches a first sub-query template from a plurality of sub-query templates.

### Claim 4 (depends on 3)

The one or more computer storage media of claim 3, wherein the cache key is generated using a sub-query template identifier for the first sub-query template.

### Claim 5 (depends on 4)

The one or more computer storage media of claim 4, wherein a plurality of leaf vertex identifiers are obtained based on the value of the cache entry, and wherein the operations further comprise:
obtaining a plurality of subsequent 1-hop sub-query instances using the plurality of leaf vertex identifiers and a second sub-query from the sequence of sub-queries;
obtaining, from the cache data and/or graph data from the graph database, a set of one or more leaf vertex identifiers for each subsequent 1-hop sub-query instance; and
wherein the output is generated using a combined set of leaf vertex identifiers provided by combining the set of one or more leaf vertex identifiers for each of the plurality of subsequent 1-hop sub-query instances.

### Claim 6 (depends on 5)

The one or more computer storage media of claim 5, wherein obtaining a first set of one or more leaf vertex identifiers for a first subsequent 1-hop sub-query instance comprises:
generating a second cache key for the first subsequent 1-hop sub-query instance using a second vertex identifier for a second vertex from the first subsequent 1-hop sub-query instance, the second vertex comprising a leaf vertex identifier from the plurality of leaf vertex identifiers;
performing a lookup in the cache data using the second cache key for the first subsequent 1-hop sub-query instance; and
responsive to not identifying a second cache entry having the second cache key, querying the graph data to obtain the first set of one or more leaf vertex identifiers for the first subsequent 1-hop sub-query instance.

### Claim 7 (depends on 1)

The one or more computer storage media of claim 1, wherein obtaining the one or more leaf vertex identifiers from the value of the cache entry comprises deserializing and/or decompressing the value to obtain the one or more leaf vertex identifiers.

### Claim 8

A computer-implemented method comprising:
obtaining a 1-hop sub-query instance corresponding to a 1-hop graph traversal from a vertex in a graph database that includes a predicate on an edge property or a leaf vertex property;
obtaining a cache key using a vertex identifier for the vertex from the 1-hop sub-query instance and a property value from the predicate;
querying graph data in a graph database using the 1-hop sub-query instance to obtain one or more leaf vertex identifiers;
generating a value using the one or more leaf vertex identifiers; and
storing a key-value pair as a cache entry in cache data for the graph database using the cache key and the value.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein the method is performed by the graph database as a single transaction.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8, wherein the 1-hop sub-query instance is obtained in response to a cache miss on the cache data for the 1-hop sub-query instance when processing a graph query.

### Claim 11 (depends on 10)

The computer-implemented method of claim 10, wherein the method is performed asynchronously from processing the graph query.

### Claim 12 (depends on 8)

The computer-implemented method of claim 8, wherein the 1-hop sub-query instance is obtained using a sub-query template and the vertex identifier.

### Claim 13 (depends on 12)

The computer-implemented method of claim 12, wherein the sub-query template comprises a predicate with a placeholder for a property of an edge or a leaf vertex, and wherein the 1-hop sub-query instance is obtained by replacing the placeholder with a property value for the property, and wherein the cache key is generated using the property value.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, wherein the 1-hop sub-query instance is obtained by analyzing historical query information for the graph database.

### Claim 15

A computer system comprising:
a processor; and
a computer storage medium storing computer-useable instructions that, when used by the processor, causes the computer system to perform operations comprising:
receiving a graph update for a graph database;
generating one or more impacted cache keys based on the graph update; and
modifying a cache entry for each impacted cache key, each cache entry comprising a key-value pair for a 1-hop sub-query instance corresponding to a 1-hop graph traversal of graph data in the graph database.

### Claim 16 (depends on 15)

The computer system of claim 15, wherein the graph update comprises one or more selected from the following: adding an edge, changing a property of an edge, deleting an edge, adding a vertex, changing a property of a vertex, and deleting a vertex.

### Claim 17 (depends on 15)

The computer system of claim 15, wherein at least one impacted cache key is generated using a vertex identifier for a vertex impacted by the graph update.

### Claim 18 (depends on 15)

The computer system of claim 15, wherein modifying a first cache entry for a first impacted cache key comprises invalidating the first cache entry or refilling a value of the first cache entry based on the graph update.

### Claim 19 (depends on 15)

The computer system of claim 15, wherein the operations and one or more modifications to graph data in the graph database based on the graph update are performed by the graph database as a write transaction.

### Claim 20 (depends on 15)

The computer system of claim 15, wherein the operations further comprise:
determining a graph update type for the graph update; and
wherein the one or more impacted cache keys are generated based and the graph update type.
