A Logic-based Temporal Cohort Discovery Engine: Algorithms, Indices, and Experimental Results on the National Sleep Research Resource Yan Huanga , Xiaojin Lia , Licong Cuia and Guo-Qiang Zhanga,∗ a University of Texas Health Science Center at Houston, Houston, TX, USA
ABSTRACT
Keywords: Rational Ensemble Logic Temporal logic Model checking Cohort discovery Secondary use of data Data management Sleep medicine National Sleep Research Resource Fractional cascading
Objective: Large sleep-study repositories contain rich time-stamped physiological annotations, but cohort discovery is still commonly implemented as ad hoc scripts or scalar-index filters. This limits reproducibility when inclusion criteria depend on precise temporal relationships among sleep stages, respiratory events, arousals, desaturations, and signal-derived features. We present a logic-based temporal cohort discovery engine that brings formal semantics, model checking, specialized indexing, and empirical evaluation into a unified biomedical informatics framework. Materials and Methods: We adopt Rational Ensemble Logic (QEL) as a densetime formal foundation for sleep-data querying and represent each annotated polysomnogram as a Biomedical Event Structure Temporal Model (BEST), a finite mapping from event labels to non-overlapping rational interval ensembles. Cohort discovery is formulated as model checking of QEL formulas over BEST databases. We organize common sleep-research requirements into three reusable temporal query patterns: single-event retrieval, dual-event temporal pattern matching, and event data extraction. To make model checking practical at repository scale, we introduce two indexing strategies: 2-Dimensional Fractional Cascading (2DFC) for intervaloverlap retrieval and Fully Connected Fractional Cascading (FCFC) for dual-event pattern matching. Results: The prototype cohort discovery engine was implemented in Python with in-memory and MongoDB-backed execution modes and evaluated on synthetic interval datasets containing up to 90 million intervals and on real-world National Sleep Research Resource annotations from the Cleveland Children’s Sleep and Health Study (CCSHS) containing 515 subjects, 202,587 intervals, 23 event labels. 2DFC constructs indexes in linear space and linear build time, reducing build time at 90 million intervals from 11,549 s with RTFC and 23,902 s with 2DRT to 3,655 s. FCFC replaces repeated flatten-sort-scan operations with precomputed boundary-distance arrays and reduced RAM query time by 80-98% in dual-event experiments; MongoDB experiments showed approximately 50% reduction for high-candidate workloads. On CCSHS, cohort-selection queries executed at sub-second latency at native scale and under 45 s at 1,000× scale. Conclusion: QEL, BEST, and model checking provide mathematically explicit semantics for temporal sleep phenotypes that are both human-readable and machine-computable, while 2DFC and FCFC demonstrate that formal temporal cohort discovery can be executed efficiently on large biomedical data repositories. The resulting framework supports reusable, explainable cohort definitions aligned with sleep-medicine scoring rules and secondary use of polysomnography data. This work is a part of the “Symbolic Biomedicine” program championed by the corresponding author.
arXiv:2607.21377v1 [cs.DB] 23 Jul 2026
ARTICLE INFO
1. Introduction
Sleep medicine is a data-intensive domain in which clinically meaningful phenotypes are often temporal rather than purely scalar. A polysomnogram (PSG) records multi-channel physiological time series over an overnight study and is accompanied by annotations for sleep stages, respiratory events, oxygen desaturations, arousals, limb movements, artifacts, and other scored events. Large repositories such as the National Sleep Research Resource (NSRR Zhang, Cui, Mueller, Tao, Kim, Rueschman, Mariani, Mobley and Redline (2018)) make these recordings available for secondary use, but the dominant cohort-discovery workflow remains a mixture of summary indices, spreadsheet filters, and custom scripts. These approaches are effective for simple variables such as apnea-hypopnea index (AHI) or oxygen desaturation ∗ Corresponding author
[email protected] (Y. Huang); [email protected] (X. Li); [email protected] (L. Cui); [email protected] (G. Zhang) ORCID (s):
Huang et al.: Preprint submitted to Elsevier
Page 1 of 19
index (ODI), yet they are poorly suited for cohort definitions whose meaning depends on metric temporal relationships: an apnea occurring during N3 sleep, a desaturation beginning within a specified delay after a respiratory event, an arousal overlapping the termination of a hypopnea, or the absence of confounding events during a washout window. This gap is a biomedical informatics problem. Cohort criteria represent computational phenotype definitions; therefore, temporal criteria should be explicit, reusable, and expressed in a format that is both easily readable by humans and computable by machines. In sleep research, however, temporal logic is rarely treated as a first-class representation. The American Academy of Sleep Medicine (AASM) Scoring Manual Berry, Brooks, Gamaldo, Harding, Lloyd, Marcus and Vaughn (2015); Berry, Budhiraja, Gottlieb, Gozal, Iber, Kapur, Marcus, Mehra, Parthasarathy, Quan et al. (2012) rules and study protocols routinely specify duration thresholds, temporal windows, co-occurrence constraints, precedence relationships, and exclusion intervals, but these semantics are often buried inside analysis code. As a result, two investigators can intend the same clinical definition but obtain different cohorts because of different event anchoring conventions, boundary handling, or delay-window assumptions. This problem is amplified in multi-study repositories where data are reused long after the original scoring context. We address this problem by developing a logic-based temporal cohort discovery engine for interval-annotated PSG data. The central idea is to formulate cohort discovery as a model-checking task. Each annotated sleep study is represented as a Biomedical Event Structure Temporal Model (BEST), in which every event label is mapped to the finite set of rational intervals during which the event holds. Cohort criteria are written as formulas in Rational Ensemble Logic (QEL Zhang, Hao, Huang, Li and Cui (2026)), a dense-time temporal logic in the Ensemble Logic spectrum proposed in Zhang (2024) combining first-order quantification, displacement, bounded existence, bounded universality, and Boolean composition in a single framework. A subject belongs to a cohort exactly when the corresponding BEST satisfies the QEL formula at the specified observation point. This gives cohort discovery a precise mathematical semantics and turns temporal phenotype definitions into reusable symbolic artifacts. The paper brings together five contributions. First, we adopt QEL as a formal foundation for cohort discovery over sleep data, including PSG annotations and signal-derived physiological event intervals. This provides a single logical language for event labels, duration thresholds, bounded temporal windows, and absence constraints. Second, we formulate temporal cohort discovery under the model-checking paradigm by representing annotated PSG recordings as BESTs and by defining query answers as satisfaction sets and temporal-pattern witnesses. Third, we introduce two index strategies that exploit the normalized structure of sleep annotation data: 2-Dimensional Fractional Cascading (2DFC), which accelerates interval-overlap retrieval with linear-space construction, and Fully Connected Fractional Cascading (FCFC), which accelerates dual-event temporal pattern matching through constant-time target-event lookup after preprocessing. Fourth, we implement these ideas in a cohort discovery engine and evaluate the engine on both synthetic datasets and real-world NSRR annotations, including synthetic workloads with up to 90 million intervals and Cleveland Children’s Sleep and Health Study (CCSHS) annotations from 515 subjects with 1,000 cohort-query runs and scaled repository experiments. Fifth, we organize sleep-research queries into three temporal query patternssingle-event retrieval, dual-event temporal pattern matching, and event data extraction-that can express practical cohort specifications and rule-like definitions aligned with AASM scoring concepts. The resulting contribution is not merely a faster interval query algorithm or a new cohort-selection interface. It is an integrated approach that combines mathematical semantics, temporal data representation, model-checking execution, index design, and empirical evaluation for a concrete biomedical repository setting. To our knowledge, no prior biomedical informatics system has combined these components for temporal sleep cohort discovery in a single framework.
Huang et al.: Preprint submitted to Elsevier
Page 2 of 19
Statement of Significance. Problem or Issue
What is Already Known
What this Paper Adds
Who Would Benefit
Temporal relationships are central to sleep medicine, but they are rarely represented as explicit, reusable, and executable cohort definitions; existing analyses rely on scalar indices, event-pairing heuristics, or study-specific scripts that obscure clinical semantics and limit cross-cohort reproducibility. Sleep repositories such as NSRR store richly annotated interval-based PSG recordings. Temporal database and event-stream systems support useful query operations, yet none provides formally grounded semantics for sleep phenotype definitions that are simultaneously human-readable and machine-computable, nor indexing structures that exploit the sorted, non-overlapping structure of per-label annotation ensembles. We introduce a QEL/BEST model-checking framework for reproducible temporal cohort discovery over large sleep archives. QEL supplies a dense-time language for temporal phenotypes; BEST supplies a repository-ready representation of annotated PSGs; and 2DFC/FCFC supply scalable indexing that makes clinically meaningful criteria, including duration thresholds, event co-occurrence, bounded delay, stage restrictions, and signal-level event definitions, available as computational phenotypes that are both human-readable and directly machine-executable. Sleep researchers, clinical investigators, data scientists, biomedical informaticists, and platform teams are building cohort-discovery and data-sharing services for secondary use of PSG and other real-world physiological data.
2. Related Work 2.1. Temporal Reasoning on Sleep Data Sleep study data combine continuous physiological signals with time-stamped clinical annotations at distinct time scales. Table 1 lists annotation event types from the CCSHS Rosen, Larkin, Kirchner, Emancipator, Bivins, Surovec, Martin and Redline (2003). Sleep stages (N1/N2/N3/REM/WAKE) are scored in fixed 30 s epochs; respiratory events, arousals, SpO2 desaturations, and limb movements are interval events with onsets and offsets Berry et al. (2015). Temporal reasoning over these annotations captures co-occurrence, precedence, and recurrence with more precision than scalar indices (AHI, ODI, arousal index Tsai, Flemons, Whitelaw, Remmers and Brant (1999); Chung, Liao, Elsaid, Islam, Shapiro and Sun (2012); American Sleep Disorders Association (1992)). Many clinically meaningful relationships are defined by timing: hypopneas require associated desaturation or arousal within a specified window Berry et al. (2015), and arousals cluster near the termination of obstructive events American Sleep Disorders Association (1992). Without explicit temporal operators, such relationships rely on ad-hoc event-pairing heuristics that vary across labs and limit reproducibility across cohorts.
2.2. Common Absolute and Relative Period Windows Used in Sleep Studies Sleep studies operationalize temporal structure via period windows. Absolute windows align to clock-time bands (e.g., 00:00-03:00) Malicki, Karuga, Szmyd, Sochal and Gabryelska (2022); Chen, Redline, Eden and Prerau (2022) or fixed post-lights-off/pre-awakening intervals, computing window-normalized event rates (AHI, ODI, arousal index). Relative windows align to the sleep episode’s internal structure: SPT partitions for early-vs-late contrasts, or stageconstrained windows (REM vs. NREM) for stage-specific burdens and phenotyping Mokhlesi (2012); Yamauchi, Fujita, Kumamoto, Yoshikawa, Ohnishi, Nakano, Inoue and Tamaki (2015). All require explicit choices about anchoring, inclusion rules, and artifact handling for cross-cohort comparability Berry et al. (2015).
2.3. Temporal Queries for Sleep Study Data Recurring temporal query patterns in sleep research include precedence, overlap, bounded delay, and stagespecific constraints. Hypoxic burden Azarbarzin, Sands, Stone, Taranto-Montemurro, Messineo, Terrill, Ancoli-Israel, Ensrud, Purcell, White and Redline (2019) moves toward an explicit temporal view but remains study-specific. Key complicating factors, pulse-oximetry delay, epoch-boundary effects, and inter-scorer variability, require queries to encode explicit lags, overlap criteria, and recovery definitions.
Huang et al.: Preprint submitted to Elsevier
Page 3 of 19
Label ARASDA_C3 SPO2_ART SPO2_DESAT N2 HYPOP WAKE N3 N1 LM_RL1 LM_LL1 REM LM_RL LM_LL PLM_RL PLM_LL PLM_RL1 CA ARASDA_C4 PLM_LL1 OA
Type Arousals Respiratory Respiratory Stages Respiratory Stages Stages Stages Limb Movement Limb Movement Stages Limb Movement Limb Movement Limb Movement Limb Movement Limb Movement Respiratory Arousals Limb Movement Respiratory
Concept ASDA arousal SpO2 artifact SpO2 desaturation Stage 2 sleep Hypopnea Wake Stage 3 sleep Stage 1 sleep Limb movement - right Limb movement - left REM sleep Limb movement - right Limb movement - left Periodic leg movement - right Periodic leg movement - left Periodic leg movement - right Central apnea ASDA arousal Periodic leg movement - left Obstructive apnea
Signal Location C3 SpO2 SpO2 N/A Airflow N/A N/A N/A Right Leg1 Left Leg1 N/A R Leg L Leg R Leg L Leg Right Leg1 Airflow C4 Left Leg1 Airflow
# of Event 42,455 36,866 31,382 18,000 13,359 13,167 8,530 8,266 5,575 5,026 4,235 3,585 3,453 1,456 1,365 1,071 1,024 862 776 657
Table 1 Sleep event annotations with short names in CCSHS.
2.4. Existing Temporal Query Systems Systems like STAR Özçep, Möller and Neuenstadt (2014), T-SQL Microsoft Corporation (2016), and KarmaLego Moskovitch and Shahar (2015) incorporate temporal operators or pattern mining over symbolic time intervals; sleep research typically relies on custom scripts. The SQL:2016 MATCH_RECOGNIZE clause ISO/IEC 9075-2:2016 (2016) and CEP engines (Esper EsperTech Inc. (2024), Apache Flink Carbone, Katsifodimos, Ewen, Markl, Haridi and Tzoumas (2015)) apply NFA-based pattern matching over event streams. Automata-based methods require flattening concurrent interval streams into a single sorted sequence, lack metric temporal operators, and cannot exploit the nonoverlapping sorted structure of BEST. Our 2DFC and FCFC algorithms address these limitations directly.
3. Methods The formal development adopts Rational Ensemble Logic over the rational timeline and specializes it to intervalannotated PSG records. The resulting workflow has four layers: (i) raw XML annotations are normalized into labeled intervals; (ii) each subject is represented as a BEST; (iii) QEL formulas define query and cohort criteria; and (iv) model-checking results are accelerated by 2DFC and FCFC indexes. Figure 1 illustrates the overall pipeline.
3.1. BEST for QEL over rational time Intervals and interval ensembles. Following the QEL Zhang et al. (2026) framework, the time domain is the rational line. For sleep data we use the non-negative rational timeline ℚ≥0 because PSG annotation onsets and durations are stored as finite decimal or sampled quantities on a timeline starting at zero. An interval is denoted by [(𝑠, 𝑡)] and defined as [(𝑠, 𝑡)] = {𝑧 ∈ ℚ≥0 ∣ 𝑠 ⪯ 𝑧 ≪ 𝑡}, where 𝑠, 𝑡 ∈ ℚ≥0 with 𝑠 ≤ 𝑡, and the boundary relations ⪯ and ≪ are instantiated by < or ≤ to represent open, closed, left-closed right-open, and left-open right-closed intervals. A single time point is represented by the degenerate closed interval [𝑠, 𝑠]. Definition 1 (Interval ensemble). An interval ensemble 𝛿 is a finite set of non-empty, pairwise non-overlapping intervals over ℚ≥0 . We write IE for the set of all interval ensembles over ℚ≥0 . In a normalized PSG representation, Huang et al.: Preprint submitted to Elsevier
Page 4 of 19
Central Apnea in Stage 3 Sleep during Day2 5am-6am?
[{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...]
BEST-DB
[{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...] [{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...]
... [{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...]
1800448
[{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...] [{Central Apnea:(xxx,xxx), Stage 3 Sleep:(xxx,xxx)}, ...]
BEST of Subject 1800448 1800448
Annotations
Annotation File
Interval Ensembles
Wake Stage 1 Sleep Stage 2 Sleep Stage 3 Sleep REM Sleep Central Apnea Day 2 05:00:00
Day 2 06:00:00
XML ... <ScoredEvent> <EventType> Respiratory|Respiratory </EventType> <EventConcept> Central apnea|Central Apnea </EventConcept> <Start> 27437.2 </Start> <Duration> 12 </Duration> <SignalLocation> AIRFLOW </SignalLocation> </ScoredEvent> ...
Figure 1: Overview of the BEST-DB framework. A “Central Apnea” annotation from NSRR XML is transformed into a labeled interval, inserted into the subject-specific BEST, and evaluated by QEL model checking. Query execution returns matching subjects and, when requested, the witnessing intervals that certify the temporal pattern.
intervals in each ensemble are ordered by start time, and points not contained in the union of the intervals are treated under a closed-world assumption as times at which the corresponding label is absent. Labeled interval ensembles. Let 𝖯 be the finite set of PSG event labels used as atomic propositions, such as 𝖯 = {N3, REM, HYPOP, SPO2_DESAT, ARASDA_C3, CA, 𝑎𝑛𝑑OA}. A labeled interval ensemble (𝓁, 𝛿) pairs 𝓁 ∈ 𝖯 with all intervals during which the label holds for a given subject or recording. For example, (N3, 𝛿𝑛3 ) collects the Stage-3 sleep intervals in one timeline. Definition 2 (BEST and BEST-DB Zhang et al. (2026)). A Biomedical Event Structure Temporal Model (BEST) is a function 𝜀 ∶ 𝖯 → IE. Thus 𝜀(𝓁) is the interval ensemble in which label 𝓁 holds. A pair (𝓁, 𝜀(𝓁)) is a labeled interval ensemble representing a temporal event of 𝓁. By convention, labels mapped to the empty interval ensemble are omitted from the displayed graph of 𝜀, so a BEST may be written as a finite set of non-empty labeled interval ensembles. A BEST-DB 𝐷 is a finite collection of subject-level or session-level BESTs: 𝐷 = {𝜀1 , 𝜀2 , … , 𝜀𝑚 }.
3.2. QEL syntax and BEST semantics We now restate the QEL syntax used by the application. Point terms over ℚ≥0 are generated by constants, variables, and finite addition: 𝑢, 𝑣 ∶∶= 𝑎 ∣ 𝑥 ∣ 𝑢 + 𝑣,
𝑎 ∈ ℚ≥0 .
Window or norm terms are positive rational-valued terms generated by positive constants, variables, absolute values of point terms, and finite addition: 𝑠, 𝑡 ∶∶= 𝑐 ∣ 𝑧 ∣ ‖𝑢‖ ∣ 𝑠 + 𝑡,
𝑐 ∈ ℚ+ .
Huang et al.: Preprint submitted to Elsevier
Page 5 of 19
For the sleep-query templates below, most window terms are constants or quantified duration variables; constrained quantifier notation such as ∃𝑥 ∈ [0, 𝑟) is used as a readable abbreviation for restricting the assignment of 𝑥 to that rational interval. Definition 3 (QEL formula syntax Zhang et al. (2026)). QEL formulas are generated by 𝜑, 𝜓 ∶∶= 𝑝 ∣ 𝜑𝑢 ∣ ¬𝜑 ∣ 𝜑 ∧ 𝜓 ∣ 𝜑 ∨ 𝜓 ∣ □𝑡 𝜑 ∣ ◊𝑡 𝜑 ∣ ∃𝑥 𝜑 ∣ ∀𝑥 𝜑, where 𝑝 ∈ 𝖯 is an atomic event label, 𝜑𝑢 is exact displacement by point term 𝑢, ◊𝑡 𝜑 is bounded existence within the future window of length 𝑡, □𝑡 𝜑 is bounded universality throughout that window, and quantified variables range over rational time or positive rational window lengths as appropriate. Definition 4 (BEST satisfaction for QEL Zhang et al. (2026)). Let 𝜀 be a BEST and 𝑠 ∈ ℚ≥0 be a time point. The satisfaction relation (𝜀, 𝑠) ⊧ 𝜑 is defined inductively by the Boolean clauses of first-order logic and by the following QEL clauses: ⋃ (𝜀, 𝑠) ⊧ 𝑝 iff 𝑠 ∈ 𝜀(𝑝), (𝜀, 𝑠) ⊧ 𝜑𝑢
iff (𝜀, 𝑠 + 𝑢) ⊧ 𝜑,
(𝜀, 𝑠) ⊧ ◊𝑡 𝜑
iff there exists 𝑟 ∈ ℚ≥0 with 0 ≤ 𝑟 < 𝑡 and (𝜀, 𝑠 + 𝑟) ⊧ 𝜑,
(𝜀, 𝑠) ⊧ □𝑡 𝜑
iff for all 𝑟 ∈ ℚ≥0 with 0 ≤ 𝑟 < 𝑡, (𝜀, 𝑠 + 𝑟) ⊧ 𝜑,
(𝜀, 𝑠) ⊧ ∃𝑥 𝜑
iff there exists 𝑎 ∈ ℚ≥0 such that (𝜀, 𝑠) ⊧ 𝜑[𝑥 ↦ 𝑎],
(𝜀, 𝑠) ⊧ ∀𝑥 𝜑
iff for all 𝑎 ∈ ℚ≥0 , (𝜀, 𝑠) ⊧ 𝜑[𝑥 ↦ 𝑎].
For positive duration variables 𝑧, the existential and universal clauses range over ℚ+ . This is the future-directed QEL semantics specialized to PSG records.
3.3. Model checking and temporal query answers A temporal query is a QEL formula evaluated against every BEST in a database. The answer set is [[𝜑𝑞 ]]𝐷 = {𝜀 ∈ 𝐷 ∣ (𝜀, 𝑞) ⊧ 𝜑}. Equivalently, using the QEL displacement convention, 𝜀 ⊧ 𝜑𝑞 abbreviates satisfaction of 𝜑 at observation point 𝑞. A standard QEL query formula 𝜑 with an observation point 𝑞 follows the structure: 𝜑𝑞 ∶= (𝜓𝑡1 ∧ 𝜓𝑡2 ∧ ⋯ ∧ 𝜓𝑡𝑘 )𝑞 where: 1. Prefix Part : This optional part consists of quantifiers (∀, ∃) that declare time-distance variables used in the formula. If no variables are needed, this part is empty. The prefix scopes over the entire subsequent formula. 2. Core Part 𝜓𝑡𝑖 : The core consists of one or more sub-formulas connected by logical AND (∧). Each sub-formula 𝜓𝑡𝑖 is constructed from a set of atomic event annotations (labels) using one of the following operators: 𝐴𝑡 = {𝑥 ∣ 𝑥 + 𝑡 ∈ 𝐴},
◊𝑟 𝐴 = {𝑥 ∣ (𝑥 + [0, 𝑟)) ∩ 𝐴 ≠ ∅},
□𝑟 𝐴 = {𝑥 ∣ 𝑥 + [0, 𝑟) ⊆ 𝐴}.
The subscript 𝑡𝑖 denotes the temporal shift of the 𝑖-th sub-formula, meaning the condition is evaluated at time 𝑞 + 𝑡𝑖 . This allows correlating events at different relative times. Negation(¬) can be added to the atomic event annotations within 𝜓𝑡𝑖 , and they are connected using logical AND (∧) and OR (∨) as needed. (
)
Example. The query ∀𝑥∈{1, 2, 3} ∃𝑦∈[0, 5] (𝜑 ∧ 𝜑′ )𝑥 ∧ (□𝑦 (𝜓 ∨ ¬𝜓 ′ ))3 ∧ (◊5 (¬𝜒 ∧ 𝜒 ′ ))7 10 can be interpreted as: “For all 𝑥 ∈ {1, 2, 3}, there exists 𝑦 ∈ [0, 5] such that at time 10+𝑥 both 𝜑 and 𝜑′ occur; at time 13 event 𝜓 holds and 𝜓 ′ is absent for 𝑦 units; and at time 17 within a 5-unit window 𝜒 is absent at some point while 𝜒 ′ occurs.”
Definition 5 (Temporal pattern witness). Let 𝜀 ⊧ 𝜑𝑞 . A temporal pattern witness 𝜋 is a finite, set-minimal collection of positive labeled intervals and, when negation is used, negative gap intervals from complements of labeled ensembles, sufficient to certify the truth of 𝜑𝑞 in 𝜀. The query result may return only the matching BESTs, one witness per BEST, or all witnesses, denoted respectively by [[𝜑𝑞 ]]𝐷 , [[𝜑𝑞 ]]1𝐷 , and [[𝜑𝑞 ]]∗𝐷 . Huang et al.: Preprint submitted to Elsevier
Page 6 of 19
3.4. Indexing for Labeled Interval Ensembles The QEL semantics is defined over dense rational time, but each BEST contains only finitely many annotation intervals. This finiteness allows model checking to be reduced to finite evidence sets. The general QEL result uses quantifier elimination for dense ordered divisible abelian groups: after fixing a BEST, a reference point, and a formula, the satisfying assignments of rational variables decompose into finitely many linear cells, and it is sufficient to test one rational representative from each cell. Theorem 1 (Finite rational evidence set for QEL Zhang et al. (2026)). Fix a BEST 𝜀, a reference point 𝑞 ∈ ℚ≥0 , and a QEL formula 𝜑[𝐱] with free rational variables 𝐱 = (𝑥1 , … , 𝑥𝑛 ). There exists a finite set 𝐹𝜀,𝑞,𝜑 ⊆ (ℚ≥0 )𝑛 , computable from the interval endpoints in 𝜀, the rational constants in 𝜑, the reference point 𝑞, and the affine boundaries induced by displacements and modal windows, such that (𝜀, 𝑞) ⊧ ∃𝐱 𝜑[𝐱] ⟺ ∃𝐚 ∈ 𝐹𝜀,𝑞,𝜑 (𝜀, 𝑞) ⊧ 𝜑[𝐚], (𝜀, 𝑞) ⊧ ∀𝐱 𝜑[𝐱] ⟺ ∀𝐚 ∈ 𝐹𝜀,𝑞,𝜑 (𝜀, 𝑞) ⊧ 𝜑[𝐚]. For the one-dimensional window queries used by the application, this finite set specializes to representatives of endpoint-induced segments and their bounding faces. See Zhang et al. (2026). For a fixed BEST, every atomic proposition is a finite union of rational intervals. QEL uses only addition, order, rational constants, displacement, and future-window existential or universal quantification. These clauses can be translated into the first-order theory of dense ordered divisible abelian groups, which admits quantifier elimination. The resulting quantifier-free formula is a Boolean combination of linear inequalities with rational constants, producing a finite cell decomposition. Truth is constant on each cell and face, so one rational representative per cell is complete for existential and universal model checking. In the implementation, endpoint representatives are encoded as integer segment identifiers whenever the query contains only the bounded temporal templates in Section 3.5. Thus the finite-evidence theorem justifies the engineering reduction from dense rational time to endpoint arrays; the reduction is a semantic consequence of QEL, not merely an optimization.
3.5. Temporal Query Template We present standard QEL query templates for cohort extraction and pattern discovery. Let 𝓁 denote an event label, 𝓁 ∗ a wildcard label ranging over the event vocabulary, 𝑞 ∈ ℚ≥0 an observation point, 𝑟 ∈ ℚ+ a duration, and 𝑚 the maximum duration of the recording. Cohort selection queries return matching BESTs; pattern extraction queries additionally return witnesses.
Single-event queries. These queries support direct data discovery and reusable feature extraction. • Anywhere on the timeline: (◊𝑚 𝓁)0 . • Within [𝑞, 𝑞 + 𝑟): (◊𝑟 𝓁)𝑞 . ( ) • Starting within [𝑞, 𝑞 + 𝑟): ∃𝑥 ∈ [0, 𝑟) (□𝑥 ¬𝓁) ∧ 𝓁𝑥 𝑞 .
Dual-event queries. These queries support phenotype definitions that depend on co-occurrence, precedence, and bounded delay between labels 𝓁𝐴 and 𝓁𝐵 .
• Co-occurrence: event 𝓁𝐴 overlaps event 𝓁𝐵 somewhere on the timeline: ( ) ◊𝑚 (𝓁𝐴 ∧ 𝓁𝐵 ) 0 . • Before variant 1 (entire A before B): ( ( ) ( ) ) ∃𝑞∃𝑥∃𝑦 □𝑥 ¬𝓁𝐴 ∧ □𝑦 (𝓁𝐴 ∧ ¬𝓁𝐵 ) 𝑥 ∧ (¬𝓁𝐴 )𝑥+𝑦 ∧ ◊𝑚 𝓁𝐵 𝑥+𝑦
𝑞
Huang et al.: Preprint submitted to Elsevier
Page 7 of 19
• Before variant 2 (A starts before B): ) ( ( ) ∃𝑞∃𝑥∃𝑦 □𝑥 ¬𝓁𝐴 ∧ □𝑦 (𝓁𝐴 ∧ ¬𝓁𝐵 ) 𝑥 ∧ (◊𝑚 𝓁𝐵 )𝑥+𝑦
𝑞
• Before variant 3 (A ends before B): ( ) ∃𝑞∃𝑥 □𝑥 (𝓁𝐴 ∧ ¬𝓁𝐵 ) ∧ (¬𝓁𝐴 )𝑥 ∧ (◊𝑚 𝓁𝐵 )𝑥
𝑞
• Before variant 4 (moment of A before B): ( ( ) ( ) ) ∃𝑞∃𝑥 □𝑥 𝓁𝐴 ∧ ¬𝓁𝐵 ∧ ◊𝑚 𝓁𝐵 𝑥
𝑞
The variants deliberately separate stricter interval precedence from weaker pointwise precedence, making the clinical meaning of a query explicit.
Event data extraction. These templates support data-management tasks in which matching event instances, not only matching subjects, are returned.
• Clock-anchored existence: any label 𝓁 ∗ in [𝑞, 𝑞 + 𝑟): (◊𝑟 𝓁 ∗ )𝑞 . ( ) • Event-anchored existence: 𝓁 co-occurs with any label 𝓁 ∗ : ◊𝑚 (𝓁 ∧ 𝓁 ∗ ) 0 .
( ) • Event-anchored universality: 𝓁 co-occurs with 𝓁 ∗ throughout a required window: □𝑚 (𝓁 ∧ 𝓁 ∗ ) 0 .
3.6. Algorithms for Efficient Query Execution We deploy two structures under the QEL model-checking layer: 2DFC for single-event and extraction queries, where the task is fast interval retrieval within a window, and FCFC for dual-event pattern queries, where the task is fast temporal-distance lookup across heterogeneous event timelines.
3.6.1. From Temporal Queries to Range Queries Because each interval [𝑥, 𝑦] can be treated as a point (𝑥, 𝑦) in 2D, a QEL existence query over a window [𝑥′ , 𝑦′ ] reduces to a 2D range query: find all intervals whose start is not after the query end and whose end is not before the query start, i.e., all (𝑥, 𝑦) with 𝑥 ≤ 𝑦′ and 𝑦 ≥ 𝑥′ . The baseline structure 2DRT Bentley and Saxe (1980); Lueker (1978) answers this in 𝑂(log2 𝑛 + 𝑘) with 𝑂(𝑛 log 𝑛) space; RTFC Mao, Eran and Luo (2019) improves query time to 𝑂(log 𝑛 + 𝑘) via fractional cascading Chazelle and Guibas (1986) at the same space cost. Because BEST intervals are pre-sorted and non-overlapping, 2DFC eliminates the preprocessing overhead of these general structures. 3.6.2. 2-Dimensional Fractional Cascading for Intervals (2DFC) Given 𝑚 sorted non-overlapping interval lists with 𝑛 total intervals, 2DFC splits each list into a start-point list 𝐿𝑥𝓁 and an end-point list 𝐿𝑦𝓁 , then builds two 1DFC structures (𝐹 𝐶𝑥 , 𝐹 𝐶𝑦 ). Algorithm 1 details the construction. Proposition 1. Given a valid 2DFC structure over a set of non-overlapping interval ensembles, Algorithm 2 returns exactly the set of intervals [𝑥𝑖 , 𝑦𝑖 ] that overlap the query interval [𝑥′ , 𝑦′ ], equivalently those satisfying 𝑥𝑖 ≤ 𝑦′ and 𝑦𝑖 ≥ 𝑥′ . Thus 2DFC correctly solves the interval-overlap range query required by QEL bounded-existence extraction. The QEL query algorithm for an existence query using 2DFC is shown in Algorithm 2; Figure 2 illustrates the cascading pointer traversal on a worked example.
Complexity analysis. Leveraging the FC data structure, given a 2-dimensional query interval 𝑞 = [𝑥′ , 𝑦′ ] and a
dataset 𝐿 comprising 𝑚 sorted interval lists with a total of 𝑛 intervals, we can efficiently locate the position of 𝑥′ in every end-point list and the position of 𝑦′ in every start-point list. In Algorithm 2, the Q UERY1DFC procedure performs a single binary search on the augmented first list 𝐹 𝐶[0] and then cascades through the remaining 𝑚 − 1 lists in 𝑂(1) ∑ ∑ 𝑛𝑖 𝑛 𝑛 ≤ 𝑖≥1 𝑛𝑖 = 𝑛, the time per list. The size of 𝐹 𝐶[0] is bounded by |𝐹 𝐶[0]| ≤ 𝑛1 + 22 + 43 + ⋯. Since 𝑖≥2 2𝑖−1 total is at most 𝑛1 + 𝑛 ≤ 2𝑛, where 𝑛𝑖 denotes the number of intervals in the 𝑖-th list. When the lists are approximately Huang et al.: Preprint submitted to Elsevier
Page 8 of 19
Algorithm 1: Build 2DFC Input: The original 2D array of intervals 𝐿 Output: 2 1DFC data structures 𝐹 𝐶𝑥 and 𝐹 𝐶𝑦 1 Function Build2DFC(𝐿): 2 Initialize 𝐿𝑥 and 𝐿𝑦 ; 3 for 𝑖 ← 0 to |𝐿| − 1 do 4 foreach 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 in 𝐿[𝑖] do 5 Add 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙.𝑠𝑡𝑎𝑟𝑡 to 𝐿𝑥 [𝑖]; 6 Add 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙.𝑒𝑛𝑑 to 𝐿𝑦 [𝑖]; 7 8 9
Create 1DFC 𝐹 𝐶𝑥 for 𝐿𝑥 using the structure of (𝑑𝑎𝑡𝑎, 𝑖𝑛𝑑𝑒𝑥_𝑖𝑛_𝐿, 𝑝𝑜𝑖𝑛𝑡𝑒𝑟_𝑛𝑒𝑥𝑡); Create 1DFC 𝐹 𝐶𝑦 for 𝐿𝑦 using the structure of (𝑑𝑎𝑡𝑎, 𝑖𝑛𝑑𝑒𝑥_𝑖𝑛_𝐿, 𝑝𝑜𝑖𝑛𝑡𝑒𝑟_𝑛𝑒𝑥𝑡); return 𝐹 𝐶𝑥 , 𝐹 𝐶𝑦 ;
Algorithm 2: Existence query by 2DFC Input: 𝐿, 𝐹 𝐶𝑥 , 𝐹 𝐶𝑦 , 𝑞 = [𝑥′ , 𝑦′ ] Output: A list of intervals ′ ′ 1 Function Query2DFC(𝐿, 𝐹 𝐶𝑥 , 𝐹 𝐶𝑦 , 𝑥 , 𝑦 ): 2 Initialize 𝑅𝑒𝑠𝑢𝑙𝑡; 3 𝑠𝑡𝑎𝑟𝑡_𝑖𝑛𝑑𝑖𝑐𝑒𝑠 ← Query1DFC(𝐹 𝐶𝑦 , 𝑥′ ); 4 𝑒𝑛𝑑_𝑖𝑛𝑑𝑖𝑐𝑒𝑠 ← Query1DFC(𝐹 𝐶𝑥 , 𝑦′ ); 5 for 𝑖 ← 0 to |𝐿| − 1 do 6 for 𝑗 ← 𝑠𝑡𝑎𝑟𝑡_𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖] to 𝑒𝑛𝑑_𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖] do 7 if 𝐿[𝑖][𝑗].𝑠𝑡𝑎𝑟𝑡 ≤ 𝑦′ then 8 Add 𝐿[𝑖][𝑗] to 𝑅𝑒𝑠𝑢𝑙𝑡; 9
return 𝑅𝑒𝑠𝑢𝑙𝑡;
Function Query1DFC(𝐿, 𝐹 𝐶, 𝑥): Initialize 𝑅𝑒𝑠𝑢𝑙𝑡; 12 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 ← BinarySearch(𝐹 𝐶[0], 𝑥); 13 for 𝑖 ← 0 to |𝐹 𝐶| − 1 do 14 if 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 < 𝐹 𝐶[𝑖].𝑙𝑒𝑛𝑔𝑡ℎ then 15 𝑖𝑛𝑑𝑒𝑥_𝑖𝑛_𝐿 ← 𝐹 𝐶[𝑖][𝑝𝑜𝑖𝑛𝑡𝑒𝑟][1]; 16 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 ← 𝐹 𝐶[𝑖][𝑝𝑜𝑖𝑛𝑡𝑒𝑟][2];
10
11
17 18 19
else 𝑖𝑛𝑑𝑒𝑥_𝑖𝑛_𝐿 ← 𝐿[𝑖].𝑙𝑒𝑛𝑔𝑡ℎ; 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 ← 𝐹 𝐶[𝑖 + 1].𝑙𝑒𝑛𝑔𝑡ℎ;
21
if 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 > 0 and 𝐹 𝐶[𝑖 + 1][𝑝𝑜𝑖𝑛𝑡𝑒𝑟 − 1][0] ≤ 𝑥 then 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 ← 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 − 1;
22
Add 𝑖𝑛𝑑𝑒𝑥_𝑖𝑛_𝐿 to 𝑅𝑒𝑠𝑢𝑙𝑡;
20
23
return 𝑅𝑒𝑠𝑢𝑙𝑡;
balanced (i.e., 𝑛𝑖 ≈ 𝑛∕𝑚), we have |𝐹 𝐶[0]| ≤ 2𝑛∕𝑚 = 2𝑛1 , so the binary search takes 𝑂(log 𝑛1 ) time. In the general (unbalanced) case, |𝐹 𝐶[0]| can be as large as 𝑂(𝑛), making the binary search 𝑂(log 𝑛). Since the algorithm invokes Q UERY1DFC twice (once for start points, once for end points) and then scans the candidate intervals in 𝑂(𝑚 + 𝑘) time, the total query time is: 𝑂(log |𝐹 𝐶[0]| + 𝑚 + 𝑘), Huang et al.: Preprint submitted to Elsevier
Page 9 of 19
Original 2D interval array 𝐿[0]
1
𝐿[1]
2
7
16
42
45
67
71
1
9
32
32
55
56
58
66
𝐿[2]
2
10
19
29
93
99
𝐿[3]
6
12
31
32
38
46
56
63
𝐿[4]
16
20
32
38
47
51
51
52
72
75
81
81
Query: [40, 60] 2 16 29 45 46 66 71 75 FC𝑦 [0]
0 0
FC built bottom→top
FC𝑦 [1]
FC𝑦 [2]
FC𝑦 [3]
FC𝑦 [4]
1 1
2 1
2 3
3 3
3 5
3 6
1
7 19 38 42 58 67 72
4
Index in L
0
1
2
2
2
2
3
4
6
succ
0
1
1
3
4
5
6
6
9 29 32 46 56 66 99
1 19 32 38 55 58 93
0
1
1
2
2
3
4
0
1
1
2
2
3
4
0
1
1
3
4
5
5
0
1
3
3
4
5
5
10 29 32 46 63 99
2 19 31 38 56 93
0
1
2
2
2
2
0
1
2
2
2
2
0
1
1
3
5
6
0
1
1
1
1
2
12 32 38 46 52 63
6 31 32 38 51 56
0
1
2
2
3
3
0
1
2
2
3
3
0
1
1
2
3
4
0
1
1
2
3
4
20 38 51 52 81
16 32 47 51 81
0
1
2
3
4
0
1
2
3
4
0
0
0
0
0
0
0
0
0
0
FC𝑥 [0]
FC𝑥 [1]
FC𝑥 [2]
FC𝑥 [3]
FC𝑥 [4]
Figure 2: An example to illustrate the construction of 2DFC and the existence query with input interval [40, 60]. Extracted target ranges are navigated via pointers (boxes), triggering a localized scan (arrows), and matching intervals are returned (circles).
which is 𝑂(log 𝑛1 + 𝑚 + 𝑘) when the lists are balanced and 𝑂(log 𝑛 + 𝑚 + 𝑘) in the worst case. Here 𝑘 is the number of reported intervals. Compared to the 2DRT query time of 𝑂(log2 𝑛 + 𝑘) and the RTFC query time of 𝑂(log 𝑛 + 𝑘), 2DFC trades a small additive 𝑂(𝑚) term for a potentially reduced logarithmic factor. In typical sleep study datasets where 𝑚 ≪ 𝑛 (e.g., 𝑚 = 20 event types and 𝑛 > 200,000 intervals), the 𝑂(𝑚) term is negligible and 2DFC achieves competitive or superior query performance.
Space complexity. By the standard fractional cascading result Chazelle and Guibas (1986), the total number of elements across all lists in a single FC structure is at most 2𝑛. Since 2DFC constructs two independent FC structures (one for start points, one for end points), the total storage is at most 4𝑛 = 𝑂(𝑛). This is a significant improvement over both 2DRT and RTFC, which require 𝑂(𝑛 log 𝑛) space due to the replication of elements across 𝑂(log 𝑛) levels of the range tree.
3.6.3. Fully Connected Fractional Cascading for Pattern Matching (FCFC) While 2DFC is designed for efficient event data extraction, such as retrieving all events that occur within a given time window, pattern matching queries require a complementary strategy. In pattern matching, the goal is to identify temporal relationships (e.g., co-occurrence, precedence, bounded delay) between a specified anchor event and one or more target events across the entire timeline. This corresponds directly to the dual-event query templates defined in Section 3.5, such as the “Before” variants and “Co-occurrence” patterns. As discussed in Section 2, NFA-based approaches (e.g., MATCH_RECOGNIZE ISO/IEC 9075-2:2016 (2016)) require flattening concurrent interval streams into a single row sequence, lack first-class metric temporal operators, and do not exploit the non-overlapping BEST structure. To overcome these limitations, we introduce FCFC, which connects all Huang et al.: Preprint submitted to Elsevier
Page 10 of 19
interval boundaries to a global boundary index and precomputes event-specific successor arrays. The term “fractional cascading” in FCFC refers to this propagation of boundary positions through a fully connected global backbone, rather than the classical list-sampling structure used in 2DFC. The FCFC structure is built from the sorted, non-overlapping interval ensembles in a BEST. Let 𝐺𝑙𝑜𝑏𝑎𝑙 be the sorted set of all starts and ends across all event labels. For each label 𝑖 and each global boundary 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗], FCFC stores (i) the first interval of label 𝑖 whose start is not before 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗], supporting bounded-future and precedence tests, and (ii) the first interval of label 𝑖 whose end is after 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗], supporting overlap/co-occurrence tests. Because interval boundaries are also linked to their positions in 𝐺𝑙𝑜𝑏𝑎𝑙 during construction, a query can move from an anchor interval boundary to the relevant target-event candidate in 𝑂(1) time per target label. Algorithm 3: Build FCFC Input: The original 2D array of sorted, non-overlapping intervals 𝐿 Output: Global index array 𝐺𝑙𝑜𝑏𝑎𝑙, next-start arrays 𝑁𝑒𝑥𝑡𝑆𝑡𝑎𝑟𝑡, next-live arrays 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒, and boundary links 1 Function BuildFCFC(𝐿): 2 𝐺𝑙𝑜𝑏𝑎𝑙 ← Sort unique starts and ends across all lists in 𝐿; 3 𝑁𝑒𝑥𝑡𝑆𝑡𝑎𝑟𝑡 ← Empty array of size |𝐿| × |𝐺𝑙𝑜𝑏𝑎𝑙|; 4 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒 ← Empty array of size |𝐿| × |𝐺𝑙𝑜𝑏𝑎𝑙|; 5 for 𝑖 ← 0 to |𝐿| − 1 do 6 𝑠 ← 0; 𝑒 ← 0; 7 for 𝑗 ← 0 to |𝐺𝑙𝑜𝑏𝑎𝑙| − 1 do 8 while 𝑠 < |𝐿[𝑖]| and 𝐿[𝑖][𝑠].𝑠𝑡𝑎𝑟𝑡 < 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗] do 9 𝑠 ← 𝑠 + 1; 10 11 12 13 14 15
while 𝑒 < |𝐿[𝑖]| and 𝐿[𝑖][𝑒].𝑒𝑛𝑑 ≤ 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗] do 𝑒 ← 𝑒 + 1; 𝑁𝑒𝑥𝑡𝑆𝑡𝑎𝑟𝑡[𝑖][𝑗] ← 𝑠 ; 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒[𝑖][𝑗] ← 𝑒 ;
// first interval starting at or after 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗] // first interval ending after 𝐺𝑙𝑜𝑏𝑎𝑙[𝑗]
Link each interval boundary in 𝐿 to its index in 𝐺𝑙𝑜𝑏𝑎𝑙; return 𝐺𝑙𝑜𝑏𝑎𝑙, 𝑁𝑒𝑥𝑡𝑆𝑡𝑎𝑟𝑡, 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒;
Algorithm 4: Pattern Matching Query (Co-occurrence) by FCFC Input: Interval lists 𝐿, anchor event index 𝐴, target event index 𝑇 , global-index links, and 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒 Output: Intervals of 𝐴 overlapping at least one interval of 𝑇 1 Function QueryFCFC(𝐿, 𝐴, 𝑇 , 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒): 2 𝑅𝑒𝑠𝑢𝑙𝑡 ← Empty list; 3 foreach 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 in 𝐿[𝐴] do 4 𝑗 ← 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙.𝑔𝑙𝑜𝑏𝑎𝑙_𝑠𝑡𝑎𝑟𝑡_𝑖𝑑𝑥; 5 𝑐 ← 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒[𝑇 ][𝑗]; 6 if 𝑐 < |𝐿[𝑇 ]| and 𝐿[𝑇 ][𝑐].𝑠𝑡𝑎𝑟𝑡 < 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙.𝑒𝑛𝑑 then 7 Add 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 to 𝑅𝑒𝑠𝑢𝑙𝑡; 8
return 𝑅𝑒𝑠𝑢𝑙𝑡;
Proposition 2. Given a valid FCFC structure over normalized non-overlapping interval ensembles, Algorithm 4 returns exactly the anchor intervals of label 𝐴 that overlap at least one target interval of label 𝑇 . Proof sketch. For an anchor interval [𝑎, 𝑏), the FCFC lookup 𝑁𝑒𝑥𝑡𝐿𝑖𝑣𝑒[𝑇 ][𝑗] at the global position of 𝑎 returns the first target interval whose end is greater than 𝑎. All earlier target intervals end at or before 𝑎 and therefore cannot overlap Huang et al.: Preprint submitted to Elsevier
Page 11 of 19
𝐿[0]
[4, 8] [11, 14] [18, 22]
𝐿[1]
[1, 3] [5, 6] [13, 15] [19, 21]
𝐿[2]
[6, 9] [16, 17]
Index Time
0
1
2
3
4
5
6
7
1
3
4
5
6
7
8
9 11 13 14 15 16 17 18 19 21 22
𝐹 𝐶[0]
𝐹 𝐶[1]
9 10 11 12 13 14 15 16 17
4
8
11
14
18
22
2
6
8
10
14
17
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17
0
2
1
0
7
6
5
4
2
0
✓ 𝐹 𝐶[2]
8
0
4
3
✓
2
1
0
-1 -1
✓
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17
5
3
2
1
0
0
0
7
5
3
✓
×
2
1
0
-1 -1 -1 -1 -1
×
Figure 3: An example to illustrate the construction of FCFC and the query to find all “Co-occurrence” patterns between 𝐿[0] and 𝐿[1], and 𝐿[0] and 𝐿[2]
the anchor. If this first not-yet-ended target interval starts before 𝑏, then it overlaps [𝑎, 𝑏) and the anchor is returned. If it starts at or after 𝑏, then every later target interval starts no earlier and therefore also cannot overlap [𝑎, 𝑏). Thus the test is both sound and complete. Algorithms 3-4 implement the FCFC build and co-occurrence query; Figure 3 shows the construction and a worked example with three events and nine intervals.
Complexity analysis. Consider a dataset 𝐿 with 𝑚 event types and 𝑙 total intervals. The global index contains at most
2𝑙 boundary points. FCFC stores two index arrays per event type over this global boundary list, so the asymptotic storage is 𝑂(𝑚𝑙) and the construction time is 𝑂(𝑚𝑙) after the global boundary list has been sorted. For a pattern-matching query with 𝑎 anchor intervals and 𝑘 target event types, each anchor-target check is a constant-time lookup followed by one interval-boundary comparison. The query time is therefore 𝑂(𝑘𝑎), or 𝑂(𝑘𝑙∕𝑚) under a balanced-event assumption. In practice, choosing the rarest clinically relevant event as the anchor often decreases 𝑎 substantially. An NFA-style alternative that repeatedly flattens, sorts, and scans the relevant interval streams requires 𝑂(𝑙′ log 𝑙′ +𝑙′ ) time per query, where 𝑙′ is the number of intervals participating in the pattern. FCFC avoids this repeated flattening and sorting while preserving the interval semantics needed by the QEL/BEST model-checking layer.
4. Results 4.1. Implementation and Experimental Setup We implemented 2DFC and FCFC in Python 3.11 as execution components under the QEL/BEST model-checking layer. We also implemented 2DRT and RTFC for comparison. Build times for 2DRT and RTFC include the required flattening or restructuring of multi-stream input; 2DFC takes the raw sorted interval lists directly, exploiting the BEST invariant. FCFC precomputes event-distance arrays over a global boundary index. Persistent structures are backed by MongoDB for large-scale testing and deployment compatibility with NSRR-style data services.
4.2. Dataset Synthetic datasets consist of 𝑚 events with 𝑛′ non-overlapping intervals each, generated uniformly on [0, 200,000,000] with max length 100. Three dataset collections vary: (1) event count with constant intervals/event; (2) event count with constant total intervals; and (3) intervals/event with constant event count. CCSHS dataset within NSRR was used for real-world evaluation because it is a population-based pediatric cohort with standardized expert scoring, 23 event labels, and over 200k non-overlapping annotation intervals, providing rich sleep-stage, respiratory, desaturation, arousal, and limb-movement information suitable for QEL/BEST temporal Huang et al.: Preprint submitted to Elsevier
Page 12 of 19
Table 2 Data structure build time in seconds for 2DFC, RTFC, and 2DRT on different sizes of synthetic data. Num of Events 200 1,000 200 200 200
Total Num of Intervals 2,000,000 2,000,000 10,000,000 50,000,000 90,000,000
2DFC 20 19 116 1,205 3,655
RTFC 83 90 476 4,466 11,549
2DRT 49 51 295 3,475 23,902
phenotypes and the 2DFC/FCFC index structures. While all NSRR datasets share a common sleep data format and could in principle be queried by the same framework, they target different cohorts and study designs; adding multiple datasets would not substantively change the behavior of the temporal query patterns evaluated here and a single, well-characterized cohort is straightforward to scale up synthetically to stress-test performance without introducing additional cohort-specific variability.
4.3. 2DFC query performance We first evaluated the data structure build time of 2DFC compared to RTFC and 2DRT on synthetic datasets (Table 2). Because the interval lists in an annotated PSG are naturally pre-sorted (see Definition 1), 2DFC takes advantage of this property to build in linear 𝑂(𝑛) time and 𝑂(𝑛) space. In contrast, 2DRT and RTFC require 𝑂(𝑛 log 𝑛) time. Consequently, 2DFC represents the fastest indexing approach for datasets up to 50 million intervals; as datasets grow larger, RTFC gradually overtakes 2DRT while 2DFC remains significantly more efficient than both. To evaluate query execution scalability, we performed three experiments varying the event and interval characteristics of the data. Due to its slow execution speeds at scale, 2DRT was excluded from these tests. First, holding the number of intervals per event constant at 100,000 while increasing the event count from 10 to 500 (Figure 4a), 2DFC demonstrated overall lower latency and better scalability for workloads with fewer than 400 events. Second, we fixed the total number of intervals at 2,000,000 and distributed them across 10 to 1,000 events (Figure 4b). Here, 2DFC query time scaled linearly with the event count, though RTFC outperformed 2DFC when querying across smaller event sets (fewer than approximately 210 events). Finally, holding the event count steady at 200 while scaling the total intervals from 10 million to 90 million (Figure 4c), RTFC exhibited more favorable scaling compared to 2DFC. This behavior illustrates the expected algorithmic tradeoff: 2DFC is subject to an additive cost per event type, whereas RTFC relies on a logarithmic range-tree traversal that acts efficiently when pure interval volume dominates. To assess the sensitivity of the index structures to query parameters, we conducted two additional experiments on smaller fixed datasets, this time including 2DRT for comprehensive comparison. First, we tested sensitivity to the query’s temporal location, executing 1,000 queries with varying start points over a dataset of 200 events and 100,000 intervals per event (Figure 4d). While 2DRT query time scaled linearly as the start point shifted later in time, 2DFC maintained a constant performance independent of the starting temporal boundary. Second, we assessed sensitivity to varying query ranges lengths (Figure 4e) using a dataset of 100 events and 20,000 intervals per event. For query lengths spanning 1 million to 90 million units (returning 2,000 to 180,000 results), all internal structures showed linear scaling. In these comparisons, 2DFC consistently provided the lowest query time overall compared to RTFC and 2DRT, with RTFC demonstrating the steepest latency slope.
4.4. FCFC query performance While 2DFC effectively handles multi-event overlap retrieval natively via bounded queries, the FCFC variant is designed specifically to accelerate sequential dual-event temporal matching. We evaluated FCFC query performance based on 36 dual-event “Before variant 2” queries (using a fixed anchor event 𝐴, 36 distinct target events 𝐵, and a threshold of 𝑚 = 600 time units). We benchmarked FCFC against a conventional NFA-style approach which utilizes a repeated flatten-sort-scan algorithm, testing both over strictly in-memory (RAM) and database-backed (MongoDB) execution environments. As illustrated in Figure 5, the algorithm yielded significant practical benefits. In RAM implementations, FCFC consistently reduced query execution times by 80-98% by bypassing repeated time comparisons, instead acting Huang et al.: Preprint submitted to Elsevier
Page 13 of 19
6
0.06
5
0.05
4
0.04
3
0.03
2
0.02
1
0.01
14 12 10 8 6
0
4 2
0 10 50 90 130 170 210 250 290 330 370 410 450 490 2DFC
0 10
110 210 310 410 510 610 710 810 910
RTFC
2DFC
(a) Events, constant intervals/event.
2DFC
(b) Events, constant total intervals.
0.4
10m 20m 30m 40m 50m 60m 70m 80m 90m
RTFC
RTFC
(c) Intervals/event, constant events.
3
0.35
2.5
0.3 2
0.25
1.5
0.2 0.15
1
0.1 0.5
0.05
1
11
21
31
41 2DFC
51 RTFC
61
71
81
91
2DRT
(d) Different query start points.
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 155 162 169 176
0
0
2DFC
RTFC
2DRT
(e) Different query ranges.
Figure 4: Query performance of 2DFC, RTFC, and 2DRT. (a)-(c) vary event count and interval count; (d)-(e) vary query interval start point and range.
upon computationally inexpensive precomputed distance arrays. In MongoDB scenarios, both methods encountered generally higher latencies due to fundamental database I/O overhead. With very low-frequency occurrences, this underlying I/O cost heavily dominated execution time and narrowed the relative gap between the implementations. However, for heavily-represented queries yielding substantial candidate sets, which is usually the cause of temporal processing bottlenecks, FCFC successfully bridged this gap to achieve around a 50% overall query time reduction.
4.5. QEL query application on real-world data To illustrate the clinical utility of the QEL/BEST framework, we first consider cohort selection for established studies of central and obstructive sleep apnea, where differentiating central from obstructive events is essential for characterizing distinct pathophysiological phenotypes Donovan and Kapur (2016). Using QEL, analogous cohort inclusion criteria can be expressed directly at the event-logical level. For central apnea, a basic QEL cohort selection query is ( ) ◊𝑚 CA 0 . Translation: “For this subject, does the overnight PSG contain at least one central apnea (CA) event anywhere in the recording window [0, 𝑚)” Evaluating this formula on the CCSHS cohort returns 285 subjects (55.3% of the sample) Huang et al.: Preprint submitted to Elsevier
Page 14 of 19
7
100.00%
6
350
100.00%
300
50.00% 5
50.00% 250
0.00%
4
3
-50.00%
2
0.00%
200
150
-50.00%
100
-100.00% 1
-100.00% 50
0
-150.00% 1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 tel_query_time
benchmark_query_time
0
-150.00% 1
2
3
4
5
tel_time_saved
(a) RAM
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 tel_query_time
benchmark_query_time
tel_time_saved
(b) MongoDB
Figure 5: Dual-event query performance comparison with 36 testing queries (x axis) on CCSHS dataset. Blue bars represent the “Before variant 2” query time using FCFC, and orange bars represent the benchmark query time. Query time is in seconds (left y axis) The gray line represents the query time saved by FCFC in percentage (right y axis). (a) shows the results on RAM, and (b) shows the results on MongoDB.
in 0.06 seconds. A structurally identical single-event query for obstructive apnea is ( ) ◊𝑚 OA 0 . In pediatric populations, the onset of desaturation following apnea can be extremely rapid with a median delay of 12 seconds, carrying significant clinical implications Patel, Lenczyk, Hannallah and McGill (1994). Related work also demonstrated tight coupling between apnea, desaturation, and bradycardia in preterm infants Poets, Stebbens, Samuels and Southall (1993). To explore such temporal relationships in CCSHS, we formulate a preliminary cohort-selectionstyle query capturing subjects in whom a central apnea precedes an SpO2 desaturation using the Before variant 2 template: ( ) ( ) ∃𝑞∃𝑥∃𝑦 □𝑥 ¬CA ∧ □𝑦 (CA ∧ ¬SPO2_DESAT) 𝑥 ∧ (◊600 SPO2_DESAT)𝑥+𝑦 . 𝑞
Translation: “Does this subject exhibit at least one episode in which a central apnea (CA) begins after a CA-free baseline, persists for 𝑦 seconds without overlapping SpO2 desaturation, and is followed within 600 seconds by an SpO2 desaturation event-mirroring analyses that select infants or children whose desaturations are temporally attributable to preceding apneas?” This query searches for sequences in which a central apnea clearly precedes an SpO2 desaturation, separating desaturation dynamics caused by apnea from those driven by other pathophysiology (e.g., intrinsic lung disease). When evaluated across all 515 CCSHS subjects, 254 subjects satisfy this desaturation-to-apnea pattern (Row 4 of Table 3). By adjusting the temporal bounds (e.g., varying the maximum allowable delay), the same QEL template can be used to compare desaturation-latency distributions across subgroups, analogous to prior work quantifying apneadesaturation delays as physiological markers. We assessed query speed for a representative set of QEL formulas, comprising one single-event query, five dualevent queries, and three event-extraction queries, on the CCSHS dataset described in Section 4.2. The evaluated queries, together with their template names (see Section 3.5) and constituent events, are: • (1) Anywhere-on-timeline existence: central apnea. • (2) Co-occurrence: central apnea and sleep stage N3. • (3-6) Before variants 1-4: central apnea and SpO2 desaturation. • (7) Clock-anchored existence extraction: events between 3:00 and 4:00 AM. • (8) Event-anchored existence extraction: windows centered on central apnea. • (9) Event-anchored universality extraction: regions in which central apnea persists. Huang et al.: Preprint submitted to Elsevier
Page 15 of 19
Table 3 Query performance on CCSHS dataset at different scales. Execution time (Exe time) is in seconds and reported as average over 10 runs. ∗The query only returns the subjects satisfying the query condition, so the number of events is not applicable.
1 2 3 4 5 6 7 8 9
Num of subjects 285 285 224 254 235 254 515 285 285
Num of events 𝑁∕𝐴∗ 𝑁∕𝐴∗ 𝑁∕𝐴∗ 𝑁∕𝐴∗ 𝑁∕𝐴∗ 𝑁∕𝐴∗ 21,667 2,700 1,747
Exe time (x1) 0.06 0.13 0.10 0.11 0.10 0.15 0.45 0.09 0.07
Exe time (x10) 0.09 0.91 0.43 0.53 0.51 0.51 1.97 0.23 0.20
Exe time (x100) 0.46 4.25 4.19 4.22 4.09 4.11 7.91 1.70 1.60
Exe time (x1000) 4.18 42.19 44.95 42.06 40.91 43.93 921.45 76.16 72.78
The query performance results are summarized in Table 3. The x1, x10, x100, and x1000 columns correspond to the original CCSHS dataset and synthetically scaled datasets containing 10, 100, and 1,000 times as many subjects, respectively. Execution times are reported as averages over 10 runs per condition. Across all scales, the QEL engine efficiently handles cohort-selection and event-extraction workloads on large sleep datasets: even at x1000, cohortselection-style queries execute in under 45 seconds. For extraction queries that return large event sets, runtime growth is dominated by memory and data-transfer overhead rather than by the temporal-logic model-checking semantics themselves, consistent with experience from large-scale oximetry-based screening studies Álvarez, Hornero, García, del Campo and Zamarrón (2007). To demonstrate the expressive power of QEL beyond standard cohort templates, we next present two illustrative patterns that align with complex clinical phenotyping tasks in the sleep-medicine literature.
Example 1: Pre-apnea medication washout and sleep-stage restriction. In interventional sleep trials, it is common to restrict analyses to epochs with/without confounding medications or interventions and to focus on specific sleep stages where respiratory events have clearer physiological interpretation. For instance, we can encode a medication washout pattern of a desaturation-to-apnea delay with medication and sleep-stage constraints: ( ) ( ) ∃𝑞 □600 ¬(MED ∨ CA ∨ OA) ∧ □5 (CA ∨ OA) ∧ N3 ∧ ¬SPO2_DESAT 600 ∧ (◊20 SPO2_DESAT)605 . 𝑞
Translation: “Does this subject have at least one medication-free baseline interval without central or obstructive apnea for 600 seconds, followed by a central or obstructive apnea occurring in N3 sleep that lasts at least 5 seconds without overlapping SpO2 desaturation, and then an SpO2 desaturation beginning within 20 seconds?” This example shows how QEL can simultaneously encode washout windows, stage-specific constraints, and apnea-desaturation timing, providing a declarative analogue of complex inclusion criteria used in mechanistic and interventional studies of apnea.
Example 2: Signal-level physiological event definitions. In many large datasets, respiratory and hypoxemic events are available only as precomputed labels, which can suffer from inter-scorer variability and evolving scoring rules Berry et al. (2012). QEL instead allows event definitions to be specified directly from continuous physiological signals, in line with the American Academy of Sleep Medicine (AASM) scoring criteria and signal-level approaches to oximetry-based screening Berry et al. (2012); Álvarez et al. (2007). We illustrate this with two atomic constructs: A signal-level central apnea can be captured in QEL as ( ) 𝜑CA_signal = ∃𝑑 ≥ 10□𝑑 𝓁AirflowCessation ∧ 𝓁EffortAbsence .
Definition: “An event is classified as a central apnea if: (i) the airflow signal shows a complete or near-complete cessation (nasal cannula pressure or thermistor amplitude close to zero, encoded by atomic label 𝓁AirflowCessation ) lasting at least 10 seconds; and (ii) respiratory effort signals show simultaneous absence of chest and abdominal movements (plethysmography bands flat, encoded by atomic label 𝓁EffortAbsence ) throughout the event, consistent with AASM criteria for central apnea Berry et al. (2012).” Huang et al.: Preprint submitted to Elsevier
Page 16 of 19
Let stable pre-event baseline window be 30 seconds. A signal-level desaturation event is defined as ( ) ( ) 𝜑Desat_signal = ∃𝑑 ≥ 10 □30 𝓁SpO2> 94% ∧ □𝑑 𝓁SpO2Drop≥ 3% 30 . Definition: “A hypoxemic event is defined as a transient drop in the SpO2 signal of at least 3 to 4% relative to a stable pre-event baseline > 94% lasting at least 10 seconds.” We can express the desaturation-to-CA delay cohort selection query using signal-level definitions as: ∃𝑞 ∃𝑑 ≤ 12 ∃𝑥 ≥ 10 ∃𝑦 ≥ 10 ( ( ) □30 𝓁SpO2>94% ∧ ¬(𝓁AirflowCessation ∧ 𝓁EffortAbsence ) ( ) ∧ □𝑥 (𝓁AirflowCessation ∧ 𝓁EffortAbsence ) ∧ □𝑑 ¬𝓁SpO2Drop≥ 3% 30 ( ) ) ∧ □𝑦 𝓁SpO2Drop≥ 3% 30+𝑑 𝑞 .
(1)
Because all components are defined directly on raw signals, QEL can reproduce and extend signal-processing pipelines used in apnea-hypopnea research while retaining a single declarative language for both event definition and cohort selection.
5. Discussion Symbolic biomedical informatics contribution. This logic-based framework recasts sleep temporal querying as a
data-management and secondary-use problem rather than a pure algorithmic range-search problem. QEL formulas provide explicit, reusable phenotype definitions; BEST provides a common interval-ensemble representation for NSRR-style annotations; and model checking provides a precise semantics for cohort inclusion. Unlike ad hoc scripts, a phenotype or cohort expressed as a QEL formula is fully reproducible, straightforward for investigators to read, and readily processed by machines.
Model-checking rigor. The finite-evidence theorem in Section 3.4 guarantees that QEL queries over dense rational
time can be evaluated by finitely many representative checks once a BEST and a formula are fixed. Thus the endpointarray representation is a sound reduction from the formal semantics. This is especially important for real-world clinical research, where small differences in event anchoring, delay windows, and inclusion/exclusion criteria can materially alter cohort membership.
2DFC build time and space efficiency. 2DFC is significant because it exploits a biomedical-data property that generic range structures ignore: per-label sleep annotation intervals are already sorted and non-overlapping after BEST normalization. At 90M intervals, 2DFC takes 3,655 s compared with 11,549 s for RTFC and 23,902 s for 2DRT, yielding approximately 3× and 6× reductions (Table 2). Its 𝑂(𝑛) build time and 𝑂(𝑛) space are important for practical repository services, where indexes must be rebuilt or refreshed as datasets are curated and shared.
2DFC query performance and tradeoffs. For typical sleep datasets (𝑚 ≈ 23, 𝑛 > 200,000), the 𝑂(𝑚) term in 2DFC’s 𝑂(log |𝐹 𝐶[0]| + 𝑚 + 𝑘) complexity is negligible. At larger 𝑚, RTFC (𝑂(log 𝑛 + 𝑘)) can overtake 2DFC; in our synthetic experiments, the crossover occurs near 𝑚 = 210 at 2M total intervals (Figure 4b). In practice, event lists can be ordered by ascending cardinality and compatible non-overlapping labels can be merged to reduce the additive event-type term.
FCFC performance for dual-event pattern matching. FCFC targets a different part of the model-checking workload: dual-event relationships such as co-occurrence, before/after variants, and bounded delay. By replacing repeated flatten-sort-scan operations with precomputed distance arrays, FCFC achieves 80-98% query-time reduction versus the NFA-style baseline in RAM mode and approximately 50% reduction in MongoDB mode for high-candidate queries (Figure 5). Choosing the rarest event as the anchor further improves throughput.
Real-world scalability. On CCSHS (515 subjects, 202,587 intervals, 23 event labels), all evaluated queries run at sub-second latency at original scale. Cohort-selection queries (Table 3, Q1-6) complete within 45 s at 1,000× scale. Event-extraction query Q7 reaches 921 s at 1,000×, reflecting result-set size and hardware constraints. These experiments show that formal model checking and scalable systems design can coexist in a deployable sleep-data platform. Huang et al.: Preprint submitted to Elsevier
Page 17 of 19
Limitations and extensions. 2DFC and FCFC assume normalized non-overlapping interval ensembles; overlapping annotations require preprocessing or label-specific normalization. FCFC’s 𝑂(𝑚𝑙) space can be large and may benefit from sparse, on-demand, or compressed construction. Fully general nested QEL formulas require recursive application of the finite-evidence theorem beyond the query templates evaluated here. The current framework is designed for retrospective, static datasets: adding new events or subjects requires rebuilding the 2DFC and FCFC index structures, and incremental or online index maintenance is an engineering extension for continuously growing repositories. The cohort-discovery layer currently relies on a fixed library of query templates; translation of arbitrary free-form QEL formulas into executable query statements, together with automated query optimization and plan selection, is an important direction for future work. Future work should also integrate uncertainty in annotations, support cross-study harmonization of event vocabularies, and expose QEL formula libraries through data-sharing platforms so that temporal phenotypes can be reused across cohorts.
6. Conclusion We presented a logic-based temporal cohort discovery engine for sleep-study data that integrates formal representation, model checking, index design, and empirical validation. QEL provides a dense-time logical foundation for expressing temporal phenotypes over PSG annotations and signal-derived intervals. BEST provides a compact subjectlevel representation in which every event label is interpreted as a finite interval ensemble. Together, QEL and BEST make cohort inclusion criteria explicit and reproducible by bridging human readability and machine computability: a subject satisfies a cohort definition precisely when the corresponding BEST model satisfies the QEL formula. The indexing contributions make this formal semantics practical for large repositories. 2DFC exploits the sorted, non-overlapping structure of normalized sleep annotation intervals to support efficient interval-overlap retrieval with 𝑂(𝑛) build time and 𝑂(𝑛) space. FCFC targets the complementary workload of dual-event temporal pattern matching by linking boundaries to a global index and enabling 𝑂(1) target-event lookup for each anchor-target comparison after preprocessing. Experiments on synthetic datasets up to 90 million intervals and on CCSHS annotations from NSRR demonstrate that this combination of formal model checking and specialized indexing can support both cohort-selection and event-extraction workloads at repository scale. This work positions temporal cohort discovery as a first-class biomedical informatics capability rather than as a collection of ad hoc scripts. By organizing sleep research requirements into single-event retrieval, dual-event temporal pattern matching, and event data extraction, the framework provides reusable query templates that can encode clinically meaningful timing constraints, including AASM-inspired duration thresholds, co-occurrence, bounded delay, stage restriction, and absence windows. The same principles can be extended to other biomedical domains where highresolution physiological time series and interval annotations are central to computational phenotyping.
Acknowledgment This work has been supported in part by the U.S. National Science Foundation Award IIS2500624 and the National Institutes of Health grants R01AG084236 and U24AG098157. The views expressed in this paper are those of the authors and do not necessarily reflect those of the funding agencies.
Declaration of Competing Interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References Álvarez, D., Hornero, R., García, M., del Campo, F., Zamarrón, C., 2007. Improving diagnostic ability of blood oxygen saturation from overnight pulse oximetry in obstructive sleep apnea detection by means of central tendency measure. Artificial intelligence in medicine 41, 13–24. American Sleep Disorders Association, 1992. EEG arousals: scoring rules and examples: a preliminary report from the sleep disorders atlas task force of the American Sleep Disorders Association. Sleep 15, 173–184. Azarbarzin, A., Sands, S.A., Stone, K.L., Taranto-Montemurro, L., Messineo, L., Terrill, P.I., Ancoli-Israel, S., Ensrud, K., Purcell, S., White, D.P., Redline, S., 2019. The hypoxic burden of sleep apnoea predicts cardiovascular disease-related mortality: the osteoporotic fractures in men study and the sleep heart health study. European Heart Journal 40, 1149–1157. Bentley, J.L., Saxe, J.B., 1980. Decomposable searching problems. SIAM Journal on Algebraic Discrete Methods 1, 301–358.
Huang et al.: Preprint submitted to Elsevier
Page 18 of 19
Berry, R.B., Brooks, R., Gamaldo, C.E., Harding, S.M., Lloyd, R.M., Marcus, C.L., Vaughn, B.V., 2015. The AASM Manual for the Scoring of Sleep and Associated Events: Rules, Terminology and Technical Specifications. Version 2.2 ed., American Academy of Sleep Medicine, Darien, Illinois. Berry, R.B., Budhiraja, R., Gottlieb, D.J., Gozal, D., Iber, C., Kapur, V.K., Marcus, C.L., Mehra, R., Parthasarathy, S., Quan, S.F., et al., 2012. Rules for scoring respiratory events in sleep: update of the 2007 aasm manual for the scoring of sleep and associated events: deliberations of the sleep apnea definitions task force of the american academy of sleep medicine. Journal of clinical sleep medicine 8, 597–619. Carbone, P., Katsifodimos, A., Ewen, S., Markl, V., Haridi, S., Tzoumas, K., 2015. Apache Flink: Stream and batch processing in a single engine. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 36, 28–38. Chazelle, B., Guibas, L.J., 1986. Fractional cascading: I. A data structuring technique. Algorithmica 1, 133–162. Chen, S., Redline, S., Eden, U.T., Prerau, M.J., 2022. Dynamic models of obstructive sleep apnea provide robust prediction of respiratory event timing and a statistical framework for phenotype exploration. Sleep 45, zsac189. Chung, F., Liao, P., Elsaid, H., Islam, S., Shapiro, C.M., Sun, Y., 2012. Oxygen desaturation index from nocturnal oximetry: a sensitive and specific tool to detect sleep-disordered breathing in surgical patients. Anesthesia & Analgesia 114, 993–1000. Donovan, L.M., Kapur, V.K., 2016. Prevalence and characteristics of central compared to obstructive sleep apnea: analyses from the sleep heart health study cohort. Sleep 39, 1353–1359. EsperTech Inc., 2024. Esper – Complex Event Processing. https://www.espertech.com/esper/. Accessed: May 19, 2025. ISO/IEC 9075-2:2016, 2016. Information technology — database languages — SQL — part 2: Foundation (SQL/Foundation). International Organization for Standardization. Row Pattern Recognition (MATCH_RECOGNIZE). Lueker, G.S., 1978. A data structure for orthogonal range queries, in: 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), IEEE. pp. 28–34. Malicki, M., Karuga, F.F., Szmyd, B., Sochal, M., Gabryelska, A., 2022. Obstructive sleep apnea, circadian clock disruption, and metabolic consequences. Metabolites 13, 60. Mao, C., Eran, A., Luo, Y., 2019. Efficient genomic interval queries using augmented range trees. Scientific Reports 9, 5059. Microsoft Corporation, 2016. Temporal tables: System-versioned temporal tables. SQL Server Technical Documentation. https://learn. microsoft.com/en-us/sql/relational-databases/tables/temporal-tables. Mokhlesi, B., 2012. Rem-related obstructive sleep apnea: to treat or not to treat? Journal of Clinical Sleep Medicine 8, 249–250. Moskovitch, R., Shahar, Y., 2015. Fast time intervals mining using the transitivity of temporal relations. Knowledge and Information Systems 42, 21–48. Özçep, Ö.L., Möller, R., Neuenstadt, C., 2014. A stream-temporal query language for ontology based data access, in: Proceedings of the 37th German Conference on Artificial Intelligence, pp. 183–194. Patel, R., Lenczyk, M., Hannallah, R.S., McGill, W.A., 1994. Age and the onset of desaturation in apnoeic children. Canadian journal of anaesthesia 41, 771–774. Poets, C.F., Stebbens, V.A., Samuels, M.P., Southall, D.P., 1993. The relationship between bradycardia, apnea, and hypoxemia in preterm infants. Pediatric research 34, 144–147. Rosen, C.L., Larkin, E.K., Kirchner, H.L., Emancipator, J.L., Bivins, S.F., Surovec, S.A., Martin, R.J., Redline, S., 2003. Prevalence and risk factors for sleep-disordered breathing in 8- to 11-year-old children: association with race and prematurity. The Journal of Pediatrics 142, 383–389. Tsai, W.H., Flemons, W.W., Whitelaw, W.A., Remmers, J.E., Brant, R., 1999. A comparison of apnea–hypopnea indices derived from different definitions of hypopnea. American Journal of Respiratory and Critical Care Medicine 159, 43–48. Yamauchi, M., Fujita, Y., Kumamoto, M., Yoshikawa, M., Ohnishi, Y., Nakano, H., Inoue, T., Tamaki, S., 2015. Nonrapid eye movementpredominant obstructive sleep apnea: a frequent phenotype in patients with sleep-disordered breathing. Journal of Clinical Sleep Medicine 11, 1007–1013. Zhang, G.Q., 2024. Temporal ensemble logic. arXiv preprint arXiv:2408.14443. Zhang, G.Q., Cui, L., Mueller, R., Tao, S., Kim, M., Rueschman, M., Mariani, S., Mobley, D., Redline, S., 2018. The National Sleep Research Resource: towards a sleep data commons. Journal of the American Medical Informatics Association 25, 1351–1358. Zhang, G.Q., Hao, X., Huang, Y., Li, X., Cui, L., 2026. QEL: Rational ensemble logic for model-checking-based cohort discovery with real-world electrophysiology data. Under review.
Huang et al.: Preprint submitted to Elsevier
Page 19 of 19