Finding K extreme values in constant processing time

Patent metadata

Field	Value
Publication number	US-10929751-B2
Application number	US-201715648475-A
Country	US
Kind code	B2
Filing date	Jul 13, 2017
Priority date	Jul 17, 2016
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

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.

First claim

What is claimed is:

1. 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.

2. The method of claim 1 wherein said extreme value is one of: a maximum and a minimum.

3. The method of claim 1 wherein an index of said multi-bit binary numbers is used as additional least significant bits of each of said multi-bit binary numbers.

4. The method of claim 1 wherein said indicators are bits in a marker vector wherein a size of said vector is identical to a size of said large dataset and an indication is a bit set in a column in said vector whose index is identical to an index of an extreme multi-bit binary number in said large dataset.

5. The method of claim 4 wherein counting an amount of said indicators comprises shifting a first value from a first column directly to a second column not directly adjacent to said first column without shifting said first value to each column in between said first column and said second column.

6. The method of claim 5 wherein said shifting comprises:
using a responder (RSP) signal to copy said value from a first location to a third location in a single step and from said third location to said second location in a single step.

7. The method of claim 1 wherein said adding comprises:
creating a candidate indication per each of said multi-bit binary numbers;
for each multi-bit binary number in a current column having a bit with a first predetermined value, deleting said candidate indication; and
for each multi-bit binary number in a current column having a bit with a second predetermined value, modifying said candidate indication to a qualified indication until an amount of qualified indications is smaller than k; and
adding all of said qualified indications to said set.

8. The method of claim 1 wherein said candidate indication comprises a vector of bits wherein all bits initialized to “1” and said qualified indication comprises a vector of bits, all initialized to “0”; and wherein:
removing said candidate indication comprises performing a logical “AND” operation between said candidate indication and said scanned bit; and
modifying said candidate indication to a qualified indication comprises performing a logical “OR” operation between said qualified indication and said candidate indication.

9. 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.

10. 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.

11. 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.

Assignees

• Gsi Technology Inc

Inventors

• Ehrman Eli
• Akerib Avidan
• Lazer Moshe

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title

• G06N3/08 Primary

  Learning methods · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06F16/2458

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title