Fast color searching

• US 9,996,579 B2
• Filed: 06/26/2014
• Issued: 06/12/2018
• 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, III, Paul Barnhart
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US14/315,700
• Publication Number:
  US 20150379071A1
• Time in Patent Office: 1,447 Days
• Field of Search: None
• 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 color dimension, identify a first bit prefix that comprises a subset of bits of the minimum color value of the respective color dimension and a second bit prefix that comprises a subset of bits of the maximum dimension color value of the respective color dimension;

interleave bits of each color dimension'"'"'s first bit prefix based on a bit order of the bits of each color dimension'"'"'s first bit prefix to form an interleaved first bit prefix;

interleave bits of each color dimension'"'"'s second bit prefix based on a bit order of the bits of each color dimension'"'"'s second bit prefix to form an interleaved second bit prefix;

generate one or more integer search ranges based at least in part on the interleaved first bit prefix and the interleaved second bit prefix, wherein the one or more integer search ranges each comprise a number of bits that is larger than a number of bits in the interleaved first bit prefix;

generate a search query, the search query comprising the one or more integer search ranges as search parameters, wherein generation of the search query to comprise the one or more integer search ranges instead of a second integer search range representing the color search range results in an increased query speed, the increased query speed resulting based at least in part on at least one bit value that falls within the second integer search range not falling within the one or more integer search ranges;

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 first bit prefix comprises bits corresponding to a first bit prefix for a red dimension, a first bit prefix for a green dimension, and a first bit prefix for a blue dimension.

4. The system of claim 3, wherein bits of the interleaved first bit prefix are arranged in a repeating pattern of a red bit from the first bit prefix for the red dimension, a green bit from the first bit prefix for the green dimension, and a blue bit from the first bit prefix for the blue dimension, 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 the first bit prefix of a first color dimension in the n-dimensional color model is 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 of first bit prefixes that comprise a subset of bits of the minimum color values and interleaving bits of second bit prefixes that comprise a subset of bits of the maximum dimension color values, and wherein the one or more integer search ranges each comprise a number of bits that is larger than a number of interleaved first bit prefix bits;

initiating 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, wherein initiating the search based at least in part on the search query that comprises the one or more integer search ranges instead of a second integer search range representing the color search range results in an increased query speed, the increased query speed resulting based at least in part on at least one bit value that falls within the second integer search range not falling within the one or more integer search ranges; 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 interleaving bits of a first bit prefix for a red dimension, a first bit prefix for a green dimension, and a first bit prefix for a blue dimension.

13. The computer-implemented method of claim 12, wherein interleaving bits comprises arranging in a repeating pattern of a red bit from the first bit prefix for the red dimension, a green bit from the first bit prefix for the green dimension, and a blue bit from the first bit prefix for the blue dimension, 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;

identifying a first red bit prefix that comprises a subset of bits of the minimum red value and a second red bit prefix that comprises a subset of bits of the maximum red value;

identifying a first green bit prefix that comprises a subset of bits of the minimum green value and a second green bit prefix that comprises a subset of bits of the maximum green value;

identifying a first blue bit prefix that comprises a subset of bits of the minimum blue value and a second blue bit prefix that comprises a subset of bits of the maximum blue value;

interleaving bits of the first red bit prefix, the first green bit prefix, and the first blue bit prefix from highest dimensional order to lowest dimensional order to form an interleaved first bit prefix;

interleaving bits of the second red bit prefix, the second green bit prefix, and the second blue bit prefix from highest dimensional order to lowest dimensional order to form an interleaved second bit prefix;

generating one or more integer search ranges based at least in part on the interleaved first bit prefix and the interleaved second bit prefix, wherein the one or more integer search ranges each comprise a number of bits that is larger than a number of bits in the interleaved first bit prefix; 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, wherein retrieving the search results using the one or more integer search ranges instead of a second integer search range representing the RGB color search range results in an increased query speed, the increased query speed resulting based at least in part on at least one bit value that falls within the second integer search range not falling within the one or more integer search ranges.

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

wherein the first red bit prefix is identified by determining a first divergent bit in the minimum red value;

wherein the first green bit prefix is identified by determining a second divergent bit in the minimum green value; and

wherein the first blue bit prefix is identified by determining a third divergent bit in the minimum 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.