Delivering alternate versions of objects from an object cache

• US 6,289,358 B1
• Filed: 04/15/1998
• Issued: 09/11/2001
• Est. Priority Date: 04/15/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Inktomi Corporation (Apollo Global Management, Inc.)
• Inventors: Haines, Matthew, Beguelin, Adam, Gourley, David, Totty, Brian, Mattis, Peter, Plevyak, John
• Primary Examiner(s): Homere, Jean R.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US09/060,887
• Time in Patent Office: 1,245 Days
• Field of Search: 707/203, 707/200, 707/206, 707/202, 707/3, 707/2, 707/100, 707/10
• US Class Current: 707/695
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: Y10S 707/918 Location
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method is provided for caching and delivering an alternate version from among a plurality of alternate versions of information objects. One or more alternate versions of an information object, for example, versions of the information object that are prepared in different languages or compatible with different systems, are stored in an object cache database. In the cache, a vector of alternates is associated with a key value that identifies the information object. The vector of alternates stores information that describes the alternate, the context and constraints of the object'"'"'s use, and a reference to the location of the alternate'"'"'s object content. When a subsequent client request for the information object is received, the cache extracts information from the client request, and attempts to select an acceptable and optimal alternate from the vector by matching the request information to the cached contextual information in the vector of alternates. This selection is performed in a time- and space-efficient manner. Accordingly, the cache can deliver different versions of an information object based on the metadata and criteria specified in a request to the cache. As a result, the information delivered by the cache is customized for the requesting client, without requiring access to the original object server.

Claims

1. A method for providing information objects in response to requests for said information objects, the method comprising the computer-implemented steps of:

maintaining at a first location a cache of information objects that are stored at one or more second locations;

receiving at said first location a first request for an information object stored at one of said second locations; and

responding to said first request by performing the steps of;

traversing an index structure to locate a vector of alternates for said information object, wherein said vector of alternates includes first data about a plurality of alternate versions of said information object that are stored in said cache;

reading said first data from said vector of alternates;

based on said first data, identifying a particular alternate version of said information object to supply in response to said first request; and

supplying said particular alternate version of said information object.

2. The method of claim 1, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, and the method further comprising the step of:

based on said second data, identifying where within said cache said particular alternate version of said information object is stored.

3. The method of claim 1, wherein said first request includes data characterizing said first request for said information object and said first data includes data obtained from a prior request for said information object, and wherein the step of identifying said particular alternate version of said information object to supply in response to said first request comprises the steps of:

comparing said data characterizing said first request for said information object to said data obtained from said prior request for said information object; and

selecting said particular alternate version of said information object based upon results from said comparing step.

4. The method of claim 3, wherein said first data further includes data characterizing said first request for said information object, and wherein the step of comparing said data obtained from said current request for said information object to said data obtained from said prior request for said information object comprises the step of:

comparing said data characterizing said first request for said information object to said data obtained from said prior request for said information object and said data received in response to said prior request for said information object.

5. The method of claim 1, wherein said first request is sent by a first client, and wherein said data received in response to said prior request for said information object is obtained from a second client.

6. The method of claim 1, wherein said first request includes data characterizing said first request for said information object and said first data includes data received in response to said prior request for said information object, and wherein the step of identifying said particular alternate version of said information object to supply in response to said first request comprises the steps of:

comparing said data characterizing said first request for said information object to said data received in response to said prior request for said information object; and

selecting said particular alternate version of said information object based upon results from said comparing step.

7. The method of claim 1, wherein said first request includes data characterizing said first request for said information object and acceptance criteria, and wherein the step of identifying said particular alternate version of said information object to supply in response to said first request comprises the steps of:

comparing said data characterizing said first request for said information object to said first data;

determining whether results from said comparing step satisfy said acceptance criteria; and

when said results satisfy said acceptance criteria, selecting said particular alternate version of said information object.

8. The method of claim 1, wherein the step of traversing said index structure to locate said vector of alternates further comprises the steps of:

traversing said index structure based upon a name of said information object to find a location identifier; and

locating said vector of alternates based upon said location identifier.

9. The method of claim 8, further comprising the steps of:

