×

Retrieval of prefix completions by way of walking nodes of a trie data structure

  • US 9,158,758 B2
  • Filed: 01/09/2012
  • Issued: 10/13/2015
  • Est. Priority Date: 01/09/2012
  • Status: Active Grant
First Claim
Patent Images

1. A method executed by a computer processor, the method comprising:

  • receiving a prefix that comprises at least one character; and

    using the prefix, executing a search over a computer-implemented trie data structure to retrieve a suggested completion for the prefix, the trie data structure comprising;

    a root node;

    a plurality of leaf nodes that are child nodes of the root node, the leaf nodes corresponding to a respective plurality of completions to potential prefixes, each leaf node in the plurality of leaf nodes having a respective score assigned thereto that is indicative of historic frequency of use of its corresponding completion; and

    a plurality of intermediate nodes, wherein each intermediate node is a descendant node of the root node and an ancestor node to at least one leaf node, the intermediate nodes corresponding to a respective plurality of extensions to the potential prefixes, and wherein each intermediate node is assigned a respective score that maps to a highest score assigned to a respective leaf node from amongst all leaf nodes that are child nodes of the respective intermediate node, wherein the suggested completion for the prefix is retrieved by walking nodes of the trie data structure based upon the respective scores assigned thereto.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×