Methods and apparatus for processing ranked fuzzy cartesian queries

• US 6,778,946 B1
• Filed: 10/17/2000
• Issued: 08/17/2004
• Est. Priority Date: 10/17/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chang, Yuan-Chi, Li, Chung-Sheng
• Primary Examiner(s): PALADINI, ALBERT WILLIAM
• Application Number:
  US09/690,378
• Time in Patent Office: 1,400 Days
• Field of Search: 703/2, 706/900, 706/52, 706/46, 706/8, 706/4, 707/3, 707/5, 707/6, 708/422
• US Class Current: 703/2
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

Ranked fuzzy cartesian queries request top-K composite objects in a multimedia database. These composite objects, comprising multiple simple objects with their relations specified, are ranked by a fuzzy AND score of individual object properties and their fuzzy relations. Ranked fuzzy cartesian queries appeared in many different applications but were not fully exploited because of high computational complexity. In accordance with the present invention, methods and apparatus are provided for preprocessing a ranked fuzzy cartesian query to prune candidates which will not appear in the final top-K composite objects. Algorithms for processing queries against two simple objects and against three or more simple objects are separately described. These algorithms use a bound-and-prune technique to determine the candidates which can be removed from the search space. Disclosed methods are guaranteed to have no false dismissal.

Claims

1. A computer-based method of pruning a search space of a composite object associated with a ranked fuzzy cartesian query, the method comprising the steps of:

obtaining at least two simple objects associated with the composite object, the at least two simple objects being characterized by respective lists of one or more candidates associated with the simple objects, the candidates of the at least two lists having relations respectively therebetween which are defined in accordance with a fuzzy specification, wherein each candidate in one of the lists, each candidate in the other of the lists and the relation therebetween form a path;

calculating a metric for at least a subset of the paths formed by the candidates and relations and identifying the paths having the top-K ranked path metrics; and

removing candidates from the at least two lists which are not associated with the paths having the top-K ranked path metrics such that a pruned composite object is formed that may be used in a fuzzy cartesian query evaluation operation.

2. The method of claim 1, wherein the metric calculating step comprises the steps of:

obtaining a fuzzy object score for each candidate in the at least two lists; and

determining a minimum fuzzy object score for each list.

3. The method of claim 2, wherein the metric calculating step further comprises the steps of:

obtaining a fuzzy relation score for a relation between a pair of candidates from the at least two lists; and

determining a minimum fuzzy relation score.

4. The method of claim 3, wherein the metric calculating step further comprises the step of using the minimum fuzzy object score and the minimum fuzzy relation score to identify the paths having the top-K ranked path metrics.

5. The method of claim 1, wherein the metric calculating step further comprises the steps of:

determining an evaluation set of candidates for a first one of the lists and an evaluation set for the second one of the lists, the respective evaluation sets including respective candidates associated with the paths having the top-K ranked path metrics;

generating complementary sets from the evaluation sets, respectively;

determining whether a path metric associated with a candidate in the first one of the evaluation sets and a candidate in the complementary set of the second one of the evaluation sets is not less than the minimum path metric;

determining whether a path metric associated with a candidate in the second one of the evaluation sets and a candidate in the complementary set of the first one of the evaluation sets is not less than the minimum path metric; and

ensuring that candidates associated with the path metrics that are not less than the minimum path metric are not removed from the at least two lists.

6. The method of claim 1, wherein the composite object is represented by at least three simple objects, each of the at least three simple objects being characterized by respective lists of one or more candidates associated with the simple objects, the candidates of the at least three lists having relations respectively between neighboring lists which are defined in accordance with a fuzzy specification, wherein each candidate in a first one of the lists, each candidate in a second one of the lists, each candidate in a third one of the lists, and the relations therebetween form a path.

7. The method of claim 6, further comprising the step of verifying that, for any portion of a path having removed candidates, there are at least K paths remaining in the pruned composite object with larger path metrics than the portion of the path having removed candidates.

8. The method of claim 7, wherein the verifying step is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when the size of each of the neighboring candidate lists, after the removing operation, is greater than K.

9. The method of claim 8, wherein the verifying step is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when the top-K ranked paths of the pairing are not removed.

10. The method of claim 9, wherein the verifying step is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when for any candidates in one of the lists of a pairing formed after the removing operation, there exists a candidate in the other list of the pairing formed after the removing operation such that the path metric associated with the two candidates is greater than any path metric associated with complements of the two lists formed after the removing operation.