storing a plurality of vector of alternates for said information object; and

storing, within said index structure, data for determining which vector of alternates to locate in response to each request for said information object.

10. The method of claim 1, wherein the step of identifying said particular alternate version of said information object to supply in response to said first request comprises the steps of:

checking out said vector of alternates;

selecting said particular alternate version based on said first data; and

checking in said vector of alternates.

11. The method of claim 1, wherein said particular alternate version of said information object is not identified in said vector of alternates, and the method further comprises the steps of:

sending a second request to one of said second locations, wherein said second request describes an additional alternate version of said information object that conforms to said first request;

receiving a response from said one of said second locations, wherein said response includes information about said additional alternate version; and

incorporating additional first data into said vector of alternates, wherein said additional first data relates to said additional alternate version.

12. The method of claim 11, wherein said additional first data includes data obtained from said first request and data received from said response.

13. The method of claim 11, further comprising the steps of:

prior to said sending step, checking out said vector of alternates; and

after said incorporating step, checking in said vector of alternates.

14. The method of claim 11, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, wherein said response includes a copy of said additional alternate version of said information object, and the method further comprising the steps of:

storing, in said cache, said copy of said additional alternate version of said information object; and

incorporating additional second data into said vector of alternates to identify where within said cache said copy of said additional alternate version of said information object is stored.

15. The method of claim 11, wherein each of said plurality of alternate versions of said information object contains a unique set of content that is stored in said cache, wherein said additional alternate version contains an additional set of content that is included in said response, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, and the method further comprises the steps of:

identifying a particular unique set of content that is identical to said additional set of content;

incorporating additional data into said vector of alternates to specify that said additional alternate version corresponds to said particular unique set of content that is stored in said cache;

whereby said particular unique set of content is shared by said additional alternate version and one or more other alternate versions.

16. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, a human language, and the step of identifying said particular alternate version is based upon which human language is supported by said particular alternate version.

17. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, a character set, and the step of identifying said particular alternate version is based upon which character set is supported by said particular alternate version.

18. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, an application for displaying said information object, and the step of identifying said particular alternate version is based upon which application for displaying said information object is supported by said particular alternate version.

19. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, a multimedia data type, and the step of identifying said particular alternate version is based upon which multimedia data type is supported by said particular alternate version.

20. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, a document encoding scheme, and the step of identifying said particular alternate version is based upon which document encoding scheme is supported by said particular alternate version.

21. The method of claim 1, wherein said first data indicates, for at least said particular alternate version of said plurality of alternate versions, that said information object includes server-generated variable content that depends on one or more characteristics of a client request, and the step of identifying said particular alternate version is based upon whether said particular alternate version is consistent with said one or more characteristics of said first request.

22. A computer-readable medium carrying:

a vector of alternates for each of a plurality of information objects, wherein each of said vector of alternates is associated with to a particular information object and includes first data for identifying which alternate version, among a plurality of alternate versions of said particular information object, to supply from a cache in response to a request;

an index structure configured to allow locating of a particular vector of alternates that is associated with said particular information object based on an index value that is associated with said particular information object.

23. The computer-readable medium of claim 22, wherein each of said vector of alternates includes second data for locating within said cache each of said plurality of alternate versions of said particular information object.

24. A computer-readable medium carrying one or more sequences of instructions for providing information objects in response to requests for said information objects, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

maintaining at a first location a cache of information objects that are stored at one or more second locations;

receiving at said first location a first request for an information object stored at one of said second locations; and

responding to said first request by performing the steps of;

traversing an index structure to locate a vector of alternates for said information object, wherein said vector of alternates includes first data about a plurality of alternate versions of said information object that are stored in said cache;

reading said first data from said vector of alternates;

based on said first data, identifying a particular alternate version of said information object to supply in response to said first request; and

supplying said particular alternate version of said information object.

25. The computer-readable medium of claim 24, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, and further comprising instructions for performing the step of:

based on said second data, identifying where within said cache said particular alternate version of said information object is stored.

