Predictive, multi-layer caching architectures

• US 8,850,075 B2
• Filed: 07/06/2011
• Issued: 09/30/2014
• Est. Priority Date: 07/06/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhu, Wenwu, Molinari, Roberto R., Li, Hongzhi, Li, Zheng
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): Shaw, Robert
• Application Number:
  US13/177,058
• Publication Number:
  US 20130014064A1
• Time in Patent Office: 1,182 Days
• Field of Search: 709/249
• US Class Current: 709/249
• 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. At least one computer-readable storage medium storing computer-executable instructions that, when executed by one or more processors of a prediction server, cause the one or more processors to perform acts comprising:

receiving an image request from a proxy server communicatively coupled to the prediction server and to a client computing device, the image request identifying a particular image of a collection of images that represent a map or a three-dimensional (3D) model of a scene, and that a user of the client computing device has navigated to in a map or a three-dimensional (3D) model;

identifying, at the prediction server from the image request, a first set of images of the collection of images for storing on a cache of the client computing device, and a second set of images of the collection of images for storing on a cache of the proxy server, wherein the first set of images comprises images of the collection that are immediately adjacent to the particular image, and the second set of images comprises images of the collection that are immediately adjacent to the images of the first set of images; and

sending the first set of images and the second sets of images from the prediction server to the proxy server, wherein the proxy server caches the second set of images and further sends the first set of images to the client computing device.

2. The at least one computer-readable storage medium as recited in claim 1, wherein the image request is received from the proxy server at least partly in response to a user of the client computing device navigating within the map or the 3D model.

3. The at least one computer-readable storage medium as recited in claim 1, the acts further comprising identifying, from the image request, the client computing device, and wherein the sending comprises:

referencing a table associated with client computing device to identify which images of the first and second sets of images the prediction server has previously sent to the proxy server; and

sending, to the proxy server, the first and second sets of images less any images that have previously been sent to the proxy server.

4. The at least one computer-readable storage medium as recited in claim 1, the acts 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 proxy server.

13. The at least one computer-readable storage medium as recited in claim 1, wherein the acts further comprises retrieving the first set of images and the second set of images from a storage server to the prediction server prior to the sending the first set of images and the second sets of images from the prediction server to the proxy server.

14. The at least one computer-readable storage medium as recited in claim 13, wherein one or more images stored in the proxy server are nearer to the client computing device than one or more images stored in the storage server.

15. The at least one computer-readable storage medium as recited in claim 14, wherein one or more images in the proxy server are nearer to the client computing device that one or more images stored in the storage server.

5. A method, comprising:

receiving an image request from a proxy server communicatively coupled to a prediction server and to a client computing device, the image request identifying a particular image of a collection of images, that represent a map or a three-dimensional (3D) model of a scene, and that a user of the client computing device has navigated to in the map or 3D model;

identifying, at the prediction server from the image request, a first set of images of the collection of images for storing on a cache of the client computing device, and a second set of images of the collection of images for storing on a cache of the proxy server, wherein the first set of images comprises images of the collection that are immediately adjacent to the particular image and the second set of images comprises images of the collection that are immediately adjacent to the images of the first set of images;

retrieving the first set of images and the second set of images from a storage server to the prediction server; and

sending the first set of images and the second set of images from the prediction server to the proxy server, wherein the proxy server caches the second set of images and further sends the first set of images to the client computing device.

6. The method as recited in claim 5 wherein the image request is received from the proxy server at least partly in response to a user of the client computing device navigating within the map or the 3D model.

7. The method as recited in claim 5, further comprising identifying, from the image request, the client computing device, and wherein the sending comprises:

referencing a table associated with client computing device to identify which images of the first and second sets of images the prediction server has previously sent to the proxy serve; and

sending, to the proxy server, the first and second sets of images less any images that have previously been sent to the proxy server.

8. The method as recited in claim 5, 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 proxy server.

9. The method as recited in claim 5, wherein one or more images stored in the proxy server are nearer to the client computing device than one or more images stored in the storage server.

10. A method, comprising:

receiving an image request from a proxy server communicatively coupled to a prediction server and to a client computing device, the image request identifying a particular image of a collection of images, that represent a map or a three-dimensional (3D) model of a scene, and that a user of the client computing device has navigated to in a map or a three-dimensional (3D) model;

identifying, at the prediction server from the image request, a first set of images of the collection of images for storing on a cache of the client computing device, and a second set of images of the collection of images for storing on a cache of the proxy server, the first set of images comprises images of the collection that are immediately adjacent to the particular image, and the second set of images comprises images of the collection that are immediately adjacent to the images of the first set of images; and

sending the first set of images and the second set of images from the prediction server to the proxy server, the proxy server to stores the second set of images and further sends the first set of images to the client computing device.

11. The method as recited in claim 10, wherein the image request is received from the proxy server at least partly in response to the user of the client computing device navigating within the map or the 3D model.

12. The method as recited in claim 10, 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 proxy server.