Finding K extreme values in constant processing time
AssigneeGSI Technology, Inc.
InventorsEli Ehrman, Avidan Akerib, Moshe Lazer
Life of this patent
Estimating the term…
Abstract
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. A method creates a set of k indicators, each indicator associated with one multi-bit binary number in a large dataset of multi-bit binary numbers. The method includes arranging the multi-bit binary numbers such that each bit n of each said multi-bit binary number is located in a different row n of an associative memory array, starting from a row storing a most significant bit (MSB), adding an indicator to the set for each multi-bit binary number having a bit with an extreme value in the row and continuing the adding until said set contains k indicators.
Claims11
A method to create a set of k indicators, each indicator associated with one multi-bit binary number in a large dataset of multi-bit binary numbers, the method comprising:
- arranging said multi-bit binary numbers such that each bit n of each said multi-bit binary number is located in a different row n of an associative memory array;
- starting from a row storing a most significant bit (MSB), adding an indicator to said set for each multi-bit binary number having a bit with an extreme value in said row;
- and
- continuing said adding until said set contains k of said indicators.
A method for assigning a class to an unclassified object with a k-nearest neighbors (K-NN) algorithm in a large dataset, each object in said dataset associated with a class, the method comprising:
- calculating a distance between said unclassified object and each object in said dataset;
- finding k indicators indicating objects having a distance with a minimum value, said finding occurring in a constant time irrespective of the size of said dataset;
- and
- assigning a class most common in said k-minimum indicators to said unclassified object.
A system for determining a set of k extreme values of a large dataset of multi-bit binary numbers, the system comprising:
- a memory array to store said large dataset;
- an associative memory to compute and store computation results;
- and
- a k-mins processor to find k extreme values in said dataset in a constant computation complexity and create an indication of each of said extreme value.
A method for classifying an unclassified item, the method comprising:
- initially preparing a set of features for each item in a large dataset, said initially preparing comprising:
- starting training an untrained convolution neural network (CNN)using a training set of already classified items;
- stopping said training in an intermediate network state when said CNN starts converging;
- computing activations of said classified items using said intermediate state;
- storing said activations as features of said classified items;
- and
- for an unclassified item, computing activations of said unclassified item using said intermediate state;
- performing a K-NN operation between said activations of said unclassified item and said activations of said classified items.
Dependencies are inferred from the claim text.