Applying string matching algorithms to finding ad unit availability interval

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.

BACKGROUND

In a direct content placement campaign that allows for direct placement of content items, such as creatives, a content provider can reserve a content slot of an information resource of a content publisher such that each time the information resource is served, a creative of the content provider is provided for display within the content slot of the information resource.

SUMMARY

According to one aspect, a method for identifying availability of a content unit for a contiguous set of time units is described. A data processing system including one or more processors can receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range. The request identifies 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. The data processing system can generate, from the request, a request string including a first plurality of characters. Each character of the first plurality of characters corresponds to a position in the request string and has a character value. The position corresponds to a respective time unit of the contiguous set of time units and the character value corresponds to the reservation size value associated with the time unit to which the character corresponds. The data processing system can 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 corresponds to a position in the inventory string and has a character value. The position in the inventory string corresponds to a respective time unit of the date range and the character value represents a size of an available portion of the time unit. The data processing system can 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 data processing system can provide, for display, dates corresponding to the substring.

In some implementations, 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.

In some implementations, 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 can correspond to a time unit within the date range.

In some implementations, generating, from an availability schedule of the content unit, an inventory string including a 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.

In some implementations, determining a substring of the inventory string includes identifying a first character of the request string, determining a first character value corresponding to the first character of the request string and determining a first character of the inventory string of the inventory string having a character value that is equal to or greater than the first character value.

In some implementations, the data processing system can identify, for each subsequent character of the request string, a character value corresponding to the subsequent character of the request string. The data processing system can determine, for the subsequent character of the request string, a corresponding character of the inventory string of the inventory string based on a position of the character of the inventory string relative to the first character of the inventory string. The data processing system can 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.

In some implementations, 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.

According to another aspect, a system for identifying availability of a content unit for a contiguous set of time units is described. The system includes a data processing system including a memory storing processor-executable instructions and a processor configured to execute the processor-executable instructions. The processor is configured 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 identifies 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. The processor is configured to generate, from the request, a request string including a first plurality of characters. Each character of the first plurality of characters corresponds to a position in the request string and has a character value. The position corresponds to a respective time unit of the contiguous set of time units and the character value corresponds to the reservation size value associated with the time unit to which the character corresponds. The processor is configured to 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 corresponds to a position in the inventory string and has a character value. The position in the inventory string corresponds to a respective time unit of the date range and the character value represents a size of an available portion of the time unit. The processor is configured to 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 processor is configured to provide, for display, dates corresponding to the substring.

In some implementations, to generate the request string from the request, the processor is configured to assign, to each time unit, a character corresponding to the reservation size value of the time unit.

In some implementations, 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 can correspond to a time unit within the date range.

In some implementations, to generate, from an availability schedule of the content unit, an inventory string including a second plurality of characters, the processor is 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.

In some implementations, to determine a substring of the inventory string, the processor is configured to identify a first character of the request string, determine a first character value corresponding to the first character of the request string and determine a first character of the inventory string of the inventory string having a character value that is equal to or greater than the first character value.

In some implementations, the processor is configured to identify, for each subsequent character of the request string, a character value corresponding to the subsequent character of the request string. The processor is configured to determine, for the subsequent character of the request string, a corresponding character of the inventory string of the inventory string based on a position of the character of the inventory string relative to the first character of the inventory string. The processor is configured to 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.

In some implementations, to provide, for display, dates corresponding to the substring, the processor is 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.

According to another aspect, a computer readable storage medium having computer-executable instructions to identify availability of a content unit for a contiguous set of time units is described. The computer-executable instructions include 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 identifies 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. The computer-executable instructions include instructions to generate, from the request, a request string including a first plurality of characters. Each character of the first plurality of characters corresponds to a position in the request string and has a character value. The position corresponds to a respective time unit of the contiguous set of time units and the character value corresponds to the reservation size value associated with the time unit to which the character corresponds. The computer-executable instructions include instructions to 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 corresponds to a position in the inventory string and has a character value. The position in the inventory string corresponds to a respective time unit of the date range and the character value represents a size of an available portion of the time unit. The computer-executable instructions include instructions to 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 computer-executable instructions include instructions to provide, for display, dates corresponding to the substring.

In some implementations, 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.

In some implementations, 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 can correspond to a time unit within the date range.

In some implementations, generating, from an availability schedule of the content unit, an inventory string including a 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.

In some implementations, determining a substring of the inventory string includes identifying a first character of the request string, determining a first character value corresponding to the first character of the request string and determining a first character of the inventory string of the inventory string having a character value that is equal to or greater than the first character value.

In some implementations, 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.

DETAILED DESCRIPTION

Following below are more detailed descriptions of various concepts related to, and implementations of, methods, apparatuses, and systems for identifying availability of a content unit for a contiguous set of time units. The various concepts introduced above and discussed in greater detail below may be implemented in any of numerous ways, as the described concepts are not limited to any particular manner of implementation. Examples of specific implementations and applications are provided primarily for illustrative purposes.

