Dynamic menus for multi-prefix interactive mobile searches

• US 8,255,411 B1
• Filed: 11/17/2009
• Issued: 08/28/2012
• Est. Priority Date: 06/19/2008
• Status: Active Grant

• Current Assignee: Tropare, Inc.
• Original Assignee: Boopsie Incorporated
• Inventors: Carpenter, G. Gregory, Kay, Timothy L.
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US12/620,195
• Time in Patent Office: 1,015 Days
• Field of Search: 707/764, 707/765, 709/204
• US Class Current: 707/764
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures

Abstract

The present invention includes systems and methods for retrieving information via a flexible and consistent targeted search model that employs interactive multi-prefix, multi-tier and dynamic menu information retrieval techniques that provide context-specific functionality tailored to particular information channels, as well as to records within or across such channels, and other known state information. Users are presented with a consistent search interface among multiple tiers across and within a large domain of information sources, and need not learn different or special search syntax. A thin-client server-controlled architecture enables users of resource-constrained mobile communications devices to locate targeted information more quickly by entering fewer keystrokes and performing fewer query iterations and web page refreshes, which in turn reduces required network bandwidth.

Claims

1. A method for caching results of multi-prefix user queries in an information retrieval system, the method comprising the following steps:

(a) receiving a multi-prefix user query containing a plurality of prefix terms;

(b) retrieving from an index, for each prefix term, a list of records containing at least one word having a prefix matching that prefix term;

(c) generating a result list for the user query by intersecting the lists of records retrieved from the index;

(d) computing the value of a query function to determine whether to cache the result list, wherein the value of the query function is dependent upon a plurality of factors, including the total number of characters in the user query and the processing time required to retrieve and intersect the lists of records from the index to generate the result list; and

(e) conditionally caching the result list in storage, based upon a comparison of the value of the query function to a predefined threshold,

(f) whereby the processing time for a subsequent user query is decreased by retrieving the cached result list from storage.

2. The method of claim 1, wherein the value of the query function is equal to the total number of characters in the user query.

3. The method of claim 1, wherein the value of the query function is equal to the amount of processing time required to retrieve and intersect the lists of records from the index to generate the result list.

4. The method of claim 1, further comprising the step of pre-caching into storage (prior to receiving the user query), for each single-letter prefix, a list of records containing at least one word having a prefix matching that single-letter prefix.

5. The method of claim 4, further comprising the step of pre-caching into storage (prior to receiving the user query), for each pair of single-letter prefixes, a list of records resulting from the intersection of the list of records corresponding to each letter of that pair.

6. A method for processing multi-prefix user queries in an information retrieval system, the method comprising the following steps:

(a) receiving a multi-prefix user query containing a plurality of prefix terms;

(b) determining, for each prefix term, whether a list of records corresponding to that prefix term has previously been cached in storage, and, if so, retrieving that list of records;

(c) retrieving from an index, for each prefix term not having a corresponding list of records cached in storage, a list of records containing at least one word having a prefix matching that prefix term;

(d) generating a result list for the user query by intersecting the lists of records retrieved from the cache in storage and from the index;

(e) computing the value of a query function to determine whether to cache the result list, wherein the value of the query function is dependent upon a plurality of factors, including the total number of characters in the user query and the processing time required to retrieve and intersect the lists of records from the index to generate the result list; and

(f) conditionally caching the result list in storage, based upon a comparison of the value of the query function to a predefined threshold,

(g) whereby the processing time for a subsequent user query is decreased by retrieving the cached result list from storage.

7. The method of claim 6, wherein the value of the query function is equal to the total number of characters in the user query.

8. The method of claim 6, wherein the value of the query function is equal to the amount of processing time required to retrieve and intersect the lists of records from the index to generate the result list.

9. The method of claim 6, further comprising the step of pre-caching into storage (prior to receiving the user query), for each single-letter prefix, a list of records containing at least one word having a prefix matching that single-letter prefix.

10. The method of claim 9, further comprising the step of pre-caching into storage (prior to receiving the user query), for each pair of single-letter prefixes, a list of records resulting from the intersection of the list of records corresponding to each letter of that pair.

11. An information retrieval system for caching results of multi-prefix user queries containing a plurality of prefix terms, the system comprising:

(a) a multi-prefix search module that retrieves from an index, for each prefix term, a list of records containing at least one word having a prefix matching that prefix term; and

(b) a result delivery module that;

(i) generates a result list by intersecting the lists of records retrieved from the index,

(ii) computes the value of a query function to determine whether to cache the result list, wherein the value of the query function is dependent upon a plurality of factors, including the total number of characters in the user query and the processing time required to retrieve and intersect the lists of records from the index to generate the result list, and

(iii) conditionally caches the result list in storage, based upon a comparison of the value of the query function to a predefined threshold,

