Cached evaluation of paths through graph-based data representation

Patent metadata

Field	Value
Publication number	US-10164941-B2
Application number	US-201314031777-A
Country	US
Kind code	B2
Filing date	Sep 19, 2013
Priority date	Mar 15, 2013
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

Embodiments of the invention generally provide a method, a computing system, and a computer-readable medium configured to request, cache, and generate translations of paths through graph-based data representations. The computer-implemented method includes receiving a first request for translation, wherein the first request specifies a first path configured to identify first payload data. The computer-implemented method further includes determining whether a graph object stored in the local cache memory includes a first translation associated with the first path. If the local cache memory does not include the first translation, then the first translation is obtained from a remote computing device and stored in the graph object. If the local cache memory does include the first translation associated with the first path, then the first translation is obtained from the local cache memory. The computer-implemented method also includes obtaining the first payload data based on the first translation.

First claim

What I claim is:

1. A computer-implemented method comprising:
receiving a first request for translation associated with a client device, wherein the first request specifies a first path configured to identify first payload data downloaded over a network via a hypertext transfer protocol (HTTP) and cached in a graph object, and wherein the graph object is stored in a local cache memory;
determining whether the graph object includes a first translation associated with the first path, wherein the first path comprises a non-unique path defined by a first sequence of keys included in the graph object, and the first translation comprises a unique path defined by a second sequence of keys included in the graph object or is used to determine the unique path through the graph object; and
if the local cache memory does not include the first translation, then obtaining the first translation from a remote computing device and storing the first translation in the graph object, or
if the local cache memory includes the first translation associated with the first path, then obtaining the first translation from the local cache memory, wherein the client device obtains the first payload data based on the first translation.

2. The computer-implemented method of claim 1 , further comprising generating a fully translated path based on the first path and the first translation, wherein the fully translated path corresponds to the unique path through the graph object.

3. The computer-implemented method of claim 2 , wherein:
generating the fully translated path comprises:
determining whether the graph object stored in the local cache memory includes all translations necessary for generating the fully translated path; and
if the graph object includes all translations necessary for generating the fully translated path, then generating the fully translated path based on the graph object, or
if the graph object does not include all translations necessary for generating the fully translated path, then obtaining one or more translations from the remote computing device, and generating the fully translated path based on the first path, the first translation, and the one or more translations obtained from the remote computing device.

4. The computer-implemented method of claim 3 , further comprising storing the one or more translations in the graph object in the local cache memory.

5. The computer-implemented method of claim 4 , wherein:
the first translation includes an indication that a first portion of the first sequence of keys translates to the second sequence of keys, and
each of the one or more translations includes an indication that a corresponding untranslated sequence of keys translates to a corresponding translated sequence of keys.

6. The computer-implemented method of claim 5 , wherein the graph object includes a plurality of nodes arranged in a hierarchy and each node includes a corresponding key.

7. The computer-implemented method of claim 6 , wherein:
determining whether the graph object stored in the local cache memory includes all translations necessary for generating the fully translated path comprises:
setting a current sequence of keys to a first key in the first sequence of keys;
determining whether the current sequence of keys references a node in the graph object stored in the local cache, and
if the current sequence of keys does not reference a node in the graph object, then deciding that the graph object does not include all translations necessary for generating the fully translated path, or
if the current sequence of keys references a node in the graph object, then updating the current sequence of keys to include a next key in the first sequence of keys; and
repeating the steps of determining, deciding, and updating until no next key exists in the first sequence of keys.

8. The computer-implemented method of claim 1 , wherein:
the first request includes a multi-key reference, and
further comprising:
expanding the first request into a plurality of paths based on the multi-key reference; and
for each path included in the plurality of paths, performing the steps of determining and obtaining.

9. The computer-implemented method of claim 8 , further comprising:
for each path included in the plurality of paths:
determining whether a corresponding fully translated path is stored in the graph object, wherein the corresponding fully translated path corresponds to the unique path through the graph object, and
if the corresponding fully translated path is stored in the graph object, then obtaining the fully translated path from the graph object, or
if the corresponding fully translated path is not stored in the graph object, then storing the fully translated path in the graph object.

10. A computer system, comprising:
a processing device, configured to:
receive a first request for translation, wherein the first request specifies a first path configured to identify first payload data downloaded over a network via a hypertext transfer protocol (HTTP) and cached in a graph object, and wherein the graph object is stored in a local cache memory;
determine whether the graph object includes a first translation associated with the first path, wherein the first path comprises a non-unique path defined by a first sequence of keys included in the graph object, and the first translation comprises a unique path defined by a second sequence of keys included in the graph object or is used to determine the unique path through the graph object; and
if the local cache memory does not include the first translation, then obtain the first translation from a remote computing device and store the first translation in the graph object, or
if the local cache memory includes the first translation associated with the first path, then obtain the first translation from the local cache memory, wherein the client device obtains the first payload data based on the first translation.

11. The computer system of claim 10 , wherein the processing device is further configured to generate a fully translated path based on the first path and the first translation, wherein the fully translated path corresponds to the unique path through the graph object.

12. The computer system of claim 11 , wherein:
generating the fully translated path comprises:
determining whether the graph object stored in the local cache memory includes all translations necessary for generating the fully translated path; and
if the graph object includes all translations necessary for generating the fully translated path, then generating the fully translated path based on the graph object, or
if the graph object does not include all translations necessary for generating the fully translated path, then obtaining one or more translations from the remote computing device, and generating the fully translated path based on the first path, the first translation, and the one or more translations obtained from the remote computing device.

13. The computer system of claim 12 , wherein the processing device is further configured to store the one or more translations in the graph object in the local cache memory.

14. The computer system of claim 13 , wherein:
the first translation includes an indication that a first portion of the first sequence of keys translates to the second sequence of keys, and
each of the one or more translations includes an indication that a corresponding untranslated sequence of keys translates to a corresponding translated sequence of keys.

15. The computer system of claim 14 , wherein the graph object includes a plurality of nodes arrang

Assignees

• Netflix Inc

Inventors

• Husain Jafar

Classifications

• G06F12/0811

  with multilevel cache hierarchies · CPC title

• H04L61/2596 Primary

  Translation of addresses of the same type other than IP, e.g. translation from MAC to MAC addresses · CPC title

• G06F12/0817

  using directory methods · CPC title

• G06F17/30858

  Physics · mapped topic

• G06F17/30831

  Physics · mapped topic