A content provider, such as an advertiser, can serve ads on some webpages by participating in auctions. The advertiser can serve ads on other webpages by reserving ad units. An ad unit is a unit of inventory available on a publisher's webpage. The ad unit can correspond to a content slot within which an ad may be inserted. In direct campaigns, a content publisher may sell some of the inventory to an advertiser for a premium price on an exclusive or semi-exclusive basis. In an exclusive basis, each time the webpage receives an impression, an ad of the advertiser is displayed such that the advertiser's ads receive a 100% impression rate. In a semi-exclusive basis, an advertiser's ads only receive a percentage of the total number of webpage impressions based on the percentage of impressions the advertiser purchased from the publisher. The availability of an ad unit corresponds to a percentage of impressions for which no advertiser has reserved the ad unit. For instance, if an advertiser buys 70% of an ad unit's inventory, the ad unit's availability is 30%. When an ad unit is not completely sold, the remaining availability of the given ad unit may be sold provided that the requested share of impressions is less or equal to ad unit's availability.

An advertiser interested in reserving an ad unit to show advertisements can select an interval for which the advertiser wants to show advertisements in the ad unit. In some circumstances, it is not easy to find an interval of the requested length, especially if the ad unit has been previously booked by other advertisers. The present disclosure aims to assist an advertiser in finding an ad unit available for purchase that satisfies the availability criteria of an advertiser. The availability criteria may include one or more availability parameters. Examples of availability parameters can include a minimum availability of the ad unit (e.g. 50%), a desired length of the interval (e.g. 7 days), one or more date limitations (e.g. before September 1st but after June 15th), among others.

To produce strict match, a modified substring matching algorithm can be utilized to identify dates that match the availability criteria of the advertiser. For this, each ad unit can have an availability value Aat, which represents the availability of an ad unit a at time period t. Each Aatcan be represented as a letter of some alphabet. For example, if a given ad unit availability is 0, 0, 0, 50, 50, 50, 75, 75, 75, 100, 100, 100 for some interval of dates, this will correspond to a string AAABBBCCCDDD where A is 0% availability, B is 50%, C is 75% and D is 100%. Suppose an advertiser is looking to buy 75% impressions for the period of 5 days, this can be represented as a string CCCCC.

Normal string matching algorithms will not be able to find this since the longest consecutive interval of letter C only consists of 3 days. However, in the present case, there is a valid solution with an interval starting on day 7 (first letter C). To facilitate this, a character equality rule in a string matching algorithm can be redefined as: ci=cjiff A(ci)≧A(cj), where ciis the character of the inventory string (haystack in terms of string matching), cjis a character of a request string corresponding to the request to lookup availability (needle) and function A is a non-negative function which maps character to its availability in percent. That is, an inventory character is considered equal to the request character if and only if the availability associated with the inventory character is more than or equal to the required availability of the request character.

Certain string matching algorithms, such as a naive string matching algorithm or well-known Knuth-Morris-Pratt algorithm can be applied with a re-defined character equality operator. It should be noted that string matching algorithms that rely on string hashing will not work.

Aspects of the present disclosure relate to methods and systems for identifying availability of a content unit for a contiguous set of time units are described. A data processing system including one or more processors can receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range. The request identifies 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. The data processing system can generate, from the request, a request string including a first plurality of characters. Each character of the first plurality of characters corresponds to a position in the request string and has a character value. The position corresponds to a respective time unit of the contiguous set of time units and the character value corresponds to the reservation size value associated with the time unit to which the character corresponds. The data processing system can generate, from an availability schedule of the content unit, a inventory string including a second plurality of characters. Each character of the second plurality of characters corresponds to a position in the inventory string and has a character value. The position in the inventory string corresponds to a respective time unit of the date range and the character value represents a size of an available portion of the time unit. The data processing system can 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 data processing system can provide, for display, dates corresponding to the substring.

FIG. 1is a block diagram depicting one implementation of an environment for identifying availability of a content unit for a contiguous set of time units. The environment100includes at least one data processing system110. The data processing system110can include at least one processor and a memory, i.e., a processing circuit. The memory stores processor-executable instructions that, when executed by processor, cause the processor to perform one or more of the operations described herein. The processor may include a microprocessor, application-specific integrated circuit (ASIC), field-programmable gate array (FPGA), etc., or combinations thereof. The memory may include, but is not limited to, electronic, optical, magnetic, or any other storage or transmission device capable of providing the processor with program instructions. The memory may further include a floppy disk, CD-ROM, DVD, magnetic disk, memory chip, ASIC, FPGA, read-only memory (ROM), random-access memory (RAM), electrically-erasable ROM (EEPROM), erasable-programmable ROM (EPROM), flash memory, optical media, or any other suitable memory from which the processor can read instructions. The instructions may include code from any suitable computer-programming language. The data processing system can include one or more computing devices or servers that can perform various functions. In some implementations, the data processing system can include an advertising auction system configured to host auctions. In some implementations, the data processing system does not include the advertising auction system but is configured to communicate with the advertising auction system via the network105.

