PROGRESSIVE SPATIAL SEARCHING USING AUGMENTED STRUCTURES
First Claim
1. A method comprising:
- generating a character string search structure that includes an initial node and a plurality of internal nodes included in string paths from the initial node to terminal nodes, each string path representing a valid character string;
storing at least one retrieval item in a computing device storage area associated with each terminal node, wherein the retrieval item includes an item location indicator and a recommendation indicator associated with the retrieval item;
determining a cardinality of augmented non-terminal nodes for storing spatial bound indicators indicating bounds of sub-structures of the character string search structure that emanate from the augmented non-terminal nodes;
determining a set of augmented non-terminal nodes based on comparing a benefit value of each augmented non-terminal node with a benefit value of an ancestor node of the augmented non-terminal node in the character string search structure, based on a benefit function of nodes and having the determined cardinality;
determining spatial bound values associated with spatial regions represented by each of the augmented non-terminal nodes included in the set, based on comparing error values of bounds associated with a first non-terminal node spatial region with error values of bounds associated with spatial regions associated with nodes that are descendants of the first non-terminal node; and
storing each spatial bound value in association with the respective associated augmented non-terminal node.
2 Assignments
0 Petitions
Accused Products
Abstract
A location associated with a user of a computing device and a prefix portion of an input string may be received as one or more successive characters of the input string are provided by the user via the computing device. A list of suggested items may be obtained based on a function of respective recommendation indicators and proximities of the items to the location in response to receiving the prefix portion, and based on partially traversing a character string search structure having a plurality of non-terminal nodes augmented with bound indicators associated with spatial regions. The list of suggested items and descriptive information associated with each suggested item may be returned to the user, in response to receiving the prefix portion, for rendering an image illustrating indicators associated with the list in a manner relative to the location, as the user provides each successive character of the input string.
-
Citations
5 Claims
-
1. A method comprising:
-
generating a character string search structure that includes an initial node and a plurality of internal nodes included in string paths from the initial node to terminal nodes, each string path representing a valid character string; storing at least one retrieval item in a computing device storage area associated with each terminal node, wherein the retrieval item includes an item location indicator and a recommendation indicator associated with the retrieval item; determining a cardinality of augmented non-terminal nodes for storing spatial bound indicators indicating bounds of sub-structures of the character string search structure that emanate from the augmented non-terminal nodes; determining a set of augmented non-terminal nodes based on comparing a benefit value of each augmented non-terminal node with a benefit value of an ancestor node of the augmented non-terminal node in the character string search structure, based on a benefit function of nodes and having the determined cardinality; determining spatial bound values associated with spatial regions represented by each of the augmented non-terminal nodes included in the set, based on comparing error values of bounds associated with a first non-terminal node spatial region with error values of bounds associated with spatial regions associated with nodes that are descendants of the first non-terminal node; and storing each spatial bound value in association with the respective associated augmented non-terminal node. - View Dependent Claims (2, 3, 4, 5)
-
Specification