ASO Patents

Patent number	US9405832B2
Official title	Application search query classifier
Assignee	Apple Inc.
Inventors	Catherine A. Edwards, Alexander F. Braunstein, Eva H. Mok, Natalia Hernandez-Gardiol
Priority date	May 31, 2012
Filed	August 3, 2012
Granted	August 2, 2016
Status	Lapsed for unpaid maintenance fees. Anticipated expiry was April 17, 2035
Family	US20130325892A1 (published application), PCT/US2013/038416
Source	patents.google.com/patent/US9405832B2

What This Patent Covers and Why It Matters for ASO

Feature it describes: the query understanding layer that sits in front of App Store search ranking.

Most ASO work treats App Store search as one ranking function. You pick keywords, you place them in the title, subtitle and keyword field, and you assume the same placement logic applies to every query. This patent describes a system that breaks that assumption. Before Apple ranks anything, it tries to decide what kind of search the user just performed, and then it switches the retrieval and ranking technique based on that decision.

The patent defines three primary query classes. Navigational means the user wants one specific app by name. Functional means the user wants an app that performs a task. Browse means the user is surveying a category. Each class gets a different technique. Navigational queries lean on text matching against app titles and metadata. Functional queries widen the net with synonyms and semantically similar terms, and they weight popularity signals such as downloads and ratings much more heavily. Browse queries lean on ratings and popularity over text matching almost entirely.

The patent is unusually specific about how much the weighting moves. In one worked example a navigational query applies a weight of 0.8 to the text based search and 0.2 to everything else. For a functional query those weights flip to roughly 0.4 and 0.6. Whether or not those exact numbers ever shipped, the design intent is explicit: on some queries your metadata is most of the answer, and on others it is less than half of it.

If this is how the App Store behaves, several practical consequences follow.

• A keyword is not simply easy or hard. Its difficulty depends on which class Apple assigns it to. Exact match in the title is the strongest lever available on a navigational query and one of the weakest on a browse query.
• Popularity and conversion signals matter more on functional and browse queries than on navigational ones. A small app can outrank a large one on a brand query it owns, and will struggle on “best photo editor” no matter how the metadata is written.
• Short branded queries and long descriptive queries need separate strategies, because they are served by different retrieval logic rather than by one function with different inputs.
• Class membership is decided by user behavior on the query, not by your metadata. You cannot move a query from browse to navigational by rewriting your title. You can only decide which classes you want to compete in.
• Because the classifier is trained on what people install after searching, conversion on a query feeds back into how that query is interpreted for everyone who types it next. This is the strongest argument in the patent for treating conversion rate as a ranking input rather than a reporting metric.

One caveat applies to every patent on this site. A granted patent proves Apple designed and claimed the method. It does not prove the method shipped, or that it still runs in today’s App Store. This one also lapsed for unpaid maintenance fees, which is a weak signal that Apple stopped treating it as worth defending, not proof that the technique was abandoned. Apple filed considerably more specific work on query understanding after 2016, which is the more likely reason this one was left to lapse.

Patent Summary

A user submits a search query to an app store. The system analyzes the terms in that query and assigns it a category, primarily navigational, functional or browse, with location based and price based categories also named. The categorization draws on three kinds of evidence: the linguistic shape of the query, the results of a preliminary search, and empirical data from previous similar searches, including which apps people actually downloaded afterward. Once a category is assigned, the system selects a matching search strategy, and those strategies weight text signals and non text signals differently.

The most durable idea in the filing is the empirical test. Rather than inferring intent from grammar alone, the system looks at the distribution of downloads that followed the same query in the past. If almost all downloads concentrate on one app, the query is treated as navigational. If they spread across many apps, it is treated as functional. Intent is measured by its consequences.

“By assessing terms in the search query, the search query can be categorized (e.g., as a navigational, functional or browse query). The categorization can depend on an analysis of terms in the search query, a preliminary search, and/or empirical data tied to previous and similar searches.”

US9405832B2, abstract

Detailed Explanation

The problem the patent opens with

Figure 1 of the patent sets up the whole argument with two queries side by side: “Angry Birds” and “strategy game”. Both are valid app store searches. Both would be handled identically by a keyword matching engine, which would count term occurrences in app metadata and rank accordingly.