The network105can include computer networks such as the internet, local, wide, metro or other area networks, intranets, satellite networks, other computer networks such as voice or data mobile phone communication networks, and combinations thereof. The data processing system110of the system100can communicate via the network105, for instance with at least one content provider computing device115, at least one content publisher computing device120, or at least one end user computing device125. The network105may be any form of computer network that relays information between the user computing device115, data processing system110, and one or more content sources, for example, web servers, advertising servers, amongst others. For example, the network105may include the Internet and/or other types of data networks, such as a local area network (LAN), a wide area network (WAN), a cellular network, satellite network, or other types of data networks. The network105may also include any number of computing devices (e.g., computer, servers, routers, network switches, etc.) that are configured to receive and/or transmit data within network105. The network105may further include any number of hardwired and/or wireless connections. For example, the user computing device115may communicate wirelessly (e.g., via WiFi, cellular, radio, etc.) with a transceiver that is hardwired (e.g., via a fiber optic cable, a CAT5 cable, etc.) to other computing devices in network105.

The data processing system110can include at least one server. For instance, the data processing system110can include a plurality of servers located in at least one data center or server farm. In some implementations, the data processing system110includes a content placement system, e.g., an ad server or ad placement system. The data processing system110can include at least one reservation availability string generation module130, at least one string comparison module132, at least one content reservation module134, at least one content serving module136and at least one database140.

The reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136can each include at least one processing unit, server, virtual server, circuit, engine, agent, appliance, or other logic device such as programmable logic arrays configured to communicate with the database140and with other computing devices (e.g., the content provider computing device115, the content publisher computing device120, or the end user computing device125) via the network105.

The reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136can include or execute at least one computer program or at least one script. The reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136can be separate components, a single component, or part of the data processing system110. The reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136, can include combinations of software and hardware, such as one or more processors configured to execute one or more scripts to receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range, 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, generate, from an availability schedule of the content unit, a 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, determine 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 provide, for display, dates corresponding to the substring.

The data processing system can also include one or more content repositories or databases140. The databases140can be local to the data processing system110. In some implementations, the databases140can be remote to the data processing system110but can communicate with the data processing system110via the network105. The databases140can store reservations for a plurality of content slots available for reservation on a plurality of information resources as well as store availability schedules for the plurality of content slots. Additional details of the contents of the databases140will be provided below.

The content provider computing devices115can include servers or other computing devices operated by a content provider entity to provide content items such as advertisements for display on information resources at the end user computing device125. The content provided by the content provider computing device115can include third party content items or creatives (e.g., ads) for display on information resources such as a website or web page that includes primary content, e.g. content provided by the content publisher computing device120. The content items can also be displayed on a search results web page. For instance, the content provider computing device115can provide or be the source of ads or other content items for display in content slots of content web pages such as a web page of a company where the primary content of the web page is provided by the company, or for display on a search results landing page provided by a search engine. The content items associated with the content provider computing device115can be displayed on information resources other than web pages, such as content displayed as part of the execution of an application on a smartphone or other end user computing device125.

The content publisher computing devices120can include servers or other computing devices operated by a content publishing entity to provide primary content for display via the network105. For instance, the content publisher computing device120can include a web page operator who provides primary content for display on the web page. The primary content can include content other than that provided by the content publisher computing device120, and the web page can include content slots configured for the display of third party content items (e.g., ads) from the content provider computing devices115. For instance, the content publisher computing device120can operate the website of a company and can provide content about that company for display on web pages of the website. The web pages can include content slots configured for the display of third party content items such as ads of the content provider computing device115. In some implementations, the content publisher computing device120includes a search engine computing device (e.g. server) of a search engine operator that operates a search engine website. The primary content of search engine web pages (e.g., a results or landing web page) can include results of a search as well as third party content items displayed in content slots such as content items from the content provider computing device115.

The end user computing devices125can include computing devices configured to communicate via the network105to display data such as the content provided by the content publisher computing device120(e.g., primary web page content or other information resources) and the content provided by the content provider computing device115(e.g., third party content items such as ads configured for display in a content slot of a web page). The end user computing device125, the content provider computing device115, and the content publisher computing device120can include desktop computers, laptop computers, tablet computers, smartphones, personal digital assistants, mobile devices, end user computing devices, consumer computing devices, servers, clients, and other computing devices. The end user computing device125, the content provider computing device115, and the content publisher computing device120can include user interfaces such as microphones, speakers, touchscreens, keyboards, pointing devices, a computer mouse, touchpad, or other input or output interfaces.

The content provider computing devices115, the content publisher computing devices120and the end user computing devices125may be any number of different user electronic devices, for example, a laptop computer, a desktop computer, a tablet computer, a smartphone, a digital video recorder, a set-top box for a television, a video game console, or any other computing device configured to communicate via the network105. The content provider computing devices115, the content publisher computing device120and the end user computing devices125can include a processor and a memory, i.e., a processing circuit. The memory stores machine instructions that, when executed by processor, cause processor to perform one or more of the operations described herein. The processor may include a microprocessor, application-specific integrated circuit (ASIC), field-programmable gate array (FPGA), etc., or combinations thereof. The memory may include, but is not limited to, electronic, optical, magnetic, or any other storage or transmission device capable of providing the processor with program instructions. The memory may further include a floppy disk, CD-ROM, DVD, magnetic disk, memory chip, ASIC, FPGA, read-only memory (ROM), random-access memory (RAM), electrically-erasable ROM (EEPROM), erasable-programmable ROM (EPROM), flash memory, optical media, or any other suitable memory from which the processor can read instructions. The instructions may include code from any suitable computer-programming language.

