Visualizations to Summarize Search Behavior

Ian S. Howell, Berthe Y. Choueiry, Hongfeng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we argue that metrics that assess the performance of backtrack search for solving a Constraint Satisfaction Problem should not be visualized and examined only at the end of search, but their evolution should be tracked throughout the search process in order to provide a more complete picture of the behavior of search. We describe a process that organizes search history by automatically recognizing qualitatively significant changes in the metrics that assess search performance. To this end, we introduce a criterion for quantifying change between two time instants and a summarization technique for organizing the history of search at controllable levels of abstraction. We validate our approach in the context of two algorithms for enforcing consistency: one that is activated by a surge of backtracking and the second that modifies the structure of the constraint graph. We also introduce a new visualization for exposing the behavior of variable ordering heuristics and validate its usefulness both as a standalone tool and when displayed alongside search history.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings
EditorsHelmut Simonis
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783030584740
StatePublished - 2020
Event26th International Conference on Principles and Practice of Constraint Programming, CP 2020 - Louvain-la-Neuve, Belgium
Duration: Sep 7 2020Sep 11 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12333 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th International Conference on Principles and Practice of Constraint Programming, CP 2020


  • Constraint Satisfaction
  • Search
  • Visualization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Visualizations to Summarize Search Behavior'. Together they form a unique fingerprint.

Cite this