Predictive, multi-layer caching architectures

• US 9,785,608 B2
• Filed: 09/30/2014
• Issued: 10/10/2017
• Est. Priority Date: 07/06/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zhu, Wenwu, Li, Zheng, Molinari, Roberto R., Li, Hongzhi
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US14/502,656
• Publication Number:
  US 20150081779A1
• Time in Patent Office: 1,106 Days
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/205 Image-based rendering
• CPC Class Codes: G06T 2200/16 involving adaptation to the client's capabilities
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04N 1/00 Scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission; Details thereof
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 5/00 Details of television systems scanning details or combination thereof with generation of supply voltages H04N3/00
• CPC Class Codes: H04W 4/18 Information format or content conversion, e.g. adaptation by the network of the transmitted or received information for the purpose of wireless delivery to users or terminals

Abstract

Predictive, multi-layer caching architectures may be used to predict which elements a user is most likely to navigate to within a collection of elements associated with a predefined layout and, in response, to increase the accessibility of these elements to a client device of the user. For instance, the techniques may utilize a predictive, multi-layer caching architecture for storing these predicted elements to decrease the latency to render these images if the user navigates within the collection of elements in the predicted manner. The collection of elements may comprise images (e.g., a 3D model, a map, etc.), video files, audio files, text files, or any other type of file that is consumable on a client device.

Claims

1. A method implemented by a proxy server residing between a prediction server and a mobile computing device, the method comprising:

receiving, from the mobile computing device, data indicating navigation from a first image of a predefined layout of a collection of images to a second image that is immediately adjacent to the first image in the predefined layout; and

in response to the receiving of the data;

sending, from a cache of the proxy server to the mobile computing device, a first set of images that are immediately adjacent to the second image in the predefined layout;

requesting, from the prediction server a second set of images that are immediately adjacent to the first set of images in the predefined layout;

receiving the second set of images; and

storing, in the cache of the proxy server, the second set of images received from the prediction server;

wherein the collection of images defines a map or a three dimensional (3D) model of a scene being at least partly rendered by the mobile computing device.

2. A method as recited in claim 1, wherein the receiving of the data indicating navigation comprises receiving a request for the first set of images that are immediately adjacent to the second image in the predefined layout.

3. A method as recited in claim 1, wherein the sending of the first set of images that are immediately adjacent to the second image in the predefined layout comprises:

identifying each image stored in the proxy server that is immediately adjacent to the second image in the predefined layout;

determining a subset of the images stored in the proxy server that are immediately adjacent to the second image in the predefined layout and which have been previously sent to the mobile computing device; and

sending each image stored in the proxy server that is immediately adjacent to the second image in the predefined layout less the subset of the images previously sent to the mobile computing device.

4. A method as recited in claim 1, wherein the proxy server refrains from sending the second set of images received from the prediction server to the mobile computing device at least until receipt of other data indicating navigation from the second image of the predefined layout to a third image of the predefined layout.

5. A method as recited in claim 1, further comprising:

receiving, from the mobile computing device, other data indicating navigation from the second image of the predefined layout to a third image that is immediately adjacent to the second image in the predefined layout; and

at least partly in response to the receiving of the other indication;

sending, to the mobile computing device, at least a portion of the second set of images received from the prediction server;

requesting, from the prediction server, a third set of images that are immediately adjacent to images that are immediately adjacent to the third image; and

storing, in the cache of the proxy server, the third set of images received from the prediction server.

6. A method as recited in claim 1, wherein the second set of images received from the prediction server comprises one or more adjacent images of the collection of images, the one or more adjacent images being adjacent to an image that is immediately adjacent to the first image in the predefined layout, less a subset of the one or more adjacent images that have been previously received from the prediction server.

7. A method as recited in claim 1, further comprising, after the sending, updating a table associated with the client computing device to indicate which images of the collection of images have been sent to the mobile computing device.

8. A proxy server comprising one or more computing devices comprising:

one or more processors;

memory; and

one or more program modules, stored in the memory and executable on the one or more processors, to perform acts comprising;

receiving an indication that a client computing device is rendering a particular image of multiple different images collectively associated with a predefined layout; and

in response to receiving the indication;

sending, to the client computing device a first set of images, retrieved from a cache of the proxy server, that are immediately adjacent to the particular image in the predefined layout;

requesting, from a prediction server, a second set of images that are immediately adjacent to the first set of images in the predefined layout;

receiving the second set of images; and

storing, in the memory, the second set of images received from the prediction server;

wherein the multiple different images collectively associated with the predefined layout define a map or a three dimensional (3D) model of a scene being at least partly rendered by the client computing device.

9. The proxy server as recited in claim 8, wherein the sending of the first set of images that are immediately adjacent to the particular image comprises sending each image that is immediately adjacent to the particular image in the predefined layout, less a subset of the first set of images that have been previously sent to the client computing device.

10. One or more computing devices as recited in claim 8, wherein the second set of images received from the prediction server comprises one or more adjacent images of the multiple different images, the one or more adjacent images being adjacent to an image that is immediately adjacent to the particular image in the predefined layout, less a subset of the one or more adjacent images that have been previously received from the prediction server.

11. One or more computing devices as recited in claim 8, wherein the memory comprises one or more caches, and the storing comprises storing the second set of images in the one more caches.

12. One or more computing devices as recited in claim 8, wherein the sending of the first set of images that are immediately adjacent to the particular image in the predefined layout comprises:

identifying each image stored in a cache portion of the memory that is immediately adjacent to the particular image in the predefined layout;

determining a subset of the images stored in the cache of the proxy server that are immediately adjacent to the particular image in the predefined layout and which have been previously sent to the client computing device; and

sending each image stored in the cache of the proxy server that is immediately adjacent to the particular image in the predefined layout less the subset of the images previously sent to the client computing device.

13. One or more computing devices as recited in claim 8, wherein the acts further comprise sending the second set of images received from the prediction server to the client computing device upon receipt of another indication that the client computing device is rendering another image of the predefined layout.

14. One or more computing devices as recited in claim 8, wherein the acts further comprise:

receiving, from the client computing device, other data indicating navigation from the particular image of the predefined layout to another image that is immediately adjacent to the particular image in the predefined layout; and

at least partly in response to the receiving of the other indication;

sending, to the mobile computing device, at least a portion of the second set of images received from the prediction server;

requesting, from the prediction server, a third set of images that are immediately adjacent to images that are immediately adjacent to the other image; and

storing the third set of images received from the prediction server.