The content provider computing devices115, the content publisher computing devices120and the end user computing devices125may also include one or more user interface devices. In general, a user interface device refers to any electronic device that conveys data to a user by generating sensory information (e.g., a visualization on a display, one or more sounds, etc.) and/or converts received sensory information from a user into electronic signals (e.g., a keyboard, a mouse, a pointing device, a touch screen display, a microphone, etc.). The one or more user interface devices may be internal to a housing of the content provider computing devices115, the content publisher computing device120and the end user computing devices125(e.g., a built-in display, microphone, etc.) or external to the housing of content provider computing devices115, the content publisher computing device120and the end user computing devices125(e.g., a monitor connected to the user computing device115, a speaker connected to the user computing device115, etc.), according to various implementations. For example, the content provider computing devices115, the content publisher computing device120and the end user computing devices125may include an electronic display, which visually displays web pages using webpage data received from one or more content sources and/or from the data processing system110via the network105. In some implementations, a content placement campaign manager or third-party content provider, such as an advertiser, can communicate with the data processing system110via the content provider computing devices115. In some implementations, the advertiser can communicate with the data processing system110via a user interface displayed on the user interface devices of the content provider computing devices115.

Referring briefly toFIG. 2,FIG. 2shows a conceptual illustration of an example of an information resource including a content unit that can be reserved via the system depicted inFIG. 1. A user interface200includes an information resource202that includes primary content210and at least one content unit220that can contain a third-party content item, such as a creative or an advertisement. A content publisher of the information resource202can select the content unit to participate in a direct advertising campaign in which the content publisher can allow one or more third-party content providers the ability to reserve the content unit220for serving content items provided by the third-party content providers.

In some implementations, one or more third-party content providers can reserve inventory of a content unit, such as the content unit220over a given time period. The inventory of a content unit corresponds to a number of impressions of the information resource of which the content unit is a part. For example, if the information resource receives 10,000 impressions over a given time period, the inventory of the content unit is 10,000. A third-party content provider can reserve the entire inventory of the content unit220for the given time period, or reserve a portion of the inventory of the content unit220for the given time period. In some implementations, the size of the portion of the inventory of the content unit220that the third-party can reserve can vary. In some implementations, the third-party content provider can reserve anywhere from 1%-100% of the entire inventory for a given time period. In some implementations, a first third-party content provider can reserve any portion of the entire inventory for the given time period, while subsequent third-party content providers can only reserve up to a remaining amount of the entire inventory for the given time period. In some implementations, when a third-party content provider reserves, for instance, 50% of the entire inventory for the given time period, the content unit will display a third-party content item of the third-party content provider on every second impression. The content unit can display a third-party content item selected via an auction process during the impressions of the web page when the third-party content item of the third-party content provider is not displayed.

FIG. 3shows a conceptual illustration of a user interface through which a third-party content provider can submit a request to identify a content slot that is available for reservation. In some implementations, the request300can include a time range field302corresponding to a time period within which to identify a content unit to reserve. The request can also include a length of time field304corresponding to a number of time units for which to reserve the content unit. In some implementations, each time unit can have a length of one day. In some implementations, the granularity of the time unit can vary, from one minute, to one hour, to one day, to one week, to one month, among others. The request300can also include a reservation portion size field306corresponding to a size of a portion of the content unit's inventory for a particular time unit. In some implementations, the reservation portion size field306can include values corresponding to one or more time units. For example, the reservation portion size field306includes a value of 40%, 50%, 40%, 50%, 70%, 70% and 90%. In some implementations, based on this field, the request indicates that 40% of the first and third time units are to be reserved, 50% of the second and fourth time units are to be reserved, 70% of the fifth and sixth time units are to be reserved and 90% of the seventh time unit is to be reserved. In some implementations, the reservation portion size field306can include a single value that corresponds to all of the time units to be reserved. The request300can also identify the domain name or URL of the information resource on which to reserve the content slot via the domain name field308. The request300can also include a content slot identifier field310identifying the content slot to reserve.

Referring again toFIG. 1, the reservation availability string generation module130can be designed, configured or constructed to receive a request to identify availability of inventory of a content unit for a contiguous set of time units within a given date range. As described above, the request can include one or more request parameters, including values corresponding to one or more of a time range field, a length of time field, a reservation portion size field, a domain name field and a content slot identifier field, among others. The request can be generated in response to receiving inputs via a user interface.

The reservation availability string generation module130can be configured to generate, from the request, a request string including a first plurality of characters. In some implementations, each character of the first plurality of characters may correspond to a position in the request string and may have a character value. In some implementations, the position of a character may correspond to a respective time unit of the contiguous set of time units. In some implementations, the character value may correspond to the reservation size value associated with the time unit to which the character corresponds.

