Progressive content-based retrieval of image and video with adaptive and iterative refinement

• US 5,734,893 A
• Filed: 09/28/1995
• Issued: 03/31/1998
• Est. Priority Date: 09/28/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Castelli, Vittorio, Li, Chung-Sheng, Chen, Ming-Syan, Turek, John Joseph Edward
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/535,500
• Time in Patent Office: 915 Days
• Field of Search: 395/605, 395/604, 395/10, 395/602, 395/615, 395/603, 395/611, 382/201, 382/203
• US Class Current: 707/694
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus for minimizing the time required to obtain results for a content based query in a data base. More specifically, with this invention, the data base is partitioned into a plurality of groups. Then, a schedule or sequence of groups is assigned to each of the operations of the query, where the schedule represents the order in which an operation of the query will be applied to the groups in the schedule. Each schedule is arranged so that each application of the operation operates on the group which will yield intermediate results that are closest to final results.

Claims

1. A method of processing a content based query in a database, said method comprising:

partitioning said database into groups of data; and

assigning a schedule to each operation of a plurality of operations of said query, said schedule representing an order of said groups upon which each said operation is applied, said order in said schedule being arranged so that by each application of each said operation according to said schedule, a group is chosen to minimize the difference between the current result and a final result which will yield intermediate results closest to said final result.

2. A method as recited in claim 1, wherein said schedule for each operation is assigned by a user.

3. A method as recited in claim 1, wherein said schedule for each operation is assigned by a rule based expert system in accordance with a set rules implied by a user query.

4. A method as recited in claim 1, wherein said query is an example of a target result, wherein said example is modified by adding or removing details of the query depending upon the contents of said results.

5. A method as recited in claim 1, wherein each entry of said database comprises a plurality of array attributes, and wherein each of said groups of data comprises selected ones of said array attribute.

6. A method as recited in claim 1, wherein each entry of said database comprises a plurality of array attributes, and wherein each of said array attributes comprises a number of said groups.

7. A method as recited in claim 1, wherein each entry of said database comprises a plurality of array transformed attributes, and wherein each of said groups of data comprises selected ones of said array transformed attribute.

8. A method as recited in claim 1, wherein each entry of said database comprises a plurality of array transformed attributes, and wherein each of said array transformed attributes comprises a number of said groups.

9. A method as recited in claim 3, wherein said query is modified by a user.

10. A method as recited in claim 3, wherein said query is modified by a rule based expert system.

11. A method as recited in claim 10, wherein said data in said database is grouped by feature extraction directly from an array attribute and/or from a transformation of said array attribute of entries in said database.

12. An apparatus for processing a content based query in a database, said apparatus comprising:

means for partitioning said database into groups of data; and

means for assigning a schedule to each operation of a plurality of operations of said query, said schedule representing an order of said groups upon which each said operation is applied, said order in said schedule being arranged so that, when applied, each application of said operation according to said schedule results in a group being chosen to minimize the difference between a current result and a final result which will yield intermediate results closest to said final result.

13. A method of processing a content based query in a database, said method comprising the steps of:

partitioning data in said database into a plurality of groups according to group attributes;

establishing a plurality of schedules of said groups, one for each of a sequence of operations of said query;

performing a first of said sequence of operations according to said schedules to produce intermediate query results;

reviewing said intermediate query results to determine whether said query has been satisfied;

performing a next of said sequence of operations on said intermediate results to produce further intermediate results if said reviewing determines that said query has not been satisfied;

analyzing said further intermediate results to determine whether said query has been satisfied; and

repeating said performing of said next of said sequence of operations and said analyzing of said further intermediate results until said analyzing determines that said query has been satisfied.

14. The method of claim 13 further comprising the step of adjusting said schedules based on said reviewing.

15. The method of claim 13 further comprising the step of adjusting said schedules based on said analyzing, and wherein said performing a next of said sequence of operations, said analyzing, and said adjusting steps are repeated until said query is satisfied.

16. The method of claim 13 further comprising the step of adjusting said operations of said query based on said reviewing.

17. The method of claim 13 further comprising the step of adjusting said operations of said query based on said reviewing, and wherein said performing a next of said sequence of operations, said analyzing, and said adjusting steps are repeated until said query is satisfied.

18. The method of claim 13 further comprising selecting said group attributes based upon said query prior to said partitioning.

19. The method of claim 13 wherein said reviewing and said analyzing are conducted by a user.

20. The method of claim 13 wherein said reviewing and said analyzing are conducted by a rule based expert system.

21. The method of claim 13 wherein said performing a first of said sequence of operations comprises searching said groups based upon scaler attributes.

22. The method of claim 21 wherein said performing a next of said sequence of operations on said intermediate results comprises searching said intermediate results on array attributes.

23. The method of claim 13 wherein said operations of said query comprises operations selected from the group comprising spatial, spectral, temporal and numerical accuracy attributes of said data.