ASO Patents

Patent number	US8364694B2
Official title	Search assistant for digital media assets
Assignee	Apple Inc.
Inventor	Christopher Volkert
Filed	October 26, 2007
Granted	January 29, 2013
Status	Active. Anticipated expiry August 5, 2028
Continuations	US8639716B2 (filed 2013), US8943089B2 (filed 2013), US9305101B2 (filed 2015, granted 2016)
Source	patents.google.com/patent/US8364694B2

What This Patent Covers and Why It Matters for ASO

Feature it describes: the suggestion dropdown that appears while a user types in the store’s search field.

Search suggestions decide a large share of what people search for at all. A user who types three letters and takes a suggestion never enters the query they were originally going to type. That makes the ordering of that list one of the highest leverage surfaces in the store, and this patent states the ordering rule directly in its independent claim: the candidate words are ordered by sales popularity data, derived from purchase data for the assets associated with each word.

Not search volume. Not alphabetical order. Not relevance to the characters typed beyond the prefix match that got the word onto the list in the first place. Purchases.

There is an important scope note. This is a 2007 filing about an online media store and its digital media assets, which at the time meant primarily music, video and podcasts, with apps arriving the following year. It is not an App Store specific patent. What it does establish is the architecture Apple built for store search assistance, and the App Store inherited that architecture rather than getting its own.

The practical reading for ASO:

• Suggestions are built from words associated with assets in the store, and a word only becomes a candidate if it prefix matches what the user has typed. Prefix, not substring. A term buried mid phrase in your title is not what puts you in the dropdown.
• Because ordering is driven by purchase volume of the associated assets, the suggestion list is a leaderboard with a text filter in front of it. Winning a suggestion slot is downstream of conversion volume, not of metadata cleverness.
• The list is filtered by what the client device supports and by what is available in the user’s territory, before ordering. Suggestion sets therefore differ by device and by storefront by design, which is worth remembering before treating a suggestion difference between two markets as an algorithm change.
• Suggestion slots are scarce. The patent’s examples show up to ten on a desktop interface and as few as four on a touch interface. On phones, the competition is for four positions.
• This creates a compounding loop. Purchases put a word higher in the suggestion list, a higher suggestion produces more searches for that word, and more searches produce more purchases. Any term where you already convert well is worth defending aggressively, because the suggestion layer amplifies existing position rather than redistributing it.

Patent Summary

A user begins typing in the search field of an online media store. Each character is sent to the server, which determines the set of words matching those characters by prefix, where every word is associated with one or more assets available in the store. The set is then filtered twice: words whose associated assets are all of a media type the client device cannot play or run are removed, and words whose assets are unavailable in the user’s territory are removed as well. The surviving words are ordered by sales popularity, calculated from purchase data, and returned as a list of possible complete search strings for the user to pick from.

Behind this sit three data structures: a content database holding asset metadata and media, a finance database holding transaction records, and a hints structure organized as a trie, or prefix tree, that stores precomputed suggestions so the lookup is fast enough to run on every keystroke. A popularity module reads the finance database and periodically refreshes the popularity figures the ordering depends on.

“As media assets are purchased from the media repository, popularity indications for such digital media assets can be adjusted. When the user enters a search character, a list of possible complete search strings corresponding to digital media assets available in the media repository can be obtained over a network and presented to the user.”

US8364694B2, abstract

Detailed Explanation

What the search assistant does

The stated problem is ordinary usability. Typing a full query on a device is slow, users misspell things, and they often do not know the exact title of what they want. The search assistant reduces typing and steers the user toward queries that will actually return results, since every suggested string corresponds to assets that exist in the store.

That second property is the one with strategic weight. The suggestion list cannot offer a query with no inventory behind it. The store is not completing the user’s thought. It is proposing queries it already knows how to answer profitably.

How suggestions are generated

The mechanism is prefix matching. The system holds words drawn from asset names and titles, and compares the prefixes of those words against the characters the user has entered. As each additional character arrives the candidate set narrows, which is what produces the progressive refinement shown in Figures 7A through 7E.

