Patent ID: 8606823

Claim:
A method utilizing a computer for selecting an item from an unsorted cache based on a rank-order of the item, the method comprising: picking a first item from the unsorted cache; picking a second item from the unsorted cache, wherein the first item and the second item are picked randomly from the unsorted cache; obtaining a first rank-order of the first item and a first rank order of the second item, wherein the first rank-orders of the first item and the second item are associated with a first cache access criterion; comparing the first rank-order of the first item with the first rank-order of the second item in a first contest; if the first rank-order of the first item exceeds the first rank-order of the second item, designating the first item as a winner of the first contest; if the first rank-order of the first item is less than the first rank-order of the second item, designating the second item as the winner of the first contest; selecting the winner of the first contest as a first selected item; obtaining a second rank-order of the first item and a second rank-order of the second item, wherein the second rank-orders of the first item and the second item are associated with a second cache access criterion; comparing the second rank-order of the first item with the second rank-order of the second item in another first contest, wherein the first contest and the other first contest are independent of each other; if the second rank-order of the first item exceeds the second rank-order of the second item, designating the first item as a winner of the other first contest; if the rank-order of the first item is less than the rank-order of the second item, designating the second item as the winner of the other first contest; selecting the winner of the other first contest as a second selected item; and receiving a new item not in the unsorted cache; picking a third item randomly from the unsorted cache, comparing a first rank-order of the new item and a first rank-order of the third item, if the first rank-order of the new item exceeds the first rank-order of the third item: evicting the third item from the unsorted cache, and inserting the new item into the unsorted cache.