In some implementations, the reservation availability string generation module130can assign, to each time unit, a character corresponding to the reservation size value of the time unit. For instance, depending on the granularity, the reservation portion size may assign a character value of A to a reservation portion size value of 10%, a character value of B to a reservation portion size value of 20%, a character value of C to a reservation portion size value of 30%, and so forth. In some implementations, the character values can be case sensitive. In some implementations, the character values can be numbers, symbols, among others. In some implementations, the character values can be selected from a-z, A-Z, 0-9, among other symbols and characters. Using the request depicted inFIG. 3, the reservation availability string generation module130can generate a request string “DEDEGGI,” where each character D, E, D, E, G, G and I corresponds to the first, second, third, fourth, fifth, sixth and seventh time unit and the character value of D corresponds to 40%, the character value of E corresponds to 50%, the character value G corresponds to 70% and the character value of I corresponds to 90% of the inventory for a given time unit. The position of each character matches the position of the time unit of the request.

The reservation availability string generation module130can be configured to generate, from an availability schedule of the content unit, a inventory string including a second plurality of characters. Each character of the second plurality of characters may correspond to a position in the inventory string. Each character of the second plurality of characters may also have a character value. The character value corresponds to a portion of the time unit that is available to be reserved. For instance, if a time unit has a value of D, 40% of the inventory of the time unit is available to be reserved, while 60% of the inventory of the time unit is unavailable. Similarly, if a time unit has a value of G, 70% of the inventory of the time unit is available to be reserved, while 30% of the inventory of the time unit is unavailable.

In some implementations, the reservation availability string generation module130can generate a reservation availability string that has a string length that is equal to the number of time units within the time range identified in the request. Each character in the reservation availability string can correspond to a particular time unit. In some implementations, the characters in the reservation availability string are positioned based on the temporal order of the time units to which the characters correspond. For instance, the first character corresponds to the first time unit within the time range, while the last character corresponds to the last time unit within the time range. To generate the reservation availability string, the reservation availability string generation module130can identify, for each time unit, a reservation availability of the time unit. In some implementations, the reservation availability string generation module130can identify the availability of inventory of the time unit by looking up a database that maintains the inventories of time units of a content slot. Upon determining the availability of inventory of a given time unit, the reservation availability string generation module130can assign a character corresponding to a reservation size value of the time unit. The reservation size value of the time unit is the size of the inventory of the time unit available to be reserved. The reservation availability string generation module130can assign a character for each time unit within the time range included in the request. In this way, the reservation availability string generation module130can generate the reservation availability string that has a string length that is equal to the number of time units within the time range identified in the request and each character in the reservation availability string indicates a size of inventory of the time unit available to be reserved.

The string comparison module132can be designed, configured or constructed to 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.

In some implementations, the string comparison module132can identify a first character of the request string. The string comparison module132can determine a character value corresponding to the first character of the request string. The string comparison module132can then determine, from the generated inventory string, the first character of the generated inventory string that has a character value that is equal to or greater than the first character value. In some implementations, the string comparison module132can determine the first character of the generated inventory string that has a character value that is equal to or greater than the first character value using an iterative process. The iterative process entails determining a first character of the inventory string, determining the character value of the determined character of the inventory string and comparing the determined character value with the character value of the first character of the request string, and repeating this for each subsequent character of the inventory string in the inventory string until the character value of the character of the inventory string has a character value that is equal to or greater than the character value of the first character of the request string.

In some implementations, after the string comparison module132identifies the first character of the inventory string that has a character value that is equal to or greater than the character value of the first character of the request string, the string comparison module132identifies the subsequent character of the inventory string adjacent to the first character of the inventory string. The string comparison module132compares the character value of the subsequent character of the inventory string to a character value of the second character value of the request string. If the string comparison module132determines that the character value of the subsequent character of the inventory string is equal to or greater than the character value of the second character value of the request string, the string comparison module132repeats the steps of identifying the subsequent character of the inventory string adjacent to the most recently identified character of the inventory string, comparing the character value of the subsequent character of the inventory string to a character value of the corresponding character value of the request string and determining that the character value of the subsequent character of the inventory string is equal to or greater than the character value of the corresponding character value of the request string. The string comparison module132repeats these steps until all of the characters of the request string have been compared or in the event that one of the character values of a character of the request string is greater than a character value of a character value of a corresponding character of the inventory string.

If all of the characters of a subset of the inventory string have character values that are greater than or equal to character values of corresponding characters of the request string, the string comparison module132can identify the subset of the inventory string as matching the request string. In some implementations, the string comparison module132can then determine, from the position of the characters of the subset in the inventory string, dates to which the characters of the subset correspond. The string comparison module can mark or otherwise indicate the dates as available.

After determining the first character of the inventory string of the subset that has been identified as matching the request string, the string comparison module132can proceed to identify other subsets that may match the request string. In some implementations, the string comparison module132can identify a character subsequent to the first character of the inventory string of the subset identified as matching the request string and repeat the process for identifying a subset of the inventory string that matches the request string. In some implementations, more than one subset of the inventory string can match the request string. In some implementations, the string comparison module132can identify the dates to which each of the matching subsets correspond. In some implementations, the string comparison module132can then provide the identified dates for display.

Existing string matching algorithms, such as the Knuth Moore Pratt string provided below, require that the character values in the request string and the inventory string be equal to one another to be considered a match. As such, such string matching algorithms as they currently exist do not work when trying to evaluate availability as described herein. Below is an implementation of the Knuth Moore Pratt string matching algorithm.

