A Formal Model for the Representation of Binary Temporal Relations in Healthcare Applications and an Efficient Algorithm for Logic-Based Temporal Subsumption Testing and Pattern Matching

ObjectivesImportant temporal relationships exist among pairs of medically relevant events stored in electronic health records (EHRs), such as "the infection began within two weeks after surgery". Queries for specific temporal patterns also appear in decision-support rules and data-analysis programs. The accurate matching of such patterns to the patient data in EHRs is critical to the effective performance of decision-support systems, statistical analysis programs, data-abstraction processes, digital phenotyping for machine-learning, and other applications. The correct classification of temporally-qualified concepts in biomedical terminologies and ontologies, such as SNOMED-CT, is also important to ensure the accuracy and completeness of these knowledge-based resources. MethodsIn this paper, we describe an expressive model to formally represent temporal relationships between pairs of events, including "Before", "During", "Within n days after", and "Within n hours before or m hours after, but not during". We also describe a novel logic-based algorithm to deduce whether one such relationship temporally matches (i.e., is subsumed by) another such relationship, which enables the querying of structured time-stamped patient data, the querying of semi-structured narrative patient data, and the classification of logically defined medical concepts. Our model assumes an interval-based notion of time and our algorithm implements a logic-based definition of subsumption. ResultsWe formally prove the correctness of the algorithm based on the properties of temporal intervals and the axioms of propositional logic. We also prove that the algorithm has computational complexity of constant-time (i.e., O(1)) with respect to the size of the database being queried or the knowledge base being classified. ConclusionThe novel model and algorithm described here for temporal representation and reasoning are sound and have the potential to facilitate temporal subsumption testing and pattern matching in a number of medical application domains. Empirical testing is needed to establish the full scope of useful applicability.