A b s t r a c t Objective: To model the temporal information contained in medical narrative reports as a simple temporal constraint satisfaction problem. Design: A constraint satisfaction problem is defined by time points and constraints (inequalities between points). A time interval comprises a pair of points and a constraint. Five complete electronic discharge summaries and paragraphs from 226 other discharge summaries were studied. Medical events were represented as intervals, and assertions about events were represented as constraints. Through a consensus process, a set of encoding procedures and a list of issues related to encoding were generated. Measurements: Instances of temporal disjunction and contradiction and distribution of temporal constraints were used. Results: An average of 95 medical events (range, 46-151) and 234 temporal assertions (range, 118-388) were identified per complete discharge summary. Nondefinitional assertions were explicit (36%) or implicit (64%) and absolute (17%), qualitative (72%), or metric (11%). Implicit assertions were based on domain knowledge and assumptions, e.g., the section of the report determined the ordering of events. Issues included linking events, intermittence, periodicity, granularity, vagueness, ambiguity, uncertainty, and plans. Abstractions such as intermittence were not represented explicitly. The temporal network was sparse: Only 0.80% (range, 0.42%-1.38%) of possible constraints were instantiated. No instances of discontinuous temporal disjunction were found in the complete summaries or the 226 paragraphs. One instance of temporal contradiction was found (intrareport rate of 0.2 with a 95% confidence interval of 0.005-1.114). A simple temporal constraint satisfaction problem appears sufficient to represent most temporal assertions in discharge summaries and may be useful for encoding electronic medical records. The electronic medical record is a temporally rich document filled with assertions about the timing of medical events, such as visits, laboratory values, symptoms, signs, diagnoses, and procedures. Allen, 1 in his review of temporal formalisms, describes how such temporal information can be specified with the use of points anchored in absolute time, qualitative constraints among intervals, and metric relations that specify explicit durations between points. Using such formalisms, past researchers in medical informatics have attempted to model temporal assertions found in the electronic medical record. 2-4 The expressiveness of these methods has not been tested with data from actual medical reports, however. Determining and validating a suitable temporal formalism for the electronic medical record remain a challenge in medical informatics. Much of the work in temporal querying and temporal reasoning in medical informatics has used temporal formalisms based on points anchored in absolute time. 2,5-10 The available data in such work consist of discrete coded events with known times, such as visit information, laboratory test results, and medication administration logs. Typically, events are represented as points or pairs of points, in which each point is a time stamp stored in a database. The primary focus of this research has been on temporal abstraction: recognizing temporal patterns among the time stamps and determining what can be inferred medically based on the temporal semantics of the events. For example, given a series of hemoglobin tests that occur at discrete time points, one can infer the presence or absence of anemia, a condition that persists over time. Medical informatics researchers have used temporal intervals to support temporal abstraction and temporal querying. 3, 9, [11] [12] [13] [14] One method, called TNET 13 and designed for chemotherapy planning, used qualitative constraints among intervals to represent temporal relationships for stored data. Qualitative constraints can be defined by Allen's 15 interval relationships. One interval can occur before, meet, overlap, start, occur during, finish, or equal another interval. In addition to this set of relationships, one can create composite disjunctions. For example, a composite disjunction in a medical narrative may consist of an episode of chest pain that occurred before or after (but not during) an intensive care unit stay. Metric relations specify durations-or limits of durationbetween pairs of time points. 16 For example, it might be stated that chest pain began exactly two days before transfer to the intensive care unit or that it began at least two days before transfer. Temporal querying methods for clinical data 3, 7 have incorporated metric relations into extended representations of relational data, but these methods do not directly support metric relations in natural language statements. Johnson 17 and others have applied metric relations to temporal assertions found in narrative clinical reports, but the difficulty of natural language processing has limited its use. Recent strides in natural language processing are leading to increased need for something beyond absolute time points. Work on temporal formalisms for nonmedical data has demonstrated that the three types of temporal representations enumerated by Allen in his review could be unified as a general temporal constraint satisfaction problem. 18-20 Unfortunately, this work has shown that drawing conclusions from such representations is NP-hard. A subset of representations based on general temporal constraint satisfaction is known as a simple temporal constraint satisfaction problem or, more succinctly, a simple temporal problem. 18 It can be solved in polynomial time (n 3 ). A simple temporal problem supports points anchored in absolute time, metric relations among points, and primitive Allen interval relationships. It differs from a general temporal constraint satisfaction problem, however, because it does not support discontinuous temporal disjunction: It cannot represent something that occurred during one of two or more disconnected time intervals. Discontinuous temporal disjunction becomes important in planning, for example. It might be stipulated that a patient needs to go for two tests within a month, but they must not occur on the same day. One test must occur before or after but not during the other one. This set of events cannot be represented as a simple temporal problem. It is our belief that discontinuous temporal disjunction is not necessary to represent the vast majority of temporal assertions that are found in the electronic medical record and that a simple temporal problem will suffice. It is clear that time stamp data can be represented as a simple temporal problem, 18 but the temporal assertions found in narrative text are likely to be more complex. The goal of this study was to test the hypothesis that the temporal information commonly available in narrative clinical reports can be represented with a temporal formalism defined as a simple temporal problem. If this is true, then discrete time stamp data and metric assertions derived from narrative reports can be integrated into a single temporal representation, and a computationally feasible algorithm can be used to draw conclusions from this representation. Furthermore, recent discoveries about simple temporal problems, such as a new efficient algorithm for sparse networks, 21 can be applied to the electronic medical record.
Hripcsak et al. model temporal information as contraint satisfaction problem REF .
Model Formulation: Modeling Electronic Discharge Summaries as a Simple Temporal Constraint Satisfaction Problem
Journal of the American Medical Informatics Association : JAMIA
Journal of the American Medical Informatics Association : JAMIA
Computer Science Medicine Mathematics