Patent ID: 7797326

Claim:
A method of evaluating elements in a data stream, said method comprising: scanning, by a computer system, said elements as said data stream is being received by said computer system, wherein sortedness of said elements is unknown; as said elements are scanned, randomly selecting, by said computer system, a predetermined number of scanned elements for storage in a data bucket; storing, by said computer system, said predetermined number of said scanned elements in said data bucket; at multiple selected times during said scanning, selecting, by said computer system, a sample of said scanned elements from said data bucket such that multiple samples are obtained and such that said multiple samples comprise uniform samples for specified intervals immediately prior to said selected times; evaluating, by said computer system, each one of said multiple samples, wherein, for each sample, said evaluating comprises: identifying a right-most element in said sample; determining if a majority of other elements in said sample have a greater value than said right-most element; and if so, placing said fight-most element in a set of right-most elements; based on a size of said set of fight-most elements, estimating, by said computer system, a number of said elements in said data stream that must be deleted from said data stream in order to sort said elements in said data stream into a sequence having an increasing value order; and wherein said estimating comprises estimating said number as being between half and twice a size of said set of right-most elements.