Systems, apparatuses, and methods for feature searching
Detailed herein are embodiments of systems, methods, and apparatuses to be used for feature searching using an entry-based searching structure.
1. An apparatus comprising:
an entry-based search structure to perform a nearest neighbor search of a dictionary of features with entries dependent on features in the dictionary, wherein the entry-based search structure is a content addressable memory (CAM);
physical storage coupled to the entry-based search structure to store the features; and
physical logic to access the entry-based search structure to search for an entry for particular feature stored in the dictionary of features based upon a received input instance and to access the physical storage and retrieve the particular feature, wherein the dictionary of features is to describe a plurality of bounding boxes defined by interval values and wherein each bounding box is to contain a single feature.
2. The apparatus of claim 1 , wherein the physical storage is a random access memory (RAM).
3. The apparatus of claim 2 , wherein the RAM is embedded into a central processing unit of the apparatus.
4. The apparatus of claim 2 , wherein the RAM is external to a central processing unit of the apparatus.
5. The apparatus of claim 1 , wherein the physical storage is a solid state drive (SSD).
6. The apparatus of claim 1 , wherein each entry of the entry-based search structure is to store an interval value and an address of a feature in physical storage.
7. The apparatus of claim 6 , wherein the interval value comprises a plurality of bits having values of 1, 0, or don't care.
8. The apparatus of claim 1 , wherein each entry of the entry-based search structure is to store an interval value and a value of a feature.
9. The apparatus of claim 8 , wherein the interval value comprises a plurality of bits having values of 1, 0, or don't care.
10. The apparatus of claim 1 , wherein a number of cells of the CAM is less than or equal to 2(l−1)· , where l is a number of bits in each sample of input instances and is a number of features in the dictionary.
11. The apparatus of claim 1 , wherein each cell of the CAM is coupled to summation logic to add up the number of matches to the cell.
12. The apparatus of claim 1 , wherein the summation logic is internal to the CAM.
13. The apparatus of claim 1 , wherein the summation logic is external to the CAM.
14. The apparatus of claim 1 , wherein each cell of the CAM is coupled to AND and OR logic to be used to indicate a match.
15. The apparatus of claim 1 , wherein the feature is stored as a floating point value.
16. The apparatus of claim 1 , wherein the physical logic to access the entry-based search structure to search for an entry for particular feature in the dictionary of features based upon a received input instance and to access the physical storage and retrieve the particular feature is a core.
17. The apparatus of claim 1 , wherein the physical logic to access the entry-based search structure to search for an entry for particular feature in the dictionary of features based upon a received input instance and to access the physical storage and retrieve the particular feature is an accelerator.
18. The apparatus of claim 1 , wherein the entry-based search structure is to search in parallel on multiple sample dimensions of the received input instance.
19. The apparatus of claim 18 , wherein the physical logic to tally matched features across all sample dimensions of the received input instance and identify features with high votes.
20. The apparatus of claim 1 , wherein the physical storage to store a program, that is to be executed by a processor, for searching for a feature.
21. The apparatus of claim 20 , wherein the program is based on orthogonal match pursuit.
22. The apparatus of claim 20 , wherein the program is based on Compressive Sampling Matched Pursuit (CoSaMP).
23. The apparatus of claim 1 , wherein the entry-based search structure is an n-ary search tree for some integer n.
24. The apparatus of claim 1 , wherein the entry-based search structure is a random access memory (RAM) and a bit string in the input instance is to be used as a memory address to retrieve a stored feature.
25. The apparatus of claim 1 , wherein each of the plurality of bounding boxes are regularly shaped.
26. The apparatus of claim 1 , wherein interval of a bounding box on a given dimension is determined by the minimum non-zero separation between a feature and any other feature in each of the dimensions.