Applying string matching algorithms to finding ad unit availability interval

• US 9,536,011 B1
• Filed: 08/18/2014
• Issued: 01/03/2017
• Est. Priority Date: 08/18/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kirillov, Roman
• Primary Examiner(s): Huynh, Cong-Lac
• Application Number:
  US14/461,633
• Time in Patent Office: 869 Days
• Field of Search: 715/200, 715/255
• US Class Current: 1/1
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06F 40/10 Text processing natural language analysis G06F40/20; semantic analysis G06F40/30; processing or translation of natural language G06F40/40
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

Methods and systems for identifying availability of a content unit are described. Processors receive a request to reserve inventory of a content unit for a contiguous set of time units within a date range. The processors generate a request string including a first plurality of characters corresponding to a position in the request string and having a character value. The processors generate an inventory string including a second plurality of characters corresponding to a position in the inventory string and having a character value. The processors determine a substring of the inventory string that includes an equal number of characters as the request string and each character of the substring has a character value that is equal to or greater than a character value of a corresponding character of the request string. The processors display dates corresponding to the substring.

Claims

1. A method for identifying availability of a content unit for a contiguous set of time units, comprising:

receiving, by a data processing system including one or more processors, a request to reserve inventory of a content unit for a contiguous set of time units within a given date range, the request identifying the date range and a reservation size value for each time unit corresponding to a size of a portion of the time unit to reserve;

generating, by the data processing system, from the request, a request string including a first plurality of characters, each character of the first plurality of characters corresponding to a position in the request string and having a character value, the position corresponding to a respective time unit of the contiguous set of time units and the character value corresponding to the reservation size value associated with the time unit to which the character corresponds;

generating, from an availability schedule of the content unit, an inventory string including a second plurality of characters, each character of the second plurality of characters corresponding to a position in the inventory string and having a character value, the position in the inventory string corresponding to a respective time unit of the date range and the character value representing a size of an available portion of the time unit;

determining a substring of the inventory string that includes an equal number of characters as the request string and each character of the substring having a character value that is equal to or greater than a character value of a corresponding character of the request string; and

providing, for display, dates corresponding to the substring.

2. The method of claim 1, wherein generating the request string from the request includes assigning, to each time unit, a character corresponding to the reservation size value of the time unit.

3. The method of claim 1, wherein the length of the inventory string is equal to a number of time units within the date range, each of the characters of the inventory string corresponding to a time unit within the date range.

4. The method of claim 1, wherein generating, from the availability schedule of the content unit, the inventory string including the second plurality of characters includes:

identifying, for each time unit in the date range, a size of an available portion of the time unit that; and

assigning a character corresponding to the size of the available portion of the time unit.

5. The method of claim 1, wherein determining a substring of the inventory string includes:

identifying a first character of the request string;

determining a character value corresponding to the first character of the request string; and

determining a first character of the inventory string having a character value that is equal to or greater than the character value corresponding to the first character of the request string.

6. The method of claim 5, further comprising:

identifying, for each subsequent character of the request string, a character value corresponding to the subsequent character;

determining, for the subsequent character, a corresponding character of the inventory string based on a position of the character of the inventory string relative to the first character of the inventory string;

determining, for the corresponding character of the inventory string, a character value that is equal to or greater than the character value of the character of the request string to which the character of the inventory string corresponds based on a position of the character of the request string relative to the first character of the request string.

7. The method of claim 1, wherein providing, for display, dates corresponding to the substring includes:

identifying a first date corresponding to the first character of the substring; and

providing, for display, the first date that is within the given date range.

8. A system for identifying availability of a content unit for a contiguous set of time units id described, comprising:

a data processing system comprising a memory storing processor-executable instructions; and

a processor configured to execute the processor-executable instructions to receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range, the request identifying the date range and a reservation size value for each time unit corresponding to a size of a portion of the time unit to reserve;

generate, from the request, a request string including a first plurality of characters, each character of the first plurality of characters corresponding to a position in the request string and having a character value, the position corresponding to a respective time unit of the contiguous set of time units and the character value corresponding to the reservation size value associated with the time unit to which the character corresponds;