That produces a bad result in both directions. The user who typed “Angry Birds” wants one app and does not care about relevance scoring across a category. The user who typed “strategy game” wants a good strategy game, and the app whose description happens to repeat the phrase most often is not necessarily it. The patent’s position is that these are not two points on one relevance scale. They are two different tasks that happen to arrive through the same text box.

The query classes

Navigational. The user is looking for one known app. The patent’s example is “Angry Birds”. The defining property is not the wording but the outcome: almost everyone who runs this query installs the same app.

Functional. The user wants an app that does something specific. The patent’s example is “constellation identification”. Nobody has a title in mind, and downloads after the query spread across many apps.

Browse. The user is surveying a space rather than solving a task. “Best apps” is the example given. Intent is loose and the user is likely to compare several results before deciding.

Location based and price based. Both are named in the list of available categories but the description never develops how they work. They are worth knowing about mainly as evidence that the scheme was designed to be extended rather than fixed at three, and as a reminder that “free” and geographic modifiers may have been intended for special handling rather than treated as ordinary keywords.

A query can be assigned to one category, to several, or to a fixed number. Some pairs are explicitly exclusive. The patent gives the example that assigning both navigational and functional to the same query can be prohibited, which makes sense: those two classes prescribe opposite weightings, so a query cannot usefully be both.

How a query gets classified

The system combines three independent evidence streams.

1. Linguistic features of the query string. The patent lists concrete cues. Capital letters and quotation marks push toward navigational, on the logic that people capitalize product names. A short query pushes the same way. Version and edition words such as “pro”, “lite”, “premium”, “2” and “seasons” also point toward navigational, because they are how app names are built. Words such as “best”, “top”, “free”, “games”, “music” and “hot” point toward browse. Constructions such as “that can” and “how”, and task noun phrases such as “to do list”, “fm radio” and “restaurant guides”, point toward functional.

2. A preliminary search. Before committing to a class, the system runs a first pass and reads the shape of the result set: how many results came back, how many apps contain the query terms exactly in their titles, and how broadly the matching apps are spread across the catalog. A query that returns one obvious title match behaves differently from one that returns four hundred plausible candidates.

3. Empirical behavior on past identical queries. This is the strongest of the three and the most interesting for ASO. The system keeps a lookup table keyed by search term, described in the patent as search term LUT 318, and consults it at query time.

What the lookup table stores

The fields named in the description are worth reading closely, because they amount to a list of the behavioral signals Apple considered worth keeping per search term.

• Term to category associations, plus category weightings and finer grained variables
• Query frequency, meaning how often the term has been searched
• Number of results the query returns under one or more strategies
• The distribution of apps downloaded by users after seeing results for that query
• Click through rate, stored in three forms: top CTR, cumulative CTR and exact term CTR
• Download or buy rate, also stored as top, cumulative and exact term variants
• Absolute counts of how many times specific apps were opened for more information, bought or downloaded
• Average or maximum user rating for specific apps

The split between top, cumulative and exact term variants is the detail to notice. Apple is not storing one conversion number per query. It is storing conversion for the leading result, conversion across the whole result set, and conversion for results that match the term exactly. Those three numbers together describe whether a query has a clear winner, a crowded field, or a mismatch between what matches literally and what people actually want.

The download distribution test

Figure 7 of the patent lays out the empirical classification procedure step by step. For a given query the system identifies every download that followed it, counts the unique apps involved, sorts them by download count in descending order, checks whether the leading app’s share exceeds a threshold, converts counts to proportions, computes cumulative proportions, and assigns a category on that basis. The test named in the flow is whether the cumulative proportion at the nth app falls below a threshold value.

Figures 8A and 8B give the worked comparison, and it is the clearest passage in the filing. The query “BBC” produces a concentrated distribution, with BBC News taking roughly half of all downloads. The query “News” produces a dispersed one, with Fox News at around 12 percent and BBC News at around 7 percent. Same subject area, completely different shape. The first is navigational, the second is not.

