De l'utilité des contraintes pour explorer des catalogues
Avec un accès aux bases de données qui se généralise, la recherche d'objets dans des catalogue devient un sujet important. La Programmation par Contraintes assiste déjà les recherches de produits complexes et personnalisables, par le biais de configurateurs sous contraintes. Nous proposons d'assister les recherches dans des catalogues d'objets plus simples et pour lesquels aucun modèle logique n'est disponible. A ces fins, nous enfouissons un moteur de traitement de contraintes dans un assistant de recherche qui à chaque itération avec l'utilisateur, analyse les données, calcule des abstractions, des répartitions par clusters, des relaxations et retourne des alternatives à l'utilisateur, soit pour focaliser la recherche (en affinant sa requête par un ajout de contraintes), soit pour l'élargir (en relaxant sa requête pour une réouverture limitée d'un sous-ensemble de contraintes). Cette approche est complémentaire de celle des configurateurs : des algorithmes dirigés par les données (abstraction, clustering et relaxation) sont utilisés à la place d'algorithmes dirigés par la logique (propagation et recherche arborescente).
Searching objects within catalogs is a problem of increasing relevance, as the general public gains access to increasing volumes of data. Constraint Programming has adressed the case of searching databases of complex products that can be customized and build from components, through constraint-based configurators. We address the issue of searching objects within another kind of databases, namely catalogs of simpler items for which no logic description is available. We propose to embed constraint technology in a search assistant supporting dynamic and concise dialogs based on the exchange of constraint formulations between the client and the server. At each iteration, the server analyses the data available in the catalog, computes abstractions, cluster decompositions and relaxations in order to provide the user with alternative for either explicitly focusing the search (adding constraints to the user's wish) or enlarging it (relaxing, to some extent, a subset of the user's constraints). Our approach complements, within the framework of constraint processing, the configuration approach to catalog exploration: configurators use logic-based algorithms (propagation and search) to guide the search through complex catalogs, we use data-driven algorithms (abstraction, clustering and relaxation) to navigate through simpler ones.
programmation par contraintes, configuration, abstraction, relaxation.
constraint programming, configuration, abstraction, relaxation.
Français
|
