3D-04 - Pruning to increase computational efficiency for tree-based scan statistics

Background: Tree-based scan statistics (TBSSs) are popular methods to conduct disproportionality analyses with many hierarchically related outcomes, allowing one to generate hypotheses on the safety of drugs among thousands of hierarchically related outcomes. TBSSs have been routinely used to implement safety surveillance by organizations such as the Food and Drug Administration (FDA) or the Centers for Disease Control and Prevention (CDC). However, the runtime of currently available TBSS implementations can be substantial, ranging from days to weeks for cohorts of realistic sizes, thus emphasizing the need for more efficient implementations.

Objectives: To compute statistically valid bounds on the p-values calculated by TBSS, and to use those bounds in a two-fold manner. First, to quickly estimate the number of signals in the data using the fact that for non-significant nodes, p-value lower bounds usually indicate a departure from the significance threshold early on in the TBSS run. Second, to prune non-significant nodes in a sequential TBSS application, thereby reducing the size of the tree and speeding up the computation.

Methods: The Dvoretzky-Kiefer-Wolfowitz inequality can be used to bound the cdf (cumulative distribution function) that is being approximated with a permutation test. Since the p-value of any node can equivalently be computed with an evaluation of the cdf, the bounds on the cdf directly translate to bounds on the p-values. Iteratively pruning non-significant nodes, that is those nodes whose lower p-value bound exceeds the testing threshold, reduces the size of the tree and speeds up the computation.

Results: We applied the methodology to test the global null hypothesis of no elevation in risk between SGLT2 and GLP1 inhibitors in a hierarchical classification of clinical diagnoses, encoded in a tree of ICD-9 (International Disease Classification) codes. The tree contained 32513 nodes, among them 12213 leaves. Computing p-values sequentially in 10 batches (10 permutations per node and per batch) while repeatedly pruning the tree requires around 33% less effort compared to the full computation of 100 permutations per node, while discovering exactly the same 32 signals.

Conclusions: Results indicate that pruning allows one to reduce the computational effort of TBSS without a loss of power.