Sequence generation using a constraint satisfaction problem formulation

• US 6,430,573 B1
• Filed: 05/25/1999
• Issued: 08/06/2002
• Est. Priority Date: 05/27/1998
• Status: Expired due to Fees

• Current Assignee: Sony France SA (Sony Group Corp.)
• Original Assignee: Sony France SA (Sony Group Corp.)
• Inventors: Roy, Pierre, Pachet, Francois
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/318,007
• Time in Patent Office: 1,169 Days
• Field of Search: 707/8, 707/1, 707/104, 707/102, 707/104.1, 706/45
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/483 using metadata automatically derived from the content
• CPC Class Codes: G11B 27/036 Insert-editing
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and system for automatic generation of sequences (notably temporal or spatial sequences) from items in a database involves the organisation of the data in a generic format, and the formulation of the problem as a Constraint Satisfaction Problem using special constraint classes. The database format includes attribute values referring to a predetermined taxonomy allowing similarity and difference between the respective values to be evaluated. The special constraint classes include the classes of cardinality constraints (which allow it to be specified that the number of items whose attribute belongs to a given set is within a particular range, and/or that the number of values of an attribute is within a specified range), similarity or dissimilarity constraints (which allow it to be specified that successive items must be similar or different from each other) and global difference constraints (which allow it to be specified that the respective values of a given attribute for all items in a range must be different from each other).

Claims

1. A method of generating sequencing information representing a sequence made from a set of items selected in a database, the items having attributes and the attributes having values, comprising the steps of:

providing a database having therein data representative of the attributes of a plurality of items;

specifying desired features of the sequence in terms of requirements on values and/or variation in values of attributes of items in the desired sequence;

modelling the task of generating the desired sequence as a Constraint Satisfaction Problem having variables and constraints, the respective variables of the problem corresponding to the items in the desired sequence, and the respective constraints of the problem comprising standard constraints and specialized constraints corresponding to the desired features specified in the specifying step, wherein the specialized constraints are selected from the group consisting of cardinality on items, cardinality on attribute values, similarity constraints and dissimilarity constraints, wherein;

the cardinality on items is represented by the formula CI(I, j, a, b, E), wherein I is a set of item indices, j is an attribute index, a and b are integers and E is a subset of the possible values of attribute j;

the cardinality on attribute values is represented by the formula CA(I, j, a, b), wherein I, j, a and b are defined as above;

the similarity constraint is represented by the formula S(a, b, j, similar (.,.,.)), wherein a, b, and j are defined as above and similar(.,.,.) is a predicate; and

the dissimilarity constraint is represented by the formula similar(x, y, j);

=(x.a_j≠

y.a_j), wherein j, a and b are defined as above, and x and y are domain items; and

applying constraint satisfaction programming techniques to solve the modelled Constraint Satisfaction Problem.

2. The method according to claim 1, wherein:

the database-providing step comprises providing a database in which each item has at least one attribute for which a predetermined taxonomy is provided in association with the database, the predetermined taxonomy defining similarity and difference between different values of said attribute, and

the modelling step comprises generating at least one constraint requiring similarity or dissimilarity of an attribute between different items in the desired sequence.

3. The method of claim 2, wherein the modelling step comprises generating at least one constraint requiring similarity or dissimilarity of an attribute between successive items of a sub-set of contiguous items in the desired sequence.

4. The method of claim 2, wherein the modelling step comprises generating at least one constraint requiring similarity or dissimilarity of an attribute between all items in the desired sequence.

5. The method according to claim 1, wherein the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of items whose attribute (j) takes a value belonging to a given set (E) must be within a specified range (a,b).

6. The method of claim 5, wherein the modelling step comprises generating at least one constraint requiring that, in a sub-set of contiguous items in the desired sequence, the number of items whose attribute (j) takes a value belonging to a given set (E) must be within a specified range (a,b).

7. The method according to claim 2, wherein the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of items whose attribute (j) takes a value belonging to a given set (E) must be within a specified range (a,b).

8. The method of claim 7, wherein the modelling step comprises generating at least one constraint requiring that, in a sub-set of contiguous items in the desired sequence, the number of items whose attribute (j) takes a value belonging to a given set (E) must be within a specified range (a,b).

9. The method according to claim 1, wherein the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of different values for an attribute (j) of a number of items must be within a specified range (a,b).

10. The method of claim 9, wherein the modelling step comprises generating at least one constraint requiring that, in a sub-set of contiguous items in the desired sequence, the number of different values for an attribute (j) of the items of the sub-set must be within a specified range (a,b).