The following algorithm is a modified version of the Knuth Moore Pratt string matching algorithm. The present algorithm introduces an “is_available” function that is used to return a match if the character value of the inventory string is greater than or equal to the request string.

The content reservation module134can be designed, configured or constructed to provide, for display, time units corresponding to the substrings identified by the string comparison module132as matching a request string corresponding to the request to identify availability of inventory of a content unit for a contiguous set of time units within a given date range. The content reservation module134can present the time units on a calendar interface. In some implementations, the calendar interface can include disparate slots for each time unit. The content reservation module134can identify, via a visual indicator, the available sequence of time units corresponding to the substring of the inventory string that matches the request string. In some implementations, slots of the available sequence of time units can be colored or include some other visual identifier. In some implementations, the content reservation module134can identify each of the available sequence of time units that correspond to a subset of the inventory string that matches the request string can be identified with a visual indicator. In some implementations, if multiple subsets of the inventory string match, the slots corresponding to the different available sequences of time units with different colors or visual markers. In some implementations, the content reservation module134can provide, for display, a first time unit, for example, a date, corresponding to the first character of each of the subsets of the inventory string that matches the request string.

In some implementations, the content reservation module134can receive a request to reserve a content item responsive to providing the results of the request to identify availability of inventory of a content unit for a contiguous set of time units within a given date range. In some implementations a content provider, such as an advertiser, may submit a request to reserve the content unit based on the availability of inventory of the content unit. In some implementations, the content reservation module134can receive the request and determine that the content unit has sufficient inventory for each of the time units for which to reserve the content unit. The content reservation module134, upon determining that the content unit has sufficient inventory, can reserve the content unit for the amount of inventory requested. In some implementations, the content reservation module134can update a reservation schedule of the content unit to reflect the reservation. The reservation schedule of the content unit identifies the content providers or associated content items that correspond to reservations of the content unit. For instance, if a content unit is reserved for a particular time unit, for example, Jun. 23, 2014, by a first content publisher that reserved 30% of the inventory of the content unit and a second content publisher that reserved 70% of the inventory of the content unit, the reservation schedule of the content unit can include each of the content publishers and their corresponding amounts of inventory. Moreover, in some implementations, the reservation schedule can also identify one or more content items associated with each of the reservations, such that when a content serving opportunity for the first content provider arises, the content item associated with the reservation of the first content provider is provided for display.

The content serving module136can be designed, constructed or configured to select content to serve in a content unit. In some implementations, the content serving module136can determine a content item to select for serving in a content unit based on the reservation schedule of the content unit. The content serving module136can be configured to identify, from the reservation schedule of a content unit, a content item or a content provider for which a content item is to be displayed.

When a request to serve an information resource on which the content unit is received, a request to serve a content item in the content unit is generated. In some implementations, the content serving module136can receive the request to serve the content item. The request can identify the content item via a unique identifier identifying the content item. In some implementations, the request can include an identifier identifying the content item and a website address of the information resource with which the content unit is associated.

The content serving module136, responsive to receiving the request, can determine one or more content providers for which content items can be served. In some implementations, the content serving module136can include a list of all of the content providers included in the reservation schedule for the given time unit. Upon identifying the list of candidate content providers, the content serving module136can determine their respective amounts of inventory reserved. The content serving module136can then perform a lookup in a log of content serving opportunities, a number of content items served for each of the candidate content providers. Based on the number of content items served and their respective reserved amounts of inventory, the content serving module136an determine which of the candidate content providers' content item to serve. For instance, using the example provided above, if the content serving module136determines that the content serving module136has served 2 impressions of a content item for the first content provider but only served 12 impressions of a content item for the second content provider, the content serving module136can determine to provide 2 more impressions of the content item for the second content provider before providing another impression of a content item for the first content provider (due to the 30% to 70% ratio).

The content serving module136, responsive to determining the content provider whose content to serve, the content serving module136can retrieve or otherwise provide a content item for the determined content provider for display. The content serving module136can then update the log of content serving opportunities to increment the number of content serving opportunities for the determined content provider such that the next time a request to serve content for the content item is received, the content serving module136can again access the log to determine the content provider whose content to serve.

Referring now toFIG. 4,FIG. 4is a flow diagram depicting one implementation of identifying availability of a content unit for a contiguous set of time units. The data processing system can receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range (BLOCK405). The data processing system can 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 (BLOCK410). The data processing system can generate, from an availability schedule of the content unit, a 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. (BLOCK415). The data processing system can then determine 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 (BLOCK420). The data processing system can provide, for display, dates corresponding to the substring (BLOCK425).

In further detail, the data processing system can receive a request to reserve inventory of a content unit for a contiguous set of time units within a given date range (BLOCK405). As described above, the request can include one or more request parameters, including values corresponding to one or more of a time range field, a length of time field, a reservation portion size field, a domain name field and a content slot identifier field, among others. The request can be generated in response to receiving inputs via a user interface.

