FAST COLOR SEARCHING

• US 20150379071A1
• Filed: 06/26/2014
• Published: 12/31/2015
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dorner, Charles Shearer, Sayre, Paul Barnhart III
• Granted Patent: US 9,996,579 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence

Abstract

Systems and methods are described to quickly search a data store based on one or more n-dimensional colors. The n-dimensional colors in the data store may be converted to interleaved integers and indexed. An n-dimensional color search range may be converted to one or more integer search ranges. A fast color search query may be formulated based on the one or more integer search ranges, and transmitted to the data store for searching. The data store may use the interleaved integer index to quickly compare the integer search ranges to the interleaved integers, and send back one or more colors or object results that matched the desired color range.

Claims

1. A system comprising:

a memory configured to store computer-executable instructions; and

a computing device comprising one or more hardware processors, the computing device in communication with the memory and configured to execute the computer-executable instructions to at least;

obtain a color search range for colors, the colors specified by an n-dimensional color model, the color search range comprising, for each color dimension in the n-dimensional color model, a minimum dimension color value and a maximum dimension color value;

for each dimension of the color search range, calculate one or more binary split ranges based at least in part on the minimum and maximum dimension color values of a corresponding color dimension of the color search range;

generate one or more integer search ranges based at least in part on permutations of each dimension'"'"'s one or more binary split ranges, wherein the one or more integer search ranges comprise interleaved bits from permutations of the one or more binary split ranges;

generate a search query, the search query comprising the one or more integer search ranges as search parameters;

initiate a search, based at least in part on the search query, of a data store for colors within the one or more integer search ranges, the data store comprising records associated with at least one indexed integer color value; and

receive search results from the data store, the search results comprising records associated with at least one indexed integer color value within the one or more integer search ranges.

2. The system of claim 1, wherein the n-dimensional color model is an RGB color model.

3. The system of claim 2, wherein the interleaved bits comprise permutations of a red binary split range, a green binary split range, and a blue binary split range.

4. The system of claim 3, wherein the interleaved bits are arranged in a repeating pattern of a red bit from the red binary split range, a green bit from the green binary split range, and a blue bit from the blue binary split range, wherein the red bit, the green bit, and the blue bit are from the same order of bits, the repeating pattern arranged from highest order to lowest order bits.

5. The system of claim 1, wherein at least a portion of the calculated one or more binary split ranges are identified by determining a divergent bit.

6. The system of claim 1, wherein the records comprise an object record associated with one or more indexed integer color values within the one or more integer search ranges.

7. The system of claim 6, wherein the object record is an item record.

8. The system of claim 7, wherein the computing device is a user computer.

9. The system of claim 1, wherein at least one of the minimum dimension color value or the maximum dimension color value is determined based at least in part on a human color difference perception formula.

10. A computer-implemented method comprising:

under control of a hardware computing device configured with specific computer-executable instructions,

obtaining a color search range for colors, the colors specified by an n-dimensional color model, the color search range comprising, for each color dimension in the n-dimensional color model, a minimum dimension color value and a maximum dimension color value;

calculating one or more integer search ranges, wherein the one or more integer search ranges are determined by interleaving bits from the minimum and maximum dimension color values for each color dimension within the color search range;

initiate a search of a data store based at least in part on a search query comprising the one or more integer search ranges as search parameters, the data store comprising records associated with at least one indexed integer color value; and

receiving search results from the data store, the search results comprising one or more records associated with at least one indexed integer color value within the one or more integer search ranges.

11. The computer-implemented method of claim 10, wherein the n-dimensional color model is an RGB color model.

12. The computer-implemented method of claim 11, wherein interleaving bits comprises permuting a red binary split range, a green binary split range, and a blue binary split range.

13. The computer-implemented method of claim 12, wherein interleaving bits comprises arranging in a repeating pattern of a red bit from the red binary split range, a green bit from the green binary split range, and a blue bit from the blue binary split range, wherein the red bit, the green bit, and the blue bit are from the same order of bits, the repeating pattern arranged from highest order to lowest order bits.

14. The computer-implemented method of claim 10, wherein a record comprises an item record associated with one or more indexed integer color values within the one or more integer search ranges.

15. The computer-implemented method of claim 10, wherein at least one of the minimum dimension color value or the maximum dimension color value is determined based at least in part on a human color difference perception formula.

16. A non-transitory computer readable storage medium storing computer-executable instructions that when executed by a processor perform operations comprising:

obtaining an RGB color search range, the RGB color search range comprising a minimum red value, a maximum red value, a minimum green value, a maximum green value, a minimum blue value, and a maximum blue value;

calculating one or more red binary split ranges based at least in part on the minimum red value and the maximum red value;

calculating one or more green binary split ranges based at least in part on the minimum green value and the maximum green value;

calculating one or more blue binary split ranges based at least in part on the minimum green value and the maximum green value;

generating one or more integer search ranges based at least in part on permutations of the red binary split ranges, the green binary split ranges, and the blue binary split ranges, wherein each permutation comprises interleaved bits from a red binary split range of the one or more red binary split ranges, a green binary split range of the one or more green binary split ranges, and a blue binary split range of the one or more blue binary split ranges,

wherein the interleaved bits are arranged from highest dimensional order to lowest dimensional order; and

retrieving search results from a data store using the one or more integer search ranges, the search results comprising records associated with at least one indexed integer color value within the one or more integer search ranges.

17. The non-transitory computer readable storage medium of claim 16,

wherein at least a portion of the one or more red binary split ranges are identified by determining a first divergent bit in the minimum red value and the maximum red value;

wherein at least a portion of the one or more green binary split ranges are identified by determining a second divergent bit in the minimum green value and the maximum green value; and

wherein at least a portion of the one or more blue binary split ranges are identified by determining a third divergent bit in the minimum blue value and the maximum blue value.

18. The non-transitory computer readable storage medium of claim 16, wherein the search results comprise an object record associated with one or more indexed integer color values within the one or more integer search ranges.

19. The non-transitory computer readable storage medium of claim 17, wherein the object record is an item record.

20. The non-transitory computer readable storage medium of claim 18, wherein the computer readable storage medium is accessible to a user computing device.

21. The non-transitory computer readable storage medium of claim 16, wherein at least one of the minimum red value, the maximum red value, the minimum green value, the maximum green value, the minimum blue value, or the maximum blue value are determined based at least in part on a human color difference perception formula.

22. A system comprising:

a data store configured to store one or more object records, each object record associated with one or more RGB colors; and

a computing device comprising one or more hardware processors and a memory storing computer-executable instructions, the one or more hardware processors configured to execute the computer-executable instructions to at least;

for each RGB color associated with an object record in the data store;

generate an integer color value corresponding to a one dimensional color space, the integer color value comprising interleaved bits from red, green, and blue dimension values of the RGB color, the interleaved bits sorted from highest order of magnitude to lowest order of magnitude; and

store the integer color value in the data store as associated with the RGB color; and

index integer color values in the data store.

23. The system of claim 22, wherein each object record comprises an item record.