Techniques for determining ancestry in directed acyclic graphs

A non-transitory computer readable medium having stored thereon instructions for causing a processing circuitry to execute a process, the process comprising:

• accessing a first node of a plurality of nodes in a DAG to obtain first change time data and ancestry data, wherein the plurality of nodes includes at least one point of interest (POI), wherein each POI is one of the plurality of nodes storing data indicating that the node is a POI, wherein the first node stores closest POI (CPOI) data indicating a CPOI for the first node, wherein the CPOI for the first node is one of the at least one POI that requires the fewest visits when traversing upward in the DAG beginning with the first node, wherein the first change time data indicates a time of a first change to ancestry of the CPOI;
• accessing a second node of the plurality of storage nodes to obtain second change time data, wherein the second node is the CPOI for the first node indicated in the CPOI data, wherein the second change time data indicates a time of a second change to ancestry of the CPOI, wherein the second change is a most recent change to ancestry of the CPOI;
• comparing the first change time data with the second change time data;
• and
• determining ancestry of the first node, wherein the ancestry of the first node is determined based on the ancestry data when the first change time data matches the second change time data.

A system for determining ancestry in directed acyclic graphs (DAGs), comprising:

• a processing circuitry;
• and
• a memory, the memory containing instructions that, when executed by the processing circuitry, configure the system to:
• access a first node of a plurality of nodes in a DAG to obtain first change time data and ancestry data, wherein the plurality of nodes includes at least one point of interest (POI), wherein each POI is one of the plurality of nodes storing data indicating that the node is a POI, wherein the first node stores closest POI (CPOI) data indicating a CPOI for the first node, wherein the CPOI for the first node is one of the at least one POI that requires the fewest visits when traversing upward in the DAG beginning with the first node, wherein the first change time data indicates a time of a first change to ancestry of the CPOI;
• access a second node of the plurality of storage nodes to obtain second change time data, wherein the second node is the CPOI for the first node indicated in the CPOI data, wherein the second change time data indicates a time of a second change to ancestry of the CPOI, wherein the second change is a most recent change to ancestry of the CPOI;
• compare the first change time data with the second change time data;
• and
• determine ancestry of the first node, wherein the ancestry of the first node is determined based on the ancestry data when the first change time data matches the second change time data.