The data processing system can 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 (BLOCK410). In some implementations, each character of the first plurality of characters may correspond to a position in the request string and may have a character value. In some implementations, the position of a character may correspond to a respective time unit of the contiguous set of time units. In some implementations, the character value may correspond to the reservation size value associated with the time unit to which the character corresponds.

In some implementations, the data processing system can assign, to each time unit, a character corresponding to the reservation size value of the time unit. For instance, depending on the granularity, the reservation portion size may assign a character value of A to a reservation portion size value of 10%, a character value of B to a reservation portion size value of 20%, a character value of C to a reservation portion size value of 30%, and so forth. In some implementations, the character values can be case sensitive. In some implementations, the character values can be numbers, symbols, among others. In some implementations, the character values can be selected from a-z, A-Z, 0-9, among other symbols and characters. Using the request depicted inFIG. 3, the data processing system can generate a request string “DEDEGGI,” where each character D, E, D, E, G, G and I corresponds to the first, second, third, fourth, fifth, sixth and seventh time unit and the character value of D corresponds to 40%, the character value of E corresponds to 50%, the character value G corresponds to 70% and the character value of I corresponds to 90% of the inventory for a given time unit. The position of each character matches the position of the time unit of the request.

The data processing system can generate, from an availability schedule of the content unit, a 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. (BLOCK415). Each character of the second plurality of characters may correspond to a position in the inventory string. Each character of the second plurality of characters may also have a character value. The character value corresponds to a portion of the time unit that is available to be reserved. For instance, if a time unit has a value of D, 40% of the inventory of the time unit is available to be reserved, while 60% of the inventory of the time unit is unavailable. Similarly, if a time unit has a value of G, 70% of the inventory of the time unit is available to be reserved, while 30% of the inventory of the time unit is unavailable.

In some implementations, the data processing system can generate a reservation availability string that has a string length that is equal to the number of time units within the time range identified in the request. Each character in the reservation availability string can correspond to a particular time unit. In some implementations, the characters in the reservation availability string are positioned based on the temporal order of the time units to which the characters correspond. For instance, the first character corresponds to the first time unit within the time range, while the last character corresponds to the last time unit within the time range. To generate the reservation availability string, the data processing system can identify, for each time unit, a reservation availability of the time unit. In some implementations, the data processing system can identify the availability of inventory of the time unit by looking up a database that maintains the inventories of time units of a content slot. Upon determining the availability of inventory of a given time unit, the data processing system can assign a character corresponding to a reservation size value of the time unit. The reservation size value of the time unit is the size of the inventory of the time unit available to be reserved. The data processing system can assign a character for each time unit within the time range included in the request. In this way, the data processing system can generate the reservation availability string that has a string length that is equal to the number of time units within the time range identified in the request and each character in the reservation availability string indicates an size of inventory of the time unit available to be reserved.

The data processing system can then determine 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 (BLOCK420). In some implementations, the data processing system can identify a first character of the request string. The data processing system can determine a character value corresponding to the first character of the request string. The data processing system can then determine, from the generated inventory string, the first character of the inventory string of the generated inventory string that has a character value that is equal to or greater than the first character value. In some implementations, the data processing system can determine the first character of the inventory string of the generated inventory string that has a character value that is equal to or greater than the first character value using an iterative process. The iterative process entails determining a first character of the inventory string of the inventory string, determining the character value of the determined character of the inventory string and comparing the determined character value with the character value of the first character of the request string, and repeating this for each subsequent character of the inventory string in the inventory string until the character value of the character of the inventory string has a character value that is equal to or greater than the character value of the first character of the request string.

In some implementations, after the data processing system identifies the first character of the inventory string that has a character value that is equal to or greater than the character value of the first character of the request string, the data processing system identifies the subsequent character of the inventory string adjacent to the first character of the inventory string. The data processing system can compare the character value of the subsequent character of the inventory string to a character value of the second character value of the request string. If the data processing system can determine that the character value of the subsequent character of the inventory string is equal to or greater than the character value of the second character value of the request string, the data processing system can repeat the steps of identifying the subsequent character of the inventory string adjacent to the most recently identified character of the inventory string, comparing the character value of the subsequent character of the inventory string to a character value of the corresponding character value of the request string and determining that the character value of the subsequent character of the inventory string is equal to or greater than the character value of the corresponding character value of the request string. The data processing system can repeat these steps until all of the characters of the request string have been compared or in the event that one of the character values of a character of the request string is greater than a character value of a character value of a corresponding character of the inventory string.

If all of the characters of a subset of the inventory string have character values that are greater than or equal to character values of corresponding characters of the request string, the data processing system can identify the subset of the inventory string as matching the request string. In some implementations, the data processing system can then determine, from the position of the characters of the subset in the inventory string, dates to which the characters of the subset correspond. The data processing system can mark or otherwise indicate the dates as available.

After determining the first character of the inventory string of the subset that has been identified as matching the request string, the data processing system can proceed to identify other subsets that may match the request string. In some implementations, the data processing system can identify a character subsequent to the first character of the inventory string of the subset identified as matching the request string and repeat the process for identifying a subset of the inventory string that matches the request string. In some implementations, more than one subset of the inventory string can match the request string. In some implementations, the data processing system can identify the dates to which each of the matching subsets correspond. In some implementations, the data processing system can then provide the identified dates for display.

