Evaluation of paths through graph-based data representation

Patent metadata

Field	Value
Publication number	US-9948601-B2
Application number	US-201314031689-A
Country	US
Kind code	B2
Filing date	Sep 19, 2013
Priority date	Mar 15, 2013
Publication date	Apr 17, 2018
Grant date	Apr 17, 2018

Abstract

Embodiments of the invention generally provide a method, a computing system, and a computer-readable medium configured to respond to requests for payload data and provide unique cache keys for caching the payload data. The computer-implemented method includes accepting a first request for translation that specifies a first path configured to identify first payload data associated with a graph object. The computer-implemented method further includes determining that the graph object includes a first translation node associated with a first portion of the first path. The computer-implemented method also includes obtaining, from the graph object, a second path that is associated with the first translation node. The computer-implemented method further includes replacing the first portion of the first path with the second path to generate a first translated path. The computer-implemented method also includes obtaining, from the graph object, the first payload data, based on the first translated path.

First claim

What I claim is:

1. A computer-implemented method, comprising:
accepting 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 and cached in a graph object, and the first path comprises a non-unique path through the graph object and includes a first sequence of keys that identifies a relationally defined location of the first payload data in the graph object;
traversing the graph object according to the first sequence of keys included in the first path to identify a second path that is associated with a first translation node included in a first portion of the first path;
replacing the first portion of the first path with the second path to generate a first translated path, wherein the first translated path comprises a unique path through the graph object; and
obtaining, from the graph object, the first payload data, based on the first translated path, wherein the first payload data is transmitted to the client device.

2. The computer-implemented method of claim 1 , wherein the second path includes a second sequence of one or more keys, and the first portion of the first path includes at least one key in the first sequence of keys.

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

4. The computer-implemented method of claim 3 , wherein the plurality of nodes includes a set of normal nodes and a set of translation nodes, and wherein the graph object further includes a plurality of directed edges, wherein each directed edge extends from a corresponding normal node, and a plurality of translation references, wherein each translation reference extends from a corresponding translation node.

5. The computer-implemented method of claim 3 , further comprising determining that the first portion of the first path is associated with the first translation node.

6. The computer-implemented method of claim 5 , wherein determining that the first portion of the first path is associated with the first translation node comprises stepping through the graph object as specified by the first sequence of keys, until arriving at the translation node.

7. The computer-implemented method of claim 1 , wherein the first request for translation includes a multi-key reference, and further comprising expanding the first request into a plurality of paths based on the multi-key reference.

8. The computer-implemented method of claim 7 , further comprising, for each path included in the plurality of paths, performing the steps of determining, requesting and replacing.

9. The computer-implemented method of claim 1 , further comprising transmitting a callback object to a client in response to accepting the first request from the client.

10. A computer system, comprising:
a memory storing a path evaluator;
a processing device that is coupled to the memory and, when executing the path evaluator, is configured to:
accept 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 and cached in a graph object, and the first path comprises a non-unique path through the graph object and includes a first sequence of keys that identifies a relationally defined location of the first payload data in the graph object;
traversing the graph object according to the first sequence of keys included in the first path to identify a first translation node included in a first portion of the first path;
obtain, from the graph object, a second path that is associated with the first translation node;
replace the first portion of the first path with the second path to generate a first translated path, wherein the first translated path comprises a unique path through the graph object; and
obtain, from the graph object, the first payload data, based on the first translated path, wherein the first payload data is transmitted to the client device.

11. The computer system of claim 10 , wherein the second path includes a second sequence of one or more keys, and the first portion of the first path includes at least one key in the first sequence of keys.

12. A non-transitory computer-readable medium storing instructions that when executed by a processor, cause a computer system to:
accept 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 and cached in a graph object, and the first path comprises a non-unique path through the graph object and includes a first sequence of keys that identifies a relationally defined location of the first payload data in the graph object;
traversing the graph object according to the first sequence of keys included in the first path to identify a first translation node included in a first portion of the first path;
replace the first portion of the first path with a second path to generate a first translated path, wherein the first translated path comprises a unique path through the graph object; and
obtain, from the graph object, the first payload data, based on the first translated path, wherein the first payload data is transmitted to the client device.

13. The non-transitory computer-readable medium of claim 12 , further comprising determining a second path by:
determining that the graph object includes a first translation node associated with the first portion of the first path;
obtaining the second path from the graph object, wherein the second path is associated with the first translation node.

14. The non-transitory computer-readable medium of claim 13 , wherein the second path includes a second sequence of one or more keys, and the first portion of the first path includes at least one key in the first sequence of keys.

15. The non-transitory computer-readable medium of claim 14 , wherein the graph object includes a plurality of nodes arranged in a hierarchy, wherein each node includes a corresponding key.

16. The non-transitory computer-readable medium of claim 15 , wherein the plurality of nodes includes a set of normal nodes and a set of translation nodes, and wherein the graph object further includes a plurality of directed edges, wherein each directed edge extends from a corresponding normal node, and a plurality of translation references, wherein each translation reference extends from a corresponding translation node.

17. The non-transitory computer-readable medium of claim 15 , wherein determining that the graph object includes the first translation node comprises determining that the first portion of the first path is associated with the first translation node.

18. The non-transitory computer-readable medium of claim 17 , wherein determining that the first portion of the first path is associated with the first translation node comprises stepping through the graph object as specified by the first sequence of keys, until arriving at the translation node.

19. The non-transitory computer-readable medium of claim 13 , wherein the first request for translation includes a multi-key reference, and wherein the stored instructions when executed by a processor further cause a computer system to expand the first request into a plurality of paths based on the multi-key reference.

20. The non-transitory computer-readable medium of claim 13 , where

Assignees

• Netflix Inc

Inventors

• Husain Jafar

Classifications

• G06F17/30831

  Physics · mapped topic

• H04N21/47202

  for requesting content on demand, e.g. video on demand · CPC title

• G06F12/0817

  using directory methods · CPC title

• H04L45/00 Primary

  Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) · CPC title

• G06F17/30858

  Physics · mapped topic