Apparatus and method for searching information

• US 8,577,861 B2
• Filed: 07/17/2009
• Issued: 11/05/2013
• Est. Priority Date: 07/17/2008
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Nokia Corporation
• Inventors: Aley, James
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/054,553
• Publication Number:
  US 20110270874A1
• Time in Patent Office: 1,572 Days
• Field of Search: 707/705, 707769-778
• US Class Current: 707/706
• CPC Class Codes: G06F 16/332 Query formulation

Abstract

A method and apparatus for use in servicing a search request where the search request comprises a plurality of parts (such as characters) and establishing a list of tokens where the tokens correspond to elements of objects and have a numerical value. For each part of the search request a subset of the list is determined, said subset identifying a set of objects which may satisfy the search query. The subsets may be identified iteratively. Token encoding is used to encode tokens based on a content of said elements and, in this case, the same token encoding is used to encode the parts of the search request. The token encoding may comprise differential encoding. In certain embodiments, resource requirements necessary to complete the search request are determined based on the identified subsets.

Claims

1. A method comprising:

accessing, by a computing device, an ordered list comprising a plurality of tokens, said tokens corresponding to elements of one or more objects, said list storing, for each token in said list, a corresponding document identifier, wherein said list is ordered according to a value of said token and said tokens are encoded using differential encoding whereby a value for a second and each subsequently encoded character is dependent on a value of a preceding character,

receiving, by the computing device, a search term comprising a plurality of parts, and

identifying, by the computing device, a subset of said list for a first part of said search term and a further subset for at least one subsequent part of said search term, wherein each subset corresponds to possible results for said search term.

2. The method according to claim 1 wherein successive subsets are iteratively identified for more than one successive part of said search term.

3. The method according to claim 2 wherein each iteration has a corresponding part of said search term and a subset corresponding to said iteration is identified with reference to said corresponding part, and each preceding part, of said search term.

4. The method according to claim 1 wherein said tokens are encoded such that two or more of said elements may correspond to the same token.

5. The method according to claim 1 further comprising:

for an identified subset, determining a resource requirement necessary to complete a search request, determining if said resource requirement meets a specified criteria; and

completing said search request if said resource requirement meets said specified criteria.

6. The method according claim 5 further comprising iteratively identifying successive subsets for more than one successive part of said search term and, for a successive subset of a successive iteration, determining if said resource requirement meets said specified criteria.

7. Apparatus comprising:

at least one processor, and at least one memory including computer code, the at least one memory and the computer code configured to, with the at least one processor, cause the apparatus at least to perform;

accessing an ordered list comprising a plurality of tokens, said tokens corresponding to elements of one or more objects, said list storing, for each token in said list, a corresponding document identifier, wherein said list is ordered according to a value of said token and said tokens are encoded using differential encoding whereby a value for a second and each subsequently encoded character is dependent on a value of a preceding character,

receiving a search term comprising a plurality of parts, and

identifying a subset of said list for a first part of said search term and a further subset for at least one subsequent part of said search term, wherein each subset corresponds to possible results for said search term.

8. Apparatus according to claim 7 wherein the at least one memory and the computer code are further configured to, with the at least one processor, cause the apparatus to iteratively identify successive subsets for more than one successive part of said search term.

9. Apparatus according to claim 8 wherein each iteration has a corresponding part of said search term and a subset corresponding to said iteration is identified with reference to said corresponding part, and each preceding part, of said search term.

10. Apparatus according to claim 7 wherein said tokens have a numerical value and said list is ordered according to a numerical value of said tokens.

11. Apparatus according to claim 10 wherein said numerical value is represented in the list as a floating point number.

12. Apparatus according to claim 7 wherein said tokens are encoded such that two or more of said elements may correspond to the same token.

13. Apparatus according to claim 7, wherein the at least one memory and the computer code are further configured to, with the at least one processor, cause the apparatus to:

for an identified subset, determine a resource requirement necessary to complete a search request, determine if said resource requirement meets a specified criteria; and

complete said search request if said resource requirement meets said specified criteria.

14. Apparatus according to claim 13, wherein the at least one memory and the computer code are further configured to, with the at least one processor, cause the apparatus to iteratively identify successive subsets for more than one successive part of said search term and, for a successive subset of a successive iteration, determine if said resource requirement meets said specified criteria.

15. Apparatus according claim 13 wherein determining a resource requirement necessary to complete a search request is carried out with reference to one or more of:

a number of parts of said search term, a number of documents which may be associated with said search term, and a number of characters utilized in said token encoding.

16. A computer readable medium storing instructions, said instructions being such that when processed by a processor configure said processor to:

access an ordered list comprising a plurality of tokens, said tokens corresponding to elements of one or more objects, said list storing, for each token in said list, a corresponding document identifier, wherein said list is ordered according to a value of said token and said tokens are encoded using differential encoding whereby a value for a second and each subsequently encoded character is dependent on a value of a preceding character,

receive a search term comprising a plurality of parts, and

identify a subset of said list for a first part of said search term and a further subset for at least one subsequent part of said search term, wherein each subset corresponds to possible results for said search term.

17. A method comprising:

representing each of a plurality of elements of one or more objects as a corresponding token with a numerical value,

accessing, by a computing device, a list of tokens having a numerical value, each token representing at least one of a plurality of elements of one or more objects, said list storing, for each token in said list, an object identifier identifying an object wherein an element corresponding to said token may be found, said list being ordered according to said numerical values of said tokens and said tokens being encoded using differential encoding whereby a value for a second and each subsequently encoded character is dependent on a value of a preceding character,

receiving, by a computing device, a search request comprising a search term having a plurality of parts, receiving, for each part in said search term, an indication of a subset of said list which satisfies said search request, and

predicting, by a computing device, a resource requirement necessary to complete said search request based on a number of parts of said search term.

18. Apparatus comprising:

at least one processor, and at least one memory including computer code, the at least one memory and the computer code configured to, with the at least one processor, cause the apparatus at least to perform;

representing each of a plurality of elements of one or more objects as a corresponding token with a numerical value,

accessing a list of tokens having a numerical value, each token representing at least one of a plurality of elements of one or more objects, said list storing, for each token in said list, an object identifier identifying an object wherein an element corresponding to said token may be found, said list being ordered according to said numerical values of said tokens and said tokens being encoded using differential encoding whereby a value for a second and each subsequently encoded character is dependent on a value of a preceding character,

receiving a search request comprising a search term having a plurality of parts, receiving, for each part in said search term, an indication of a subset of said list which satisfies said search request, and

predicting a resource requirement necessary to complete said search request based on a number of parts of said search term.