(c) whereby the processing time for a subsequent user query is decreased by retrieving the cached result list from storage.

12. The system of claim 11, wherein the value of the query function is equal to the total number of characters in the user query.

13. The system of claim 11, wherein the value of the query function is equal to the amount of processing time required to retrieve and intersect the lists of records from the index to generate the result list.

14. The system of claim 11, wherein the system pre-caches into storage (prior to receiving the user query), for each single-letter prefix, a list of records containing at least one word having a prefix matching that single-letter prefix.

15. The system of claim 14, wherein the system pre-caches into storage (prior to receiving the user query), for each pair of single-letter prefixes, a list of records resulting from the intersection of the list of records corresponding to each letter of that pair.

16. An information retrieval system for processing multi-prefix user queries containing a plurality of prefix terms, the system comprising:

(a) a multi-prefix search module that

(i) determines, for each prefix term, whether a list of records corresponding to that prefix term has previously been cached in storage, and, if so, retrieves that list of records, and

(ii) retrieves from an index, for each prefix term not having a corresponding list of records cached in storage, a list of records containing at least one word having a prefix matching that prefix term; and

(b) a result delivery module that;

(i) generates a result list by intersecting the lists of records retrieved from the index,

(ii) computes the value of a query function to determine whether to cache the result list, wherein the value of the query function is dependent upon a plurality of factors, including the total number of characters in the user query and the processing time required to retrieve and intersect the lists of records from the index to generate the result list, and

(iii) conditionally caches the result list in storage, based upon a comparison of the value of the query function to a predefined threshold,

(c) whereby the processing time for a subsequent user query is decreased by retrieving the cached result list from storage.

17. The system of claim 16, wherein the value of the query function is equal to the total number of characters in the user query.

18. The system of claim 16, wherein the value of the query function is equal to the amount of processing time required to retrieve and intersect the lists of records from the index to generate the result list.

19. The system of claim 16, wherein the system pre-caches into storage (prior to receiving the user query), for each single-letter prefix, a list of records containing at least one word having a prefix matching that single-letter prefix.

20. The system of claim 19, wherein the system pre-caches into storage (prior to receiving the user query), for each pair of single-letter prefixes, a list of records resulting from the intersection of the list of records corresponding to each letter of that pair.

21. A method for utilizing hybrid prefix terms to facilitate processing of multi-prefix user queries in an information retrieval system, the method comprising the following steps:

(a) generating an index of prefix elements, wherein each prefix element is associated with a list of records containing at least one word having a prefix matching that prefix element;

(b) sorting the lists of records to identify the Nth longest list, having a length of L records;

(c) generating a set of hybrid prefix elements, for each list of records having a length greater than L, by intersecting that list of records with each longer list of records, and adding the sets of hybrid prefix elements to the index;

(d) receiving a multi-prefix user query containing a plurality of prefix terms;

(e) generating hybrid prefix terms by combining pairs of prefix terms;

(f) generating, and adding to the index, a set of repeated hybrid prefix elements, wherein each repeated hybrid prefix element is associated with a list of records containing repeated instances of words having a prefix matching that repeated hybrid prefix element;

(g) replacing repeated single-prefix terms with repeated hybrid prefix terms;

(h) retrieving from the index, for each prefix term or hybrid prefix term, a list of records corresponding to that prefix term or hybrid prefix term; and

(i) generating a result list for the user query by intersecting the lists of records retrieved from the index,

(j) whereby the processing time for the user query is decreased due to the prior generation of the hybrid prefix elements added to the index.

22. An information retrieval system that utilizes hybrid prefix terms to facilitate processing of multi-prefix user queries, the system comprising:

(a) an index generator that generates an index of prefix elements, wherein each prefix element is associated with a list of records containing at least one word having a prefix matching that prefix element;

(b) a list sorter that sorts the lists of records to identify the Nth longest list, having a length of L records;

(c) a hybrid prefix generator that generates a set of hybrid prefix elements, for each list of records having a length greater than L, by intersecting that list of records with each longer list of records, and adds the sets of hybrid prefix elements to the index; and

(d) a multi-prefix query processor that

(i) receives a multi-prefix user query containing a plurality of prefix terms,

(ii) generates hybrid prefix terms by combining pairs of prefix terms;

(iii) generates, and adds to the index, a set of repeated hybrid prefix elements, wherein each repeated hybrid prefix element is associated with a list of records containing repeated instances of words having a prefix matching that repeated hybrid prefix element;

(iv) replaces repeated single-prefix terms with repeated hybrid prefix terms;

(v) retrieves from the index, for each prefix term or hybrid prefix term, a list of records corresponding to that prefix term or hybrid prefix term; and

(vi) generates a result list for the user query by intersecting the lists of records retrieved from the index,

(e) whereby the processing time for the user query is decreased due to the prior generation of the hybrid prefix elements added to the index.