generate, from an availability schedule of the content unit, an inventory string including a second plurality of characters, each character of the second plurality of characters corresponding to a position in the inventory string and having a character value, the position in the inventory string corresponding to a respective time unit of the date range and the character value representing a size of an available portion of the time unit;

determine a sub string of the inventory string that includes an equal number of characters as the request string and each character of the sub string having a character value that is equal to or greater than a character value of a corresponding character of the request string; and

provide, for display, dates corresponding to the substring.

9. The system of claim 8, wherein to generate the request string from the request, the processor is further configured to assign, to each time unit, a character corresponding to the reservation size value of the time unit.

10. The system of claim 8, wherein the length of the inventory string is equal to a number of time units within the date range, each of the characters of the inventory string corresponding to a time unit within the date range.

11. The system of claim 8, wherein to generate, from an availability schedule of the content unit, the inventory string including a second plurality of characters, the processor is further configured to:

identify, for each time unit in the date range, a size of an available portion of the time unit that; and

assign a character corresponding to the size of the available portion of the time unit.

12. The system of claim 8, wherein to determine a substring of the inventory string, the processor is further configured to:

identify a first character of the request string;

determine a character value corresponding to the first character of the request string; and

determine a first character of the inventory string having a character value that is equal to or greater than the character value corresponding to the first character of the request string.

13. The system of claim 12, wherein the processor is further configured to:

identify, for each subsequent character of the request string, a character value corresponding to the subsequent character;

determine, for the subsequent character, a corresponding character of the inventory string based on a position of the character of the inventory string relative to the first character of the inventory string;

determine, for the corresponding character of the inventory string, a character value that is equal to or greater than the character value of the character of the request string to which the character of the inventory string corresponds based on a position of the character of the request string relative to the first character of the request string.

14. The system of claim 8, wherein to provide, for display, dates corresponding to the substring, the processor is further configured to:

identify a first date corresponding to the first character of the substring; and

provide, for display, the first date that is within the given date range.

15. A non-transitory computer-readable storage medium having instructions to provide information via a computer network, the instructions comprising instructions to:

receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range, the request identifying the date range and a reservation size value for each time unit corresponding to a size of a portion of the time unit to reserve;

generate, from the request, a request string including a first plurality of characters, each character of the first plurality of characters corresponding to a position in the request string and having a character value, the position corresponding to a respective time unit of the contiguous set of time units and the character value corresponding to the reservation size value associated with the time unit to which the character corresponds;

generate, from an availability schedule of the content unit, the inventory string including a second plurality of characters, each character of the second plurality of characters corresponding to a position in the inventory string and having a character value, the position in the inventory string corresponding to a respective time unit of the date range and the character value representing a size of an available portion of the time unit;

determine a sub string of the inventory string that includes an equal number of characters as the request string and each character of the sub string having a character value that is equal to or greater than a character value of a corresponding character of the request string; and

provide, for display, dates corresponding to the substring.

16. The non-transitory computer-readable storage medium of claim 15, wherein generating the request string from the request includes assigning, to each time unit, a character corresponding to the reservation size value of the time unit.

17. The non-transitory computer-readable storage medium of claim 15, wherein the length of the inventory string is equal to a number of time units within the date range, each of the characters of the inventory string corresponding to a time unit within the date range.

18. The non-transitory computer-readable storage medium of claim 15, wherein generating, from the availability schedule of the content unit, the inventory string including the second plurality of characters includes:

identifying, for each time unit in the date range, a size of an available portion of the time unit that; and

assigning a character corresponding to the size of the available portion of the time unit.

19. The non-transitory computer-readable storage medium of claim 15, wherein determining a substring of the inventory string includes:

identify a first character of the request string;

determine a character value corresponding to the first character of the request string; and

determine a first character of the inventory string having a character value that is equal to or greater than the character value corresponding to the first character of the request string.

20. The non-transitory computer-readable storage medium of claim 15, wherein providing, for display, dates corresponding to the substring includes:

identify a first date corresponding to the first character of the substring; and

provide, for display, the first date that is within the given date range.