Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Patent
1996-10-29
2000-01-04
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
711134, 711136, 711129, 711132, 709203, G06F 1200
Patent
active
060121262
ABSTRACT:
A system and method for caching objects of non-uniform size. A caching logic includes a selection logic and an admission control logic. The admission control logic determines whether an object not currently in the cache is accessed may be cached at all. The admission control logic uses an auxiliary LRU stack which contains the identities and time stamps of the objects which have been recently accessed. Thus, the memory required is relatively small. The auxiliary cache serves as a dynamic popularity list and an object may be admitted to the cache if and only if it appears on the popularity list. The selection logic selects one or more of the objects in the cache which have to be purged when a new object enters the cache. The order of removal of the objects is prioritized based both on the size as well as the frequency of access of the object and may be adjusted by a time to obsolescence factor (TTO). To reduce the time required to compare the space-time product of each object in the cache, the objects may be classified in ranges having geometrically increasing intervals. Specifically, multiple LRU stacks are maintained independently wherein each LRU stack contains only objects in a predetermined range of sizes. In order to choose candidates for replacement, only the least recently used objects in each group need be considered.
REFERENCES:
patent: 4503501 (1985-03-01), Coulson et al.
patent: 5606688 (1997-02-01), McNutt et al.
patent: 5809250 (1998-09-01), Kisor
patent: 5842216 (1998-11-01), Anderson et al.
Marc Adams, Charles Stanbridge, Ghaleb Abdulla, Stephen Williams, and Edward Fox, "Caching Proxies: Limitations and Potentials", Oct. 1995.
Hypertext Transfer Protocol--HTTP/1.1, J. Mogul DEC H. Frystyk T. Berners-Lee MIT/LCS Jan. 1997, http://www.pmg.les.mit.edu, J. Gettys.
Timos K. Sellist, "Intelligent Caching And Indexing Techniques For Relational Database Systems", Inform. Systems, vol. 13, No. 2, pp. 175-185, 1988.
Web Server Technology, The Advanced Guide for World Wide Web Information Providers, N. Yeager, et al., pp. 200-201.
Abrams M. Standridge et al., "Caching Proxies: Limitations and Potentials", Fourth International World Wide Web Conference Proceedings, p. 119, (1995).
Abrams M. Standridge et al., "Caching Proxies: Limitations and Potentials", Fourth International World Wide Web Conference Proceedings, pp. 120-133, (1995).
Aggarwal Charu Chandra
Epelman Marina Aleksandrovna
Wolf Joel Leonard
Yu Philip Shi-Lung
Chan Eddie P.
International Business Machines - Corporation
Jordan Kevin M.
McLean Kimberly N.
LandOfFree
System and method for caching objects of non-uniform size using does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for caching objects of non-uniform size using , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for caching objects of non-uniform size using will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1081021