26. The computer-readable medium of claim 24, wherein said first request includes data characterizing said first request for said information object and said first data includes data obtained from a prior request for said information object, and wherein instructions for performing the step of identifying said particular alternate version of said information object to supply in response to said first request comprise instructions for performing the steps of:

comparing said data characterizing said first request for said information object to said data obtained from said prior request for said information object; and

selecting said particular alternate version of said information object based upon results from said comparing step.

27. The computer-readable medium of claim 26, wherein said first data further includes data received in response to said prior request for said information object, and wherein instructions for performing the step of comparing said data characterizing said first request for said information object to said data obtained from said prior request for said information object comprise instructions for performing the step of:

comparing said data characterizing said first request for said information object to said data obtained from said prior request for said information object and said data received in response to said prior request for said information object.

28. The computer-readable medium of claim 26, wherein said first request is sent by a first client, and wherein said data received in response to said prior request for said information object is obtained from a second client.

29. The computer-readable medium of claim 24, wherein said first request includes data characterizing said first request for said information object and said first data includes data received in response to a prior request for said information object, and wherein instructions for performing the step of identifying said particular alternate version of said information object to supply in response to said first request comprise instructions for performing the steps of:

comparing said data characterizing said first request for said information object to said data received in response to said prior request for said information object; and

selecting said particular alternate version of said information object based upon results from said comparing step.

30. The computer-readable medium of claim 24, wherein said first request includes data characterizing said first request for said information object and acceptance criteria, and wherein instructions for performing the step of identifying said particular alternate version of said information object to supply in response to said first request comprise instructions for performing the steps of:

comparing said data characterizing said first request for said information object to said first data;

determining whether results from said comparing step satisfy said acceptance criteria; and

when said results satisfy said acceptance criteria, selecting said particular alternate version of said information object.

31. The computer-readable medium of claim 24, wherein instructions for performing the step of traversing said index structure to locate said vector of alternates further comprise instructions for performing the steps of:

traversing said index structure based upon a name of said information object to find a location identifier; and

locating said vector of alternates based upon said location identifier.

32. The computer-readable medium of claim 31, further comprising instructions for performing the steps of:

storing a plurality of vector of alternates for said information object; and

storing, within said index structure, data for determining which vector of alternates to locate in response to each request for said information object.

33. The computer-readable medium of claim 24, wherein the step of identifying said particular alternate version of said information object to supply in response to said first request comprises instructions for performing the steps of:

checking out said vector of alternates;

selecting said particular alternate version based on said first data; and

checking in said vector of alternates.

34. The computer-readable medium of claim 24, wherein said particular alternate version of said information object is not identified in said vector of alternates, and further comprising instructions for performing the steps of:

sending a second request to one of said second locations, wherein said second request describes an additional alternate version of said information object that conforms to said first request;

receiving a response from said one of said second locations, wherein said response includes information about said additional alternate version; and

incorporating additional first data into said vector of alternates, wherein said additional first data relates to said additional alternate version.

35. The computer-readable medium of claim 34, wherein said additional first data includes data obtained from said first request and data received from said response.

36. The computer-readable medium of claim 34, further comprising instructions for performing the steps of:

prior to said sending step, checking out said vector of alternates; and

after said incorporating step, checking in said vector of alternates.

37. The computer-readable medium of claim 34, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, wherein said response includes a copy of said additional alternate version of said information object, and further comprising instructions for performing the steps of:

storing, in said cache, said copy of said additional alternate version of said information object; and

incorporating additional second data into said vector of alternates to identify where within said cache said copy of said additional alternate version of said information object is stored.

38. The computer-readable medium of claim 34, wherein each of said plurality of alternate versions of said information object contains a unique set of content that is stored in said cache, wherein said additional alternate version contains an additional set of content that is included in said response, wherein said vector of alternates further includes second data to identify where within said cache each alternate version of said plurality of alternate versions of said information object is stored, and further comprising instructions for performing the steps of:

identifying a particular unique set of content that is identical to said additional set of content;

incorporating additional data into said vector of alternates to specify that said additional alternate version corresponds to said particular unique set of content that is stored in said cache;

whereby said particular unique set of content is shared by said additional alternate version and one or more other alternate versions.