US 12,579,121 B2Granted

Management of a secondary vertex index for a graph

AssigneeGraphSQL, Inc.

InventorsSongting Chen, Yu Xu, Dan Hu, Zixuan Zhuang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems, methods, and software described herein manage and use a secondary index associated with graph vertices. In one example, a graph management system may generate an index for vertices in a graph associated with an attribute type, wherein each of the vertices include a unique identifier and one or more attributes, and wherein each entry in the index associates at least one attribute value with one or more of the vertices with an attribute that qualifies for the entry. The graph management system further generates one or more delta indexes associated with the index based on modifications to the graph and generates query responses using the index and at least one of the one or more delta indexes.

Claims18

Dependent claims

A method comprising:

generating an index for searching vertices in a graph, wherein the vertices each comprise a unique identifier and one or more attributes that each correspond to an attribute type of a plurality of attribute types, wherein the index corresponds to a first attribute type of the plurality of attribute types, wherein each entry of a plurality of entries in the index associates a set of attribute values for the first attribute type with one or more of the unique identifiers for one or more of the vertices having the set of attribute values for the entry, and wherein at least one entry of the plurality of entries comprises at least two of the unique identifiers corresponding to at least two of the vertices;
generating one or more delta indexes, wherein each of the one or more delta indexes comprises a delta entry identifying one or more modifications to the graph made during a specific time period, and wherein the delta entry corresponds to one of the plurality of entries in the index;
obtaining a query to the graph associated with the first attribute type, wherein the query identifies a time period of interest;
identifying, based on the time period of interest in the query, a first delta index from the one or more delta indexes, the first delta index having the specific time period corresponding to the time period of interest;
and
generating a response to the query based at least on the index and the first delta index.

3 more elements

A computing system comprising:

a processor;
and
a memory device operably coupled to the processor and having stored thereon program instructions that, upon execution by the processor, cause the processor to:
generate an index for searching vertices in a graph, wherein the vertices each comprise a unique identifier and one or more attributes that each correspond to an attribute type of a plurality of attribute types, wherein the index corresponds to a first attribute type of the plurality of attribute types, wherein each entry of a plurality of entries in the index associates a set of attribute values for the first attribute type with one or more of the unique identifiers for one or more of the vertices having the set of attribute values for the entry, and wherein at least one entry of the plurality of entries comprises at least two of the unique identifiers corresponding to at least two of the vertices;
generate one or more delta indexes, wherein each of the one or more delta indexes comprises a delta entry identifying one or more modifications to the graph made during a specific time period, and wherein the delta entry corresponds to one of the plurality of entries in the index;
obtain a query to the graph associated with the first attribute type, wherein the query identifies a time period of interest;
identify, based on the time period of interest in the query, a first delta index from the one or more delta indexes, the first delta index having the specific time period corresponding to the time period of interest;
and
generate a response to the query based at least on the index and the first delta index.

6 more elements

Dependencies are inferred from the claim text.