1. A memory apparatus comprising:
a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors; and
a control circuit configured to control said nonvolatile memory in operation;
wherein said nonvolatile memory includes
a management area in which to record management information,
a user data area in which to record data coming from a user, and a cache area in which to hold temporarily the data to be written to and read from said user data area,
said management area includes
a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, and
addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table, and
said control circuit includes
first writing means for writing, to a deleted new cache block in said cache area, data in excess of a designated logical boundary which defines a logical space size in units of a plurality of sectors within a user data block of said user data area, and
second writing means for having the data written starting from the beginning of said new cache block upon data write by said first writing means to said new cache block, regardless of the logical address space of said new cache block.
2. The memory apparatus according to claim 1, further comprising third writing means as part of said control circuit, wherein, in case of a continuous data write subsequent to the data write performed by said first writing means to said new cache block, said control circuit causes said third writing means to write the additional data immediately in excess of written sectors within said cache block.
3. The memory apparatus according to claim 2, further comprising fourth writing means as part of said control circuit, wherein, following the data write by said first writing means to said new cache block, if it is found impossible to write data immediately in excess of said written sectors within said new cache block, then said control circuit causes said fourth writing means to copy the data from said user data block up to a write starting sector address, before writing the additional data to said cache block.
4. The memory apparatus according to claim 3, further comprising fifth writing means as part of said control circuit, wherein, if said new cache block is found fully written upon data write by said fourth writing means, then said control circuit causes said fifth writing means to write the data from said new cache block back to said user data block without starting garbage collection as a copy operation preparatory to executing the write-back.
5. A memory apparatus comprising:
a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors; and
a control circuit configured to control said nonvolatile memory in operation;
wherein said nonvolatile memory includes
a management area in which to record management information,
a user data area in which to record data coming from a user, and
a cache area in which to hold temporarily the data to be written to and read from said user data area,
said management area includes
a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, and
addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table, and
said control circuit includes
sixth writing means for writing, to a deleted new cache block in said cache area, data short of a designated logical boundary which defines a logical space size in units of a plurality of sectors within a user data block of said user data area, and
seventh writing means for having data written starting from the beginning of said new cache block upon data write by said sixth writing means to said new cache block, regardless of the logical address space of said new cache block.
6. The memory apparatus according to claim 5, further comprising eighth writing means as part of said control circuit, wherein, in case of a data write to the same logical address space within said new cache block following the data write by said sixth writing means to said new cache block, said control circuit causes said eighth writing means to write the additional data immediately in excess of written sectors within said cache block.
7. The memory apparatus according to claim 6, further comprising ninth writing means as part of said control circuit, wherein, following the data write by said eighth writing means to said new cache block, if the written data is found short of said designated logical boundary, then said control circuit causes said ninth writing means to copy the data from said user data block up to the sector address of said designated logical boundary.
8. The memory apparatus according to claim 7, further comprising tenth writing means as part of said control circuit, wherein, if said new cache block is found fully written upon data write by said ninth writing means, then said control circuit causes said tenth writing means to write the data to another cache block.
9. The memory apparatus according to claim 8, further comprising eleventh writing means as part of said control circuit, wherein, in case of a data write in excess of said designated logical border following the data write by said tenth writing means to said new cache block, said control circuit causes said eleventh writing means to write the data to another cache block.
10. A memory apparatus comprising:
a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors; and
a control circuit configured to control said nonvolatile memory in operation;
wherein said nonvolatile memory includes
a management area in which to record management information,
a user data area in which to record data coming from a user, and
a cache area in which to hold temporarily the data to be written to and read from said user data area,
said management area includes
a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, and
addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table, and
said control circuit includes
twelfth writing means for, if all cache blocks in said cache area are found fully written upon data write to user data blocks in said user data area, then writing the data from said cache blocks back to said user data blocks without starting garbage collection as a copy operation preparatory to executing the write-back, and
first preferential processing means for causing said twelfth writing means to execute said write-back to said cache blocks preferentially in ascending order of data update frequency of said cache blocks.
11. A memory apparatus comprising:
a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors; and
a control circuit configured to control said nonvolatile memory in operation;
wherein said nonvolatile memory includes
a management area in which to record management information,
a user data area in which to record data coming from a user, and
a cache area in which to hold temporarily the data to be written to and read from said user data area,
said management area includes
a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, and
addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table, and
said control circuit includes
thirteenth writing means for, if all cache blocks in said cache area are found fully written upon data write to user data blocks in said user data area, then writing the data to another cache block, and
second preferential processing means for, if said another cache block is found fully written upon data write by said thirteenth writing means, then carrying out garbage collection as a copy operation preparatory to executing a write-back operation preferentially on the fully-written cache blocks.
12. A memory control method for controlling a management area, a user data area, and a cache area in a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors, said memory control method comprising:
a storing step of storing a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, along with addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table;
a first writing step of writing, to a deleted new cache block in said cache area, data in excess of a designated logical boundary which defines a logical space size in units of a plurality of sectors within a user data block of said user data area; and
a second writing step of writing the data starting from the beginning of said new cache block upon data write in said first writing step to said new cache block, regardless of the logical address space of said new cache block.
13. The memory control method according to claim 12, further comprising, in case of a continuous data write subsequent to the data write performed in said first writing step to said new cache block, a third writing step of writing the additional data immediately in excess of written sectors within said cache block.
14. The memory control method according to claim 13, further comprising, subsequent to the data write in said first writing step to said new cache block, if it is found impossible to write data immediately in excess of said written sectors within said new cache block, a fourth writing step of performing a write to copy the data from said user data block up to a write starting sector address, before writing the additional data to said cache block.
15. The memory control method according to claim 14, further comprising, if said new cache block is found fully written upon data write in said fourth writing step, a fifth writing step of writing the data from said new cache block back to said user data block without starting garbage collection as a copy operation preparatory to executing the write-back.
16. A memory control method for controlling a management area, a user data area, and a cache area in a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors, said memory control method comprising:
a storing step of storing a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, along with addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table;
a sixth writing step of writing, to a deleted new cache block in said cache area, data short of a designated logical boundary which defines a logical space size in units of a plurality of sectors within a user data block of said user data area; and
a seventh writing step of writing the data starting from the beginning of said new cache block upon data write in said sixth writing step to said new cache block, regardless of the logical address space of said new cache block.
17. The memory control method according to claim 16, further comprising, in case of a data write to the same logical address space within said new cache block following the data write in said sixth writing step to said new cache block, a eighth writing step of writing the additional data immediately in excess of written sectors within said cache block.
18. The memory control method according to claim 17, further comprising, following the data write in said eighth writing step to said new cache block, if the written data is found short of said designated logical boundary, a ninth writing step of performing a write to copy the data from said user data block up to the sector address of said designated logical boundary.
19. The memory control method according to claim 18, further comprising, if said new cache block is found fully written upon data write in said ninth writing step, a tenth writing step of writing the data to another cache block.
20. The memory control method according to claim 19, further comprising, in case of a data write in excess of said designated logical border following the data write in said tenth writing step to said new cache block, a eleventh writing step of writing the data to another cache block.
21. A memory control method for controlling a management area, a user data area, and a cache area in a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors, said memory control method comprising:
a storing step of storing a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, along with addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table;
a twelfth writing step of, if all cache blocks in said cache area are found fully written upon data write to user data blocks in said user data area, then writing the data from said cache blocks back to said user data blocks without starting garbage collection as a copy operation preparatory to executing the write-back; and
a first preferential processing step of causing said twelfth writing step to execute said write-back to said cache blocks preferentially in ascending order of data update frequency of said cache blocks.
22. A memory control method for controlling a management area, a user data area, and a cache area in a nonvolatile memory configured to have data written thereto and read therefrom in units of clusters and to have data deleted therefrom in units of blocks each formed by a plurality of sectors, said memory control method comprising:
a storing step of storing a logical to physical conversion table retaining relations of correspondence between addresses of logical blocks in said user data area on the one hand, and addresses of physical blocks assigned to said logical blocks on the other hand, along with addresses of physical blocks in said cache area, the physical block addresses corresponding to the physical block addresses in said logical to physical conversion table;
a thirteenth writing step of, if all cache blocks in said cache area are found fully written upon data write to user data blocks in said user data area, then writing the data to another cache block; and
a second preferential processing step of, if said another cache block is found fully written upon data write in said thirteenth writing step, then carrying out garbage collection as a copy operation preparatory to executing a write-back operation preferentially on the fully-written cache blocks.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method of predictive directional Web caching, comprising:
detecting a first document accessed by a user;
predicting a subsequent document which, with a highest degree of probability, is likely to be retrieved based on the first document accessed;
caching said predicted subsequent document; and
automatically downloading the subsequent document to the user’s browser before being requested by the user,
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, and
wherein the distance function allows the user to move from one page to another without traversing a link.
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:
utilizing an N-dimensional space indexing technique to construct an indexed database of documents which are to be retrieved by the user.
5. 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.
6. The method of claim 1, further comprising:
retaining a memory of a sequence in which documents are traversed by any given user.
7. The method of claim 1, wherein, when a user retrieves first and second documents in sequence, the first document comprises an \u201corigin\u201d document of a movement and the second document comprises a \u201cdestination\u201d 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.
8. 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.
9. 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.
10. The method of claim 9, 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.
11. The method of claim 10, 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.
12. 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.
13. The method of claim 12, further comprising:
selecting, by the user, a second document from the proximity list, a hypertext link being devoid between the first and second documents.
14. The method of claim 13, 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.
15. 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.
16. 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.
17. The method of claim 16, 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.
18. 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.
19. The method of claim 18, 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.
20. The method of claim 1, wherein said predicting is based on a sequence of a plurality of documents, including said first document, previously accessed.
21. The method of claim 20, 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.
22. The method of claim 1, wherein said predicting predicts said subsequent document which is likely to be retrieved based on the first document accessed, regardless of whether there is a hypertext link from the first document to the subsequent document.
23. The method of claim 1, wherein said predicting is independent from a hypertext link from the first document to the subsequent document.
24. The method of claim 1, wherein said caching comprises automatically caching said predicted subsequent document prior to the user’s request for said predicted subsequent document.
25. A computer-implemented method of predictive directional Web caching, comprising:
detecting a first document accessed by a user; and
predicting a second document for being accessed by said user which, with a highest degree of probability, is likely to be retrieved based on the first document accessed;
caching said predicted subsequent document; and
automatically downloading the subsequent document to the user’s browser before being requested by the user,
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, and
wherein the distance function allows the user to move from one pate to another without traversing a link.
26. A signal-bearing medium tangibly embodying a program of recordable 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;
predicting a subsequent document which with highest degree of probability is likely to be retrieved based on the first document accessed;
caching said predicted subsequent document, and
automatically downloading the subsequent document to the user’s browser before being requested by the user,
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, and
wherein the distance function allows the user to move from one page to another without traversing a link.