Generating advertisements for search results that reference software applications

1. A method comprising:

receiving, by a search system via a network, a search query from a user device executing an application;

performing, by the search system, a search of a data store using the search query, the data store including function records, each function record including an application access mechanism (AAM) specifying a native application and indicating one or more operations for the native application to perform, and application state information (ASI) describing a state of the native application after the native application has performed the one or more operations;

identifying, by the search system, one or more function records during the search of the data store based on matches between terms of the search query and terms of the ASI included in each identified function record;

selecting, by the search system, one or more AAMs from the identified one or more function records;

determining that a native application specified by at least one of the selected one or more AAMs is unavailable on the user device;

generating an advertisement for the determined native application that is unavailable on the user device; and

transmitting, via the network, the selected one or more AAMs and the generated advertisement to the user device executing the application.

2. The method of claim 1 , wherein the determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device comprises:

receiving device application information indicating one or more native applications that are available on the user device;

comparing each of one or more native applications specified by the selected one or more AAMs to each of the one or more native applications indicated by the device application information; and

determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device based on the comparison.

3. The method of claim 2 , wherein the receiving of the device application information comprises one of:

transmitting an application information query to the user device, and receiving the device application information from the user device in response to the transmitted application information query; and

retrieving the device application information from a device other than the user device.

4. The method of claim 1 , wherein the determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device comprises:

after transmitting the selected one or more AAMs to the user device, receiving an indication that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device from the user device; and

determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device based on the indication.

5. The method of claim 1 , further comprising transmitting link data for each of the selected one or more AAMs, the link data including one or more of image data and text data to be used by the user device to generate a user selectable link for the AAM.

6. The method of claim 1 , further comprising transmitting an application download address (ADA) for the native application that is unavailable on the user device that indicates a web location from which the user device can download the native application.

7. The method of claim 1 , further comprising transmitting placement information indicating relative placement of the generated advertisement and the selected one or more AAMs on a display device.

8. The method of claim 1 , further comprising transmitting advertisement data indicating one or more operations for the native application that is/are unavailable on the user device to perform that cause the native application to reflect one or more conditions of the generated advertisement.

9. The method of claim 1 , wherein the transmitting of the selected one or more AAMs and the generated advertisement to the user device comprises refraining from transmitting the one or more operations indicated by the at least one of the selected one or more AAMs specifying the native application that is unavailable on the user device to the user device.

10. The method of claim 9 , further comprising:

after transmitting the selected one or more AAMs and the generated advertisement to the user device, receiving an indication indicative of the native application being available on the user device; and

transmitting the one or more operations indicated by the at least one of the selected one or more AAMs specifying the native application to the user device.

11. The method of claim 1 , wherein the generated advertisement for the native application that is unavailable on the user device indicates a monetary discount associated with one of the native application and the state of the native application after the native application has performed the one or more operations indicated by one of the at least one of the selected one or more AAMs specifying the native application.

12. A system comprising:

a data store including function records, each function record including an application access mechanism (AAM) that specifies a native application and indicates one or more operations for the native application to perform, and application state information (ASI) that describes a state of the native application after the native application has performed the one or more operations;

and one or more computing devices configured to:

receive, via a network, a search query from a user device executing an application;

perform a search of the data store using the search query;

identify one or more function records during the search of the data store based on matches between terms of the search query and terms of the ASI included in each identified function record;

select one or more AAMs from the identified one or more function records;

determine that a native application specified by at least one of the selected one or more AAMs is unavailable on the user device;

generate an advertisement for the native application that is unavailable on the user device; and

transmit, via the network, the selected one or more AAMs and the generated advertisement to the user device executing the application.

13. The system of claim 12 , wherein the determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device comprises the one or more computing devices being configured to:

receive device application information indicating one or more native applications that are available on the user device;

compare each of one or more native applications specified by the selected one or more AAMs to each of the one or more native applications indicated by the received device application information; and

determine that a native application specified by at least one of the selected one or more AAMs is unavailable on the user device based on the comparison.

14. The system of claim 13 , wherein the receiving of the device application information comprises the one or more computing devices being configured to perform one of:

transmitting an application information query to the user device, and receiving the device application information from the user device in response to the transmitted application information query; or

retrieving the device application information from a device other than the user device.

15. The system of claim 12 , wherein the determining that the native application specified by the at least one of the selected one or more AAMs is unavailable on the user device comprises the one or more computing devices being configured to:

after transmitting the selected one or more AAMs to the user device, receive an indication that a native application specified by at least one of the selected one or more AAMs is unavailable on the user device from the user device; and

determine that a native application specified by at least one of the selected one or more AAMs is unavailable on the user device based on the indication.

16. The system of claim 12 , wherein the one or more computing devices are further configured to transmit one or more of an application download address (ADA) for the native application that is unavailable on the user device that indicates a web location from which the user device can download the native application, and advertisement data that indicates one or more operations for the native application to perform that cause the native application to reflect one or more conditions of the generated advertisement.

17. The system of claim 12 , wherein the transmitting of the selected one or more AAMs and the generated advertisement to the user device comprises the one or more computing devices being configured to refrain from transmitting the one or more operations indicated by the at least one of the selected one or more AAMs specifying the native application that is unavailable on the user device to the user device.

18. The system of claim 17 , wherein the one or more computing devices are further configured to:

after transmitting the selected one or more AAMs and the generated advertisement to the user device, determine that the native application is available on the user device; and

transmit the one or more operations indicated by the at least one of the selected one or more AAMs specifying the native application to the user device.