# US 11,308,141 B2 · Template generation using directed acyclic word graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,141 B2 - Document ID: US11308141B2 - Status: Granted - Kind: B2 - Application number: 16/232,107 - Filed: 2018-12-26 - Published: 2020-07-02 - Granted: 2022-04-19 - Earliest claimed: 2018-12-26 - Assignees: Yahoo Assets LLC - Applicants: Yahoo Assets LLC - Inventors: Srinath Ravindran; Mahmoudreza Abasi; Narayan Bhamidipati - Web page: https://patentgrep.com/patent/US11308141B2 ## CPC - G06F 16/353: into predefined classes - G06F 7/08: Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) - G06F 16/322: {Trees} - G06F 16/328: {Management therefor} - G06F 16/335: Filtering based on additional data, e.g. user or group profiles (filtering in web context G06F16/9535, G06F16/9536) - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Technologies for template generation using directed acyclic word graphs (DAWGs). The technologies can include receiving a first plurality of titles from a first plurality of title feeds, and sorting the first plurality of titles into a plurality of category sets. And, for each category set of the plurality of category sets, the technologies can include transforming the respective titles belonging to the category set into a trie data structure by separating words in the respective titles into nodes of the trie data structure. For each category set, the technologies can also include transforming the trie data structure into a directed acyclic word graph (DAWG) data structure. Also, for each category set, the technologies can also include generating one or more unique templates based on the DAWG data structure. ## Claims ### Claim 1 A method comprising: receiving a first plurality of titles from a first plurality of title feeds; removing duplicate copies of titles in the first plurality of titles so that the plurality of first titles is transformed into a plurality of unique titles; sorting the plurality of unique titles into a plurality of category sets; and for each category set of the plurality of category sets: transforming the respective unique titles belonging to the category set into a trie data structure by separating words in the respective unique titles into nodes of the trie data structure, each node of the trie data structure comprising one word; normalizing the trie data structure by at least removing duplicates in the trie data structure; transforming the normalized trie data structure into a directed acyclic word graph (DAWG) data structure, the DAWG data structure comprising a plurality of fixed nodes and a plurality of variable nodes, each fixed node of the plurality of fixed nodes comprising one fixed word, and each variable node of the plurality of variable nodes comprising a plurality of alternative words representing multiple alternative words for the variable node; and generating one or more unique templates based on the DAWG data structure. ### Claim 2 (depends on 1) The method of claim 1, further comprising: receiving a second plurality of titles from feeds selected from the group of title feeds consisting of the first plurality of title feeds and a second plurality of title feeds; and for each generated unique template of the generated one or more unique templates of the plurality of category sets, searching the second plurality of titles by using the generated unique template as a regular expression to match one or more titles with the generated unique template. ### Claim 3 (depends on 2) The method of claim 2, further comprising: performing an action according to the matched one or more titles. ### Claim 4 (depends on 3) The method of claim 3, wherein the action comprises associating, in a database, the matched one or more titles with the generated unique template. ### Claim 5 (depends on 2) The method of claim 2, further comprising: associating, in a database, a given title of the second plurality of titles that matches multiple generated unique templates of the generated one or more unique templates of the plurality of category sets with only one of the multiple generated unique templates according to a criterion. ### Claim 6 (depends on 5) The method of claim 5, wherein the criterion comprises selecting one of the multiple generated unique templates that has been associated, in the database, with more titles than the other templates of the multiple generated unique templates. ### Claim 7 (depends on 1) The method of claim 1, wherein the transforming the respective unique titles belonging to the category set into the trie data structure comprises generating sub-trie data structures of the trie data structure in parallel. ### Claim 8 (depends on 1) The method of claim 1, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only two fixed words of two fixed nodes of the plurality of fixed nodes into each unique template of the one or more unique templates along with at least one wildcard parameter for one additional word. ### Claim 9 (depends on 8) The method of claim 8, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only one wildcard parameter for one additional word into each unique template of the one or more unique templates, such that the unique template can be used as a trigram. ### Claim 10 (depends on 8) The method of claim 8, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only two wildcard parameters for two additional words into each unique template of the one or more unique templates, such that the unique template can be used as a 4-gram. ### Claim 11 A non-transitory computer-readable storage medium tangibly encoded with computer-executable instructions, that when executed by a processor of computing device, performs a method, the method comprising: receiving a first plurality of titles from a first plurality of title feeds; sorting the first plurality of titles into a plurality of category sets; and for each category set of the plurality of category sets: transforming the respective titles belonging to the category set into a trie data structure by separating words in the respective titles into nodes of the trie data structure, each node of the trie data structure comprising one word; normalizing the trie data structure by at least removing duplicates in the trie data structure; and transforming the normalized trie data structure into a directed acyclic word graph (DAWG) data structure, the DAWG data structure comprising a plurality of fixed nodes and a plurality of variable nodes, each fixed node of the plurality of fixed nodes comprising one fixed word, and each variable node of the plurality of variable nodes comprising a plurality of alternative words representing multiple alternative words for the variable node. ### Claim 12 (depends on 11) The non-transitory computer-readable storage medium of claim 11, wherein the transforming the respective titles belonging to the category set into the trie data structure comprises generating sub-trie data structures of the trie data structure in parallel. ### Claim 13 (depends on 11) The non-transitory computer-readable storage medium of claim 11, wherein the method further comprises: for each category set of the plurality of category sets, generating one or more unique templates based on the respective DAWG data structure of the category set. ### Claim 14 (depends on 13) The non-transitory computer-readable storage medium of claim 13, further comprising: receiving a second plurality of titles from feeds selected from the group of title feeds consisting of the first plurality of title feeds and a second plurality of title feeds; and for each generated unique template of the generated one or more unique templates of the plurality of category sets, searching the second plurality of titles by using the generated unique template as a regular expression to match one or more titles with the generated unique template. ### Claim 15 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only two fixed words of two fixed nodes of the plurality of fixed nodes into each unique template of the one or more unique templates along with at least one wildcard parameter for one additional word. ### Claim 16 (depends on 15) The non-transitory computer-readable storage medium of claim 15, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only one wildcard parameter for one additional word into each unique template of the one or more unique templates, such that the unique template can be used as a trigram. ### Claim 17 A computing device, comprising: a processor; and a non-transitory computer-readable storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising: executable logic for receiving a first plurality of titles from a first plurality of title feeds; executable logic for sorting the first plurality of titles into a plurality of category sets; and for each category set of the plurality of category sets: executable logic for transforming the respective titles belonging to the category set into a trie data structure by separating words in the respective titles into nodes of the trie data structure, each node of the trie data structure comprising one word; executable logic for transforming the trie data structure into a directed acyclic word graph (DAWG) data structure, the DAWG data structure comprising a plurality of fixed nodes and a plurality of variable nodes, each fixed node of the plurality of fixed nodes comprising one fixed word, and each variable node of the plurality of variable nodes comprising a plurality of alternative words representing multiple alternative words for the variable node; and executable logic for generating one or more unique templates based on the DAWG data structure. ### Claim 18 (depends on 17) The computing device of claim 17, wherein the transforming the respective titles belonging to the category set into the trie data structure comprises generating sub-trie data structures of the trie data structure in parallel. ### Claim 19 (depends on 17) The computing device of claim 17, wherein the program logic further comprises: executable logic for receiving a second plurality of titles from feeds selected from the group of title feeds consisting of the first plurality of title feeds and a second plurality of title feeds; and for each generated unique template of the generated one or more unique templates of the plurality of category sets: executable logic for searching the second plurality of titles by using the generated unique template as a regular expression to match one or more titles with the generated unique template. ### Claim 20 (depends on 17) The computing device of claim 17, wherein the generating the one or more unique templates based on the DAWG data structure comprises including only two fixed words of two fixed nodes of the plurality of fixed nodes into each unique template of the one or more unique templates along with only one wildcard parameter for one additional word, such that the unique template can be used as a trigram.