Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-05-25
2002-08-06
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C706S045000
Reexamination Certificate
active
06430573
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to the field of the generation of sequences and, in particular, the generation of sequences of items from a database such that the relationship between the attributes of the component items in the sequence is controlled.
It is to be understood that in the present description the term <<database>> is used to designate any collection of data, for example covering both pre-stored data and data which is dynamically collected.
There are many situations in which it is necessary or desirable to create a sequence of items from a collection of items for which data is available, and it is important that the created sequence should be <<coherent>>, that is, that there should be a particular relationship between attributes of the component items in the sequence (typically involving a criterion that the attributes of the component items of the sequence should not be too dissimilar, especially for successive items in the sequence). The sequences in question include temporal sequences and spatial sequences. A typical case where this problem arises is in the field of multimedia and, notably, the problem of automatic generation of recitals (such a recital is an example of a temporal sequence). Here the term <<recital>> is used not only to designate a sequence of musical pieces but, more generally, any temporal sequence of multimedia items (film clips, documentaries, text items, etc.). An example of a problem involving a spatial sequence concerns the designing of a thematically-linked layout of paintings for rooms in an art gallery.
2. Description of the Prior Art
It has been proposed in the paper <<Répresentation de séquences définies sur des ensembles non instanciés par arbre PQR partiel>> by Berkaoui et al [Journées Francophones de Programmation Logique par Contraintes, 1998] to use a Constraint Satisfaction approach for solving scheduling problems. However, the approach proposed in this paper does not consider the <<coherence>> of the sequence of items which is produced, notably it does not enable the similarity or dissimilarity of items making up the sequence to be controlled.
SUMMARY OF THE INVENTION
The present invention provides a system and method which produces <<coherent>> sequences of items in a particular order. The items are, generally, stored in a database and described in terms of data pairs each consisting of an attribute and the corresponding value. The problem of creating the desired sequence is treated as a Constraint Satisfaction Problem (CSP). The sequence to be obtained is specified by formulating a collection of constraints holding on items in the database, each constraint describing a particular property of the sequence. The sequence can be specified by any number of constraints.
According to the present invention, the items in the database exhibit a particular generic format with associated taxonomies for at least some of the attribute values. Also, the constraints are specified out of a predetermined library of generic constraint classes which have been specially formulated. The special constraint classes used in the present invention allow the expression of desired properties of the target sequence, notably properties of similarity between groups of items, properties of dissimilarity, and properties of cardinality. These constraint classes enable the properties of coherent sequences to be expressed in a particularly simple manner.
It is the combination of the use of a generic format for items in the database and the special constraint classes which enables the preferred embodiments of the present invention to use CSP solution techniques to solve the difficult combinatorial problem of building an ordered collection of elements satisfying a number of constraints.
REFERENCES:
patent: 5423033 (1995-06-01), Yuen
patent: 5616876 (1997-04-01), Cluts
patent: 5636328 (1997-06-01), Kautz et al.
patent: 5870746 (1999-02-01), Knutson et al.
patent: 5969283 (1999-10-01), Looney et al.
patent: 6147940 (2000-11-01), Yankowski
Pu P et al: “Assembly planning using case adaptation methods” Proceedings of 1995 IEEE International Conference on Robotics and Automation (CAT. No. 95CH3461-1), Proceedings of 1995 IEEE International Conference on Robotics and Automation, Nagoya, Japan, May 21-27, 1995, pp. 982-987 vol. 1, XP002091213 ISBN 0-7803-1965-6, 1995, New York, NY, USA, IEE, USA.
Purvis L et al: “Adaptation using constraint satisfaction techniques” Case-Based Reasoning Research and Development. First International Conference, ICCBR-95, Proceedings, Case-Based Reasoning Research and Development. First International Conference, ICCBR-95, Proceedings, Sesimbra Portugal, Oct. 23-26, 1995, pp. 289-300, XP002091214 ISBN 3-540-60598-3, 1995, Berlin, Germany, Springer-Verlag, Germany.
Pachet François
Roy Pierre
Robinson Greta
Sony France S.A.
LandOfFree
Sequence generation using a constraint satisfaction problem... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sequence generation using a constraint satisfaction problem..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequence generation using a constraint satisfaction problem... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2943357