METHOD AND APPARATUS FOR PROCESSING SEARCH REQUEST FOR A PARTITIONED INDEX

• US 20120047164A1
• Filed: 08/23/2010
• Published: 02/23/2012
• Est. Priority Date: 08/23/2010
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Saadat, Saied
• Granted Patent: US 9,229,946 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Techniques for enhanced processing of search requests directed to a partitioned index include receiving a request for a search of an index. The index is partitioned across a plurality of nodes in communication. The method also comprises determining whether the request is deterministic. The method further comprises determining a number of responses to request from at least one of the plurality of nodes based on whether the request is deterministic.

Claims

1. A method comprising:

receiving a request for a search of an index, wherein the index is partitioned across a plurality of nodes in communication;

determining whether the request is deterministic; and

determining a number of responses to request from at least one of the plurality of nodes based on whether the request is deterministic.

2. A method of claim 1, wherein the request is deterministic if no more than a predetermined number of sets of index entries at least substantively satisfies the request.

3. A method of claim 2, wherein the predetermined number is one.

4. A method of claim 1, wherein the responses are based, at least in part, on one or more matches from the search of the index.

5. A method of claim 1, wherein, if the request is not deterministic, then determining the number of responses to request further comprises:

determining a target number of responses to return in response to the request;

determining a number of responses on a local partition of a local node of the plurality of nodes; and

determining a shortage based, at least in part, on the target number of responses and the number of responses on the local partition.

6. A method of claim 5, wherein determining the number of responses to request further comprises determining whether the number of responses to request is greater than or equal to the shortage.

7. A method of claim 5, wherein determining the number of responses to request further comprises determining the number of responses to request by dividing a product of the shortage and a cushion factor by the number of responses on the local partition.

8. A method of claim 7, wherein the cushion factor is greater than one.

9. A method of claim 5, further comprising:

determining an average number of responses from a node in response to one or more similar previous requests; and

determining a number of the plurality of nodes from which to determine the number of responses to request by dividing a product of the shortage and a cushion factor by the average number of responses.

10. A method of claim 2, wherein, if the request is deterministic, then determining the number of responses to request further comprises:

determining a target number of responses to return in response to the request;

determining a confidence level that a response is at least substantially identical to one of the limited number of sets of index entries; and

determining the number of responses to request from substantively all nodes of the plurality of nodes based, at least in part, on the confidence level.

11. A method of claim 10, wherein, if the confidence level is at least substantively equal to 100%, then the number of responses to request is at least substantively equal to the target number of responses.

12. A method of claim 10, wherein, if the confidence level is less than 100%, then the number of responses to request is at least substantively equal to a product of a cushion factor times a ratio of the target number of responses divided by a number nodes in the plurality of nodes.

13. A method of claim 12, wherein, the cushion factor is greater than one by an amount that depends, at least in part, on the confidence level.

14. A method of claim 10, further comprising:

determining a maximum number of contributions from at least another one of the plurality of nodes in response to at least one similar previous deterministic request for substantively 100% confidence,

wherein the determining of the number of responses to request is further based, at least in part, on the maximum number of contributions.

15. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

receive a request for a search of an index, wherein the index is partitioned across a plurality of nodes in communication;

determine whether the request is deterministic; and

determine a number of responses to request from at least one of the plurality of nodes based on whether the request is deterministic.

16. An apparatus of claim 15, wherein the request is deterministic if no more than a predetermined number of sets of index entries at least substantively satisfies the request.

17. An apparatus of claim 15, wherein the responses are based, at least in part, on one or more matches from the search of the index.

18. An apparatus of claim 15, wherein, if the request is not deterministic, then determining the number of responses to request further causes the apparatus to:

determine a target number of responses to return in response to the request;

determine a number of responses on a local partition of a local node of the plurality of nodes; and

determine a shortage based, at least in part, on the target number of responses and the number of responses on the local partition.

19. An apparatus of claim 18, wherein determining the number of responses to request further comprises determining the number of responses to request by dividing a product of the shortage and a cushion factor by the number of responses on the local partition.

20. An apparatus of claim 16, wherein, if the request is deterministic, then determining the number of responses to request from each of the number of nodes further causes the apparatus to:

determine a target number of responses to return in response to the request;

determine a confidence level that a response is at least substantively identical to the limited number of sets of index entries; and

determine the number of responses to request from substantively all nodes of the plurality of nodes based, at least in part, on the confidence level.

21-56. -56. (canceled)