Finding K extreme values in constant processing time
A method includes determining a set of k extreme values of a dataset of elements in a constant time irrespective of the size of the dataset. The determining includes reviewing the values bit-by-bit, starting from the most significant bit, where bit n from each element of the dataset is reviewed at the same time.
1 . A method comprising:
determining a set of k extreme values of a dataset of elements in a constant time irrespective of a storable number of items in said dataset; said determining comprising:
storing each element of the dataset in a different column of an associative memory array forming part of an associative processing unit (APU) such that the ith bit of each element of the dataset is stored in a same row of said memory array; and
searching in said memory array for an element in said dataset having an extreme value, wherein said searching is performed in said constant time irrespective of a number of columns of said memory array in which said dataset is stored, said searching comprising:
checking a single row n of said memory array at one time, starting from a row storing most significant bits (MSBs) of said values and ending in a row storing least significant bits (LSBs) of said values;
selecting, in said memory array, for said single row, those of said elements whose bit n have a predetermined bit value, indicating that said elements are candidate elements with extreme values; and
after the selecting has finished, removing any element which is not indicated as a candidate element from further consideration as an extreme value; and
repeating said searching until there are k candidate elements and setting said k candidate elements as said set of k extreme values.
2 . The method of claim 1 wherein said searching comprises adding an indicator to an indicator set for each element having bit n with an extreme value.
3 . The method of claim 2 wherein said extreme value is one of: a maximum and a minimum.
4 . The method according to claim 1 and wherein said searching is implemented in rows of said associative memory array.