11. The method of claim 10, wherein the verifying step is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when, for any candidates in one of the lists of a pairing after the removal operation, its path metric with any candidate in the other list of the pairing after the removal operation is greater than its path metric any candidate list in a complement of the other list.

12. Apparatus for pruning a search space of a composite object associated with a ranked fuzzy cartesian query, the apparatus comprising:

at least one processor operative to;

(i) obtain at least two simple objects associated with the composite object, the at least two simple objects being characterized by respective lists of one or more candidates associated with the simple objects, the candidates of the at least two lists having relations respectively therebetween which are defined in accordance with a fuzzy specification, wherein each candidate in one of the lists, each candidate in the other of the lists and the relation therebetween form a path;

(ii) calculate a metric for at least a subset of the paths formed by the candidates and relations and identify the paths having the top-K ranked path metrics; and

(iii) remove candidates from the at least two lists which are not associated with the paths having the top-K ranked path metrics such that a pruned composite object is formed that may be used in a fuzzy cartesian query evaluation operation.

13. The apparatus of claim 12, wherein the metric calculating operation comprises:

(i) obtaining a fuzzy object score for each candidate in the at least two lists; and

(ii) determining a minimum fuzzy object score for each list.

14. The apparatus of claim 13, wherein the metric calculating operation further comprises:

(i) obtaining a fuzzy relation score for a relation between a pair of candidates from the at least two lists; and

(ii) determining a minimum fuzzy relation score.

15. The apparatus of claim 14, wherein the metric calculating operation further comprises using the minimum fuzzy object score and the minimum fuzzy relation score to identify the paths having the top-K ranked path metrics.

16. The apparatus of claim 12, wherein the metric calculating operation further comprises:

(i) determining an evaluation set of candidates for a first one of the lists and an evaluation set for the second one of the lists, the respective evaluation sets including respective candidates associated with the paths having the top-K ranked path metrics;

(ii) generating complementary sets from the evaluation sets, respectively;

(iii) determining whether a path metric associated with a candidate in the first one of the evaluation sets and a candidate in the complementary set of the second one of the evaluation sets is not less than the minimum path metric;

(iv) determining whether a path metric associated with a candidate in the second one of the evaluation sets and a candidate in the complementary set of the first one of the evaluation sets is not less than the minimum path metric; and

(v) ensuring that candidates associated with the path metrics that are not less than the minimum path metric are not removed from the at least two lists.

17. The apparatus of claim 12, wherein the composite object is represented by at least three simple objects, each of the at least three simple objects being characterized by respective lists of one or more candidates associated with the simple objects, the candidates of the at least three lists having relations respectively between neighboring lists which are defined in accordance with a fuzzy specification, wherein each candidate in a first one of the lists, each candidate in a second one of the lists, each candidate in a third one of the lists, and the relations therebetween form a path.

18. The apparatus of claim 17, wherein the at least one processor is further operative to verify that, for any portion of a path having removed candidates, there are at least K paths remaining in the pruned composite object with larger path metrics than the portion of the path having removed candidates.

19. The apparatus of claim 18, wherein the verifying operation is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when the size of each of the neighboring candidate lists, after the removing operation, is greater than K.

20. The apparatus of claim 19, wherein the verifying operation is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when the top-K ranked paths of the pairing are not removed.

21. The apparatus of claim 20, wherein the verifying operation is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when for any candidates in one of the lists of a pairing formed after the removing operation, there exists a candidate in the other list of the pairing formed after the removing operation such that the path metric associated with the two candidates is greater than any path metric associated with complements of the two lists formed after the removing operation.

22. The apparatus of claim 21, wherein the verifying operation is satisfied for a pairing of neighboring candidate lists, wherein the first list forms a neighboring pairing with the second list and the second list forms neighboring pairing with the third list, when, for any candidates in one of the lists of a pairing after the removal operation, its path metric with any candidate in the other list of the pairing after the removal operation is greater than its path metric any candidate list in a complement of the other list.

23. An article of manufacture for pruning a search space of a composite object associated with a ranked fuzzy cartesian query, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining at least two simple objects associated with the composite object, the at least two simple objects being characterized by respective lists of one or more candidates associated with the simple objects, the candidates of the at least two lists having relations respectively therebetween which are defined in accordance with a fuzzy specification, wherein each candidate in one of the lists, each candidate in the other of the lists and the relation therebetween form a path;

calculating a metric for at least a subset of the paths formed by the candidates and relations and identifying the paths having the top-K ranked path metrics; and

removing candidates from the at least two lists which are not associated with the paths having the top-K ranked path metrics such that a pruned composite object is formed that may be used in a fuzzy cartesian query evaluation operation.