The hints data structure is described as a trie. A trie stores strings by shared prefix, so finding every word beginning with a given sequence is a walk down a small number of nodes rather than a scan of the catalog. It also explains a behavior ASO practitioners see constantly: suggestions respond to the start of words, not to the middle of them. A trie has no cheap answer to “which words contain this substring”.

The patent also notes the suggestions in the hints structure are precomputed with their metadata attached, and that the number returned can be limited. So the dropdown is not calculated live from the catalog on every keystroke. It is a lookup against a periodically rebuilt index, which means suggestion changes lag behind the purchase behavior that drives them.

The two databases and the popularity module

Figure 3 lays out the architecture. The content database stores the descriptive metadata and the media files themselves. The finance database stores transaction records: what was purchased, at what price. These are separate systems, and the separation is the interesting part, because the suggestion ordering does not come from the content side at all.

The popularity module reads the finance database, derives a popularity figure per asset defined as the frequency at which purchases of that asset occur, and updates those figures periodically. The patent describes the system as able to monitor and track sales for this purpose.

For apps, “purchase” in 2007 language covers the download or acquisition event. The structural claim is what matters: the ranking input for suggestions is the transaction log, not the search log.

The two filters, and why they run before ordering

Claim 1 is precise about sequence. For each candidate word the system determines whether the client device supports the media type of at least one associated asset. If the device supports none of them, the word is removed, producing what the claim calls a filtered set. Only then is sales popularity data obtained, and only then is the filtered set ordered.

A geographic filter works the same way, removing words whose assets are not available in the client’s location.

Order of operations matters here. A globally dominant asset that is unavailable in a territory does not occupy a suggestion slot in that territory and then get skipped. It is removed before ranking, and everything below it moves up. This is a clean mechanical explanation for why suggestion sets in a small market can look nothing like the equivalent list in the United States, and it argues for treating suggestion research as strictly per storefront.

How many slots exist

The examples in the description show up to ten suggestions for a desktop or browser interface and up to four for a mobile or touch interface, with the returned count able to be limited.

Treat those numbers as illustrative of the era rather than as current App Store behavior. The durable point is that the slot count is a deliberate parameter that varies by surface, and that on the smallest surfaces it is very small.

What is claimed

Claim 1 covers receiving at least one search character at an online media store from a client device, determining a set of words matching that character where each word is associated with assets that each have a media type, then per word determining whether the device supports the media type of at least one associated asset, removing the word if not, obtaining sales popularity data based on purchase data for the assets matching the filtered words, and ordering the filtered set to prioritize words based on that popularity data.

The claim is narrow in a specific way. It requires the device capability filter. That is unusual and dates the filing: in 2007 Apple was serving a store whose assets included formats many client devices could not handle, so the filter was a real engineering need. A modern App Store implementation would use device compatibility rather than media type, but the claimed shape is the same, filter to what this device can actually receive, then rank by what sells.

How to use this in practice

• Research suggestions per storefront, on a device of the type you care about, because filtering happens before ranking and both filters are client dependent.
• Check where your brand term sits as a prefix. If the distinctive word in your app name is not the first word, users typing the obvious first letters may never see you suggested.
• Read the suggestion list as a purchase leaderboard filtered by prefix. It tells you which terms have concentrated conversion behind them, which is useful competitive intelligence independent of any keyword tool.
• Expect suggestion changes to lag your ranking changes, because the hints structure is precomputed and refreshed periodically rather than recalculated live.

Family and related patents

Apple kept this line alive for nearly a decade. The original was filed in October 2007 and granted in January 2013. Three continuations followed: US8639716B2 filed January 2013, US8943089B2 filed December 2013, and US9305101B2 filed January 2015 and granted April 2016, all naming Christopher Volkert and carrying the same title.

A continuation chain of that length is a signal in itself. Apple was still investing in protecting store search assistance nine years after the first filing, which suggests the feature was considered commercially significant rather than incidental.

For the layers that run after a query is submitted rather than while it is typed, see US9405832B2 on query classification and US9280595B2 on concept matching.