The data processing system can provide, for display, dates corresponding to the substring (BLOCK425). In some implementations, the data processing system can provide, for display, time units corresponding to the substrings identified by the data processing system as matching a request string corresponding to the request to identify availability of inventory of a content unit for a contiguous set of time units within a given date range. The data processing system can present the time units on a calendar interface. In some implementations, the calendar interface can include disparate slots for each time unit. The data processing system can identify, via a visual indicator, the available sequence of time units corresponding to the substring of the inventory string that matches the request string. In some implementations, slots of the available sequence of time units can be colored or include some other visual identifier. In some implementations, the data processing system can identify each of the available sequence of time units that correspond to a subset of the inventory string that matches the request string can be identified with a visual indicator. In some implementations, if multiple subsets of the inventory string match, the slots corresponding to the different available sequences of time units with different colors or visual markers. In some implementations, the data processing system can provide, for display, a first time unit, for example, a date, corresponding to the first character of each of the subsets of the inventory string that matches the request string.

FIG. 5shows the general architecture of an illustrative computer system500that may be employed to implement any of the computer systems discussed herein (including the system50and its components such as reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136) in accordance with some implementations. The computer system500can be used to provide information via the network55for display. The computer system500ofFIG. 5comprises one or more processors520communicatively coupled to memory525, one or more communications interfaces505, and one or more output devices510(e.g., one or more display units) and one or more input devices515. The processors520can be included in the data processing system50or the other components of the system50such as the reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136.

In the computer system500ofFIG. 5, the memory525may comprise any computer-readable storage media, and may store computer instructions such as processor-executable instructions for implementing the various functionalities described herein for respective systems, as well as any data relating thereto, generated thereby, or received via the communications interface(s) or input device(s) (if present). Referring again to the system50ofFIG. 1, the data processing system50can include the memory525to store information related to the availability of inventory of one or more content units, reservations of one or more content units, among others. The memory525can include the database140. The processor(s)520shown inFIG. 5may be used to execute instructions stored in the memory525and, in so doing, also may read from or write to the memory various information processed and or generated pursuant to execution of the instructions.

The processor520of the computer system500shown inFIG. 5also may be communicatively coupled to or control the communications interface(s)505to transmit or receive various information pursuant to execution of instructions. For example, the communications interface(s)505may be coupled to a wired or wireless network, bus, or other communication means and may therefore allow the computer system500to transmit information to or receive information from other devices (e.g., other computer systems). While not shown explicitly in the system ofFIG. 1, one or more communications interfaces facilitate information flow between the components of the system50. In some implementations, the communications interface(s) may be configured (e.g., via various hardware components or software components) to provide a website as an access portal to at least some aspects of the computer system500. Examples of communications interfaces505include user interfaces (e.g., web pages), through which the user can communicate with the data processing system50.

The output devices510of the computer system500shown inFIG. 5may be provided, for example, to allow various information to be viewed or otherwise perceived in connection with execution of the instructions. The input device(s)515may be provided, for example, to allow a user to make manual adjustments, make selections, enter data, or interact in any of a variety of manners with the processor during execution of the instructions. Additional information relating to a general computer system architecture that may be employed for various systems discussed herein is provided further herein.

The features disclosed herein may be implemented on a smart television module (or connected television module, hybrid television module, etc.), which may include a processing module configured to integrate internet connectivity with more traditional television programming sources (e.g., received via cable, satellite, over-the-air, or other signals). The smart television module may be physically incorporated into a television set or may include a separate device such as a set-top box, Blu-ray or other digital media player, game console, hotel television system, and other companion device. A smart television module may be configured to allow viewers to search and find videos, movies, photos and other content on the web, on a local cable TV channel, on a satellite TV channel, or stored on a local hard drive. A set-top box (STB) or set-top unit (STU) may include an information appliance device that may contain a tuner and connect to a television set and an external source of signal, turning the signal into content which is then displayed on the television screen or other display device. A smart television module may be configured to provide a home screen or top level screen including icons for a plurality of different applications, such as a web browser and a plurality of streaming media services, a connected cable or satellite media source, other web “channels”, etc. The smart television module may further be configured to provide an electronic programming guide to the user. A companion application to the smart television module may be operable on a mobile computing device to provide additional information about available programs to a user, to allow the user to control the smart television module, etc. In alternate implementations, the features may be implemented on a laptop computer or other personal computer, a smartphone, other mobile phone, handheld computer, a tablet PC, or other computing device.

Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results.

In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. For example, the reservation availability string generation module130, the string comparison module132, the content reservation module134and the content serving module136can be part of the data processing system110, a single module, a logic device having one or more processing modules, one or more servers, or part of a search engine.

The systems and methods described herein may be embodied in other specific forms without departing from the characteristics thereof. Although the examples provided herein relate to identifying the availability of inventory of content units, the systems and methods described herein can be applied to any program in any vertical in which a comparison is performed. The foregoing implementations are illustrative rather than limiting of the described systems and methods. Scope of the systems and methods described herein is thus indicated by the appended claims, rather than the foregoing description, and changes that come within the meaning and range of equivalency of the claims are embraced therein.