Method and system for predictive directional data caching

• US 20030005038A1
• Filed: 06/29/2001
• Published: 01/02/2003
• Est. Priority Date: 06/29/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Novaes, Marcos Nogueira, Codella, Christopher Frank
• Granted Patent: US 7,003,566 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A method (and system) of predictive directional Web caching, includes detecting a first document accessed by a user, and predicting a subsequent document which, with a highest degree of probability, is likely to be retrieved based on the first document accessed.

Claims

1. A method of predictive directional Web caching, comprising:

detecting a first document accessed by a user; and

predicting a subsequent document which, with a highest degree of probability, is likely to be retrieved based on the first document accessed.

2. The method of claim 1, further comprising:

estimating a direction in a navigation pattern of spatial data retrieval by said user.

3. The method of claim 1, wherein a plurality of subsequent documents are predicted for retrieval.

4. The method of claim 1, further comprising:

automatically downloading a most likely to be retrieval document to the user'"'"'s browser before being requested by the user.

5. The method of claim 1, further comprising:

utilizing an N-dimensional space indexing technique to construct an indexed database of documents which are to be retrieved by the user.

6. The method of claim 1, wherein the predicting is based on a distance function derived from a Euclidean distance of documents in a N-dimensional space and from a usage pattern of other users.

7. The method of claim 1, wherein the predicting comprises computing a direction of trajectory based on the user'"'"'s traversals and traversals of other users.

8. The method of claim 1, further comprising:

retaining a memory of a sequence in which documents are traversed by any given user.

9. The method of claim 1, wherein, when a user retrieves first and second documents in sequence, the first document comprises an “

origin”

document of a movement and the second document comprises a “

destination”

document,

wherein one of a trail count record entry is created in a search record index of the origin document labeled with a unique resource identifier of the destination document, and a trail count record is incremented, if a trail count record already exists.

10. The method of claim 1, wherein said first and second documents are retrieved in sequence if the user retrieves the first and second documents within a scope of a single search operation, and

wherein a point of origin of a trail comprises a point of insertion of a search and a metadata index block is created corresponding to the point of insertion, which comprises the point of origin of the traversal, thereby allowing a search result and documents for which an index position are closest to the point of origin, to be sent to the user.

11. The method of claim 10, further comprising:

selecting, by the user, one of the documents from the search result; and

one of creating a trail count record at the point of origin labeled with a unique resource identifier of the document selected, and incrementing an existing trail count record, such that the point of origin becomes a position index of a most-recently retrieved document.

12. The method of claim 11, further comprising:

when the user initiates a retrieval of a document, consulting, by a Web caching portal, the index record;

computing which points are closest to the origin, using Euclidean distances; and

computing which documents are most likely to be traversed next based on a previous usage of other users, by consulting trail records of the index.

13. The method of claim 12, further comprising:

returning, to the user, at least one of a document which the user requested, documents for which a positioning index is closest to the requested document, and documents for which the trail count record of the requested document indicates are most likely to be retrieved next.

14. The method of claim 1, wherein, when a user retrieves a first document, a proximity list is returned to the user, indicating which documents are closest to the first document and the closest documents are returned and cached at a user'"'"'s side.

15. The method of claim 14, further comprising:

selecting, by the user, a second document from the proximity list, a hypertext link being devoid between the first and second documents.

16. The method of claim 15, further comprising:

based on said selecting of said second document, making a trail count record in an index of the first document, recording that a user retrieved the second document in sequence to the first document, and incrementing the trail count record each time other users make a same retrieval sequence.

17. The method of claim 16, further comprising:

monitoring that another user retrieves the first document;

estimating that the user is potentially interested in the second document regardless of whether there is a hypertext link from the first document to the second document; and

sending the second document to the user, for future retrieval.

18. The method of claim 1, further comprising:

providing a predictive Web caching portal at a user side, to allow a Web Browser at said user to determine which documents are likely to be retrieved next by the user, said documents being linked by hypertext links and a hypertext link tag being provided for links which contain a counter of a number of times that the user has traversed that link.

19. The method of claim 18, wherein each time that a user traverses a link, the counter is incremented and a Web document associated with the link is modified, to reflect a value of the hypertext link tag.

20. The method of claim 1, further comprising:

using techniques in a server to determine a content which the user would most likely fetch next given that the user has already fetched one document from a portal,

said techniques comprising a trails map and links listed in a proximity list which the user may click on given that the user is viewing a certain page, such that the trails map and the links are displayed in conjunction with the page the user is viewing.

21. The method of claim 20, wherein the server maintains a count attached to a file of how many times any given user has retrieved a page given that the user has retrieved a first page.

22. The method of claim 1, wherein said predicting is based on a sequence of a plurality of documents, including said first document, previously accessed.

23. The method of claim 22, further comprising:

constructing a vector based on said first document and another document of said plurality of documents; and

projecting said vector in space to determine a next document most likely to be requested by said user.

25. The method of claim 24, wherein said sensing is performed on a server side of a computer system.

26. The method of claim 24, wherein said item comprises a Web page.

27. The method of claim 24, further comprising:

caching said predicted second item.

28. The method of claim 27, wherein said predicted second item is displayed upon a user'"'"'s request.

29. The method of claim 24, further comprising:

estimating a direction of next items to be requested based on projecting a vector in space based on at least two items having been requested previously.

30. The method of claim 24, wherein said likelihood function comprises a traversal trail record of a previous document.

31. The method of claim 24, wherein said likelihood function comprises a trail index comprising a usage tag for client side caching.

24. A method of predicting a next item in a database, to be requested by a user, said method comprising:

sensing a first item requested by a user; and

applying a likelihood function to predict a second item to be requested by the user.

32. A computer-implemented method for obtaining documents from a database, comprising:

sensing a first document accessed by a user; and

based on said first document accessed, predicting and caching a second document for being accessed by said user.

33. A computer-implemented system predictive directional Web caching, comprising:

a detector for detecting a first document accessed by a user; and

a predictor for predicting a subsequent document which, with highest degree of probability, is likely to be retrieved based on the first document accessed.

34. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of predictive directional Web caching, said method comprising:

detecting a first document accessed by a user; and

predicting a subsequent document which with highest degree of probability is likely to be retrieved based on the first document accessed.

35. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of predicting a next item in a database, to be requested by a user, said method comprising:

sensing a first item requested by a user; and

applying a likelihood function to predict a second item to be requested by the user.