The category decision itself is described as a comparison of normalized scores. The example given is a score vector of roughly [0.05, 0.085, 0.45] across navigational, functional and browse, with the system identifying the highest value among the category associated values. The description does not specify what happens when scores are close, and no tie breaking rule appears, which is a genuine gap rather than something omitted here.

Classification is also not permanent. The empirical database is described as continuously updated, with older data progressively down weighted. A query can therefore migrate between classes as behavior changes. That is exactly what you would expect to observe when a generic term becomes strongly associated with one dominant app, and it is the mechanism by which a category term can quietly turn into a brand term.

How ranking changes once a class is assigned

Query class	Primary retrieval logic	What carries the most weight
Navigational	Text matching against app titles and metadata, crediting each instance of a query term	Exact title match and term frequency in metadata. Example weighting 0.8 text, 0.2 other
Functional	Broadened matching that looks for metadata with similar meaning to the query terms	Function match plus popularity: downloads, ratings, selection frequency. Example weighting 0.4 text, 0.6 other
Browse	Category level retrieval with reduced reliance on text	User ratings and popularity

Read the table as a weighting change, not a switch. Text signals still exist on a browse query and popularity still exists on a navigational one. What changes is which of them decides the outcome. The patent describes differential weighting clearly but says little about how multiple ranked result sets are merged, so the blending mechanics are not something this filing settles.

Figure 6 shows the simplest version of the logic as a branch: assign the category, and if it is navigational run the text based search, otherwise run the alternative. The weighted version in the description is the more sophisticated reading of the same idea.

Where the training data comes from

Figures 9 through 11 describe the collection loop. The device detects a download request and transmits it to the server. The server, which already served the search results, associates the download with the search terms that preceded it, stores the association, and delivers the app. At query time the empirical database is consulted, a distribution is generated and analyzed, and a category is assigned.

The stored records include the query, the downloads that followed and the timing between them, along with device identifiers and characteristics, plus the interactions in between such as opening a product page or purchasing. Records are indexed by query term so the system can answer one specific question at search time: when people typed this exact thing before, what did they end up installing?

For keyword strategy this is the important structural point. The classifier is trained on post search behavior, which means the competitive situation on a query is partly authored by the apps already winning it. A query with one dominant installer stays navigational and keeps rewarding that app’s exact title. A query with dispersed installs stays functional and keeps rewarding popularity and semantic fit. Neither state is a fact about language. Both are facts about accumulated behavior, and both can shift.

What is actually claimed

Claim 1 is narrower than the description, which is normal. It covers receiving a search query at a server, analyzing its terms to assign a first search category chosen from a set that includes a navigational category and a functional category, determining a search technique from that category, where the navigational category is searched on text associated with the applications and the functional category is searched on the function of the applications, then running that technique and returning the result list.

Two details matter. The browse category appears in the abstract and the description but not in claim 1, so the protected core is the navigational and functional split. And the claim requires that the two categories be searched on genuinely different bases, text on one side and function on the other. That distinction, not the act of classifying, is the heart of the patent.

How to read your own keyword set through this lens

You cannot see Apple’s classification. You can approximate it, using the same signal the patent uses, which is concentration of outcome rather than wording.

• Run the query in the App Store and look at whether one app dominates the top of the result set and holds it across storefronts. Concentration is the navigational signature.
• Check whether the leading results actually contain the term in the title. When the winners do not match literally, you are probably looking at a query where text weighting is low.
• In Apple Search Ads, compare tap through rate and conversion rate for exact match on the term against its broad match counterpart. A large gap suggests the store treats the literal term and the concept differently, which is what the exact term variants in the lookup table are for.
• Treat terms where your own conversion rate is strong as the ones worth defending in the title, since in this design conversion is what keeps a term’s classification favorable to you.

Family and related patents

US9405832B2 is the granted patent. US20130325892A1 is its published application, and PCT/US2013/038416 is the international filing from the same family. They describe the same invention at different stages, so where the wording differs, the granted claims are the authoritative version.

Inventor Natalia Hernandez-Gardiol also appears on US9280595B2, “Application query conversion”, which handles the next part of the same problem: once a query has been understood, how the store maps it onto concepts rather than literal words. Read together, the two filings describe a pipeline. This patent decides what kind of question was asked. That one decides what the question means.