11. The method according to claim 2, wherein:

the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of different values for an attribute (j) of a number of items must be within a specified range (a,b).

12. The method of claim 11, wherein the modelling step comprises generating at least one constraint requiring that, in a sub-set of contiguous items in the desired sequence, the number of different values for an attribute (j) of the items of the sub-set must be within a specified range (a,b).

13. The method according to claim 5, wherein:

the modelling step comprises gene rating at least one constraint requiring that, in the desired sequence, the number of different values for an attribute (j) of a number of items must be within a specified range (a,b).

14. The method of claim 13, wherein the modelling step comprises generating at least one constraint requiring that, in a sub-set of contiguous items in the desired sequence, the number of different values for an attribute (j) of the items of the sub-set must be within a specified range (a,b).

15. A method for generating sequencing information representing the sequence of a set of musical pieces selected in a database, said musical pieces having attributes and the attributes having values, comprising the steps of:

providing a database having therein data representative of the attributes of a plurality of musical pieces;

specifying desired features of the sequence in terms of requirements on values and/or variation in values of attributes of musical pieces in the desired sequence;

modelling the task of generating the desired sequence as a Constraint Satisfaction Problem having variables and constraints, the respective variables of the problem comprising standard constraints and specialized constraints corresponding to the musical pieces in the desired sequence, and the respective constraints of the problem corresponding to the desired features specified in the specifying step, wherein the specialized constraints are selected from the group consisting of cardinality on items, cardinality on attribute values, similarity constraints and dissimilarity constraints, wherein;

the cardinality on items is represented by the formula CI(I, j, a, b, E), wherein I is a set of item indices, j is an attribute index, a and b are integers and E is a subset of the possible values of attribute j;

the cardinality on attribute values is represented by the formula CA(I, j, a, b), wherein I, j, a and b are defined as above;

the similarity constraint is represented by the formula S(a, b, j, similar (.,.,.)), wherein a, b, and j are defined as above and similar(.,.,.) is a predicate; and

the dissimilarity constraint is represented by the formula similar(x, y, j);

=(x.a_j≠

y.a_j), wherein j, a and b are defined as above, and x and y are domain items; and

applying constraint satisfaction programming techniques whereby to solve the modelled Constraint satisfaction problem.

16. The automatic recital-generation method according to claim 15, wherein:

the database-providing step comprises providing a database in which each musical piece has at least one attribute for which a predetermined taxonomy is provided in association with the database, the predetermined taxonomy defining similarity and difference between different values of said attribute, and

the modelling step comprises generating at least one constraint requiring similarity or dissimilarity of an attribute between different musical pieces in the desired sequence.

17. The automatic recital-generation method of claim 15, wherein the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of musical pieces whose attribute (j) takes a value belonging to a given set (E) must be within a specified range (a,b).

18. The automatic recital-generation method of claim 15, wherein the modelling step comprises generating at least one constraint requiring that, in the desired sequence, the number of different values for an attribute (j) of a number of musical pieces must be within a specified range (a,b).

19. A system adapted to generate sequencing information representing a sequence made from a set of items selected in a database, the items having attributes and the attributes having values, according to the method comprising the steps of:

providing a database having therein data representative of the attributes of a plurality of items;

specifying desired features of the sequence in terms of requirements on values and/or variation in values of attributes of items in the desired sequence;

modelling the task of generating the desired sequence as a Constraint Satisfaction Problem having variables and constraints, the respective variables of the problem corresponding to the items in the desired sequence, and the respective constraints of the problem comprising standard constraints and specialized constraints corresponding to the desired features specified in the specifying step, wherein the specialized constraints are selected from the group consisting of cardinality on items, cardinality on attribute values, similarity constraints and dissimilarity constraints, wherein;

the cardinality on items is represented by the formula CI(I, j, a, b, E), wherein I is a set of item indices, j is an attribute index, a and b are integers and E is a subset of the possible values of attribute j;

the cardinality on attribute values is represented by the formula CA(I, j, a, b), wherein I, j, a and b are defined as above;

the similarity constraint is represented by the formula S(a,b,j, similar (.,.,.)), wherein a, b, and j are defined as above and similar(.,.,.) is a predicate; and

the dissimilarity constraint is represented by the formula similar(x, y, j);

=(x.a_j≠

y.a_j), wherein, a and b are defined as above, and x and y are domain items; and

applying constraint satisfaction programming techniques whereby to solve the modelled Constraint Satisfaction Problem,

said system comprising a general-purpose computer and a monitor for display of the generated sequencing information.