Widespread adoption of electronic health records has generated vast amounts of data, which are increasingly being used in clinical, epidemiological, and public health research [1]. Data from multiple health care organizations are often needed to increase statistical power or to access diverse patient populations and geographic regions. Although it is possible to combine patient-level data from multiple sites into a secure central repository for analysis, there are often significant technical and regulatory barriers to doing this in a way that ensures patient privacy. Institutions must compare the benefit of centralized data for research with the risk of violating the Health Insurance Portability and Accountability Act (HIPAA) and other privacy laws as a result of unintended disclosure of patient data. An alternative approach is to create federated clinical data research networks, which broadcast queries to multiple sites, run analyses locally, and then combine the results. In this way, sites retain control over their patient data. Two of the largest networks in the United States are the Patient-Centered Outcomes Research Network (PCORnet) [2] and the National Institutes of Health (NIH)–funded Accrual to Clinical Trials (ACT) network [3-5], both of which connect dozens of health care organizations across the country and include health data on nearly 100 million Americans.

As patients often receive care at more than one clinical site, the data for a patient at any one site might not be complete, and the same information about a patient might be duplicated at different sites. This can lead to queries returning incorrect results. This problem is amplified when the sites in the network are geographically close and there is greater overlap in their patient populations. However, because patients move or travel, sometimes across state or country borders, even far apart sites might share patients. A similar situation arises when patients’ data are intentionally separated for technical reasons, such as when large amounts of clinical data (eg, diagnoses and medications) and genomic data are stored in different locations, and it is not feasible to merge them into a single database. In both cases, computation must be performed in a distributed fashion, but the challenge is that an individual patient’s data may be spread across multiple databases.

Various methods to addressing this problem have been described in the literature, but they have different trade-offs in terms of accuracy, privacy, scalability, and computational complexity. We grouped these into 3 broad categories: aggregate counts, hashed patient identifiers, and privacy-guaranteed methods (Figure 1).

In this paper, we propose a new method for combining data from sites in a federated clinical data network, based on the HyperLogLog (HLL) probabilistic sketching algorithm [19]. A probabilistic sketch is a small data structure that summarizes large amounts of data. A calculation can run on the sketch to obtain a fast, accurate estimate of what the result would be on the original data. Although HLL is widely used in many software programs, such as internet search engines, to our knowledge, it has not been applied to federated queries of health data.

The basic idea behind HLL (and other minimum value sketches) [20] is that the minimum of a collection of random numbers between 0 and 1 is inversely proportional to how many numbers are present. For example, a single random number between 0 and 1 has an expected value of 0.5; however, if we have 99 random numbers, the minimum has an expected value of 0.01. By using a hash function that maps patients to a random number between 0 and 1, we can estimate the number of patients who match a query at a site by keeping track of just the minimum hash value of the matching patients. If the minimum hash value is v, then the estimated number of patients is (1/v)-1. Although the accuracy of this estimate is poor, the method can be improved by using t different hash functions to generate t independent estimates of the number of patients. The average of these results in a more accurate overall estimate. The set of t minimum hash values is the sketch.

If each site in a network uses the same hash function and returns its minimal hash value, then we can estimate the number of distinct patients in the whole network that match the query from the smallest of those values. Although it may seem unintuitive that the network minimum hash is the same as the hash for one hospital, the hospital which the minimum hash corresponds to changes when multiple hash functions are used, allowing the estimator to be accurate.

Instead of using t hash functions, HLL improves the accuracy of this method by using a single hash function but efficiently dividing the patients into t partitions and returning the minimum hash value of patients in each partition. HLL also returns the position of the leading one indicator in the binary expansion of the minimum values rather than the actual values. This only has a small effect on accuracy; however, it greatly reduces the risk of reidentification from a dictionary attack. For t partitions, the relative error of HLL is approximately 1/sqrt(t). For example, by asking sites to share an HLL sketch with only 100 values, the number of distinct patients can be estimated with a 10% relative error. The error can be reduced by increasing t. Although higher t increases the risk of reidentification, the risk is quantifiable and predictable, enabling networks to define policies that maximize accuracy while reducing risk to an acceptable level.

We aim to enable accurate estimates of the number of unique patients matching a federated query while providing strong guarantees on the amount of protected medical information revealed.

In the Methods section, we first show how sites can generate a privacy-preserving HLL sketch of the patients who match a query and how the shared sketches from sites can be combined to estimate the number of unique patients in the network who match the query. We then describe several obfuscation approaches that further reduce the privacy risk of aggregate counts, hashed identifiers, and HLL sketches. These include methods that might result in a loss of information or an increase in computational complexity to make it more difficult or impossible for an adversary to identify patients. In the Results section, we test our algorithm and other methods using simulated networks of different sizes and degrees of patient overlap. We compare them along several dimensions, including accuracy, privacy risk, computation time, and amount of data shared. Finally, in the Discussion section, we summarize the trade-offs and limitations of the algorithms and provide recommendations on when networks should consider using HLL sketches.

Here, we describe the algorithms we compared. The basic model assumes that a researcher at one hospital in the network sends a query of the form How many unique patients have condition X across the hospital network? to a central network hub. The hub then distributes the query to all the hospitals in the network. The hospitals determine which of their patients match the query and return a result (the form of this result varies by algorithm) to the hub. The hub combines the results and returns an estimate of the total number of unique patients to the researcher. The name of each algorithm combines the base method (Count, HashedIDs, or HLL) and any additional obfuscation (Mask, MPC, Rehash, or Shuffle).

To quantitatively measure privacy loss, we used an adapted k-anonymity model of privacy, whereby the privacy risk is defined to be the number of revealed data points that correspond to fewer than k=10 patients [22,25] (for details on the privacy risk score, see Multimedia Appendix 1 [6,7,10-12,14-17,21-24]). We ran benchmarks for runtime, accuracy, and privacy loss on (1) shared aggregate counts (Count and Count+Mask), (2) shared hashed identifiers (HashedIDs), and (3) our proposed HLL approach. Each of these was paired with various obfuscation techniques of masking, rehashing, shuffling, and MPC. HLL was tested using different number of buckets or values in the sketch. We indicate the size of the sketch, t, with a number after HLL, such that HLLN means 2^N values. For example, t=2¹=2 (HLL1), t=2⁴=16 (HLL4), t=2⁷=128 (HLL7), and t=2¹⁵=32,768 (HLL15). Although Count+MPC uses a standard MPC privacy-guaranteed cryptosystem, we implemented our own protocols for the HLL+MPC variants using ElGamal encryption [21] and a private equality test [23]. We did not run benchmarks for other existing privacy-guaranteed methods because they do not scale well and are infeasible for running on large data sets, with either extremely high runtime or error (for descriptions of several of these algorithms and their limitations, see Multimedia Appendix 1 [6,7,10-12,14-17,21-24]).

Due to patient privacy, we cannot test the algorithms using actual hospital data. Therefore, we developed software for generating simulated federated networks of hospitals spread geographically with highly varying sizes and overlap [24] (for details on simulating a federated hospital network, see Multimedia Appendix 1 [6,7,10-12,14-17,21-24]). We ran our benchmarks on simulated networks containing up to 100 million total distinct patients, distributed across 100 hospitals. In the simulations, patients on average received care at 2 hospitals. However, this number varies and hospitals that are geographically close in the simulations are modeled to have a larger number of shared patients.

The benchmarks were run on an 8-core AMD Ryzen 1700 processor with 16 GB of RAM running Ubuntu 18.04.2 Long Term Support. We measured the wall-clock time for each pipeline component for time complexity and serialized bitstrings in each communication round for transmission space complexity. We provide all code in GitHub [26].

Multimedia Appendix 2 lists the detailed benchmark results for accuracy, privacy risk, and runtimes of queries matching 1, 10, 100, 1000, 10,000, 100,000, 1 million, 10 million, or 100 million patients using the different methods. As an example, Table 1 shows a subset of rows from the table in Multimedia Appendix 2 corresponding only to queries matching 10,000 patients and HLL sketches with 2⁷ (HLL7) and 2¹⁵ (HLL15) values.

Accuracy is described in absolute terms as the 95% CIs of the estimated number of patients who matched a query in 100 simulated experiments. More precisely, in each of the 100 runs, each estimator tries to return either its best guess or upper or lower bounds. If it returns a single best guess, then we report the 97.5 and 2.5 percentiles as the upper and lower bounds, respectively. If it returns upper or lower bounds, then we report the 97.5 percentile of the upper bound and the 2.5 percentile of the lower bound. These are then converted into relative errors by comparing them with the true number of distinct patients.

Privacy risk is determined by counting the number of statistics (ie, a count, HLL bucket, or hash) that are not 10-anonymous revealed to either the hub or the hub colluding with a hospital. It relates to the number of patients who are potentially identifiable with a specific statistic, but it does not necessarily mean that an adversary will be able to identify a patient from a statistic. Therefore, it can be thought of as an upper bound on direct linkage risk. Note that this guarantee is applicable primarily for one common threat model. In the Discussion section, we will cover some other more sophisticated potential avenues for attack.

Wait time is the additional computational time that hospitals require to generate the statistics plus the time the hub requires to combine each hospital’s results. (It does not include the time each hospital needs to run the query.) For the same query, hospitals might have different wait times based on the number of matching patients. We, therefore, report both mean wait time, which is the average hospital computation time+hub computation time, and max wait time, which is the maximum hospital computation time for a run+hub computation time.

As an example, in Table 1, for a query that actually matches 10,000 patients, the basic Count algorithm had an estimated count CI (using the summation for the upper estimate and maximum for the lower estimate) of 899.9 to 19,470 patients or a relative error of –91% to +95%. It also, on average, had 2.65 hospitals that returned potentially identifiable counts because the value was less than 10. This risk can be eliminated with Count+Mask, which increases the error, or by Count+MPC, which adds computational complexity, and only gives a single guess, instead of both upper and lower bounds. On the opposite extreme, HashedIDs returns the exact answer, but all 10,000 patients’ identities are at risk from a dictionary attack. (Note that Table 1 lists the risk for HashedIDs at 19,174 because the same patient’s hash value can be returned by more than one hospital. We report the number of potentially identifiable values shared, not the number of unique patients at risk.) In HashedIDs+Rehash, the hub alone cannot identify patients from the hash values (the Risk:Hub column). However, the risk returns if an adversary can also obtain the secret random string from a hospital (the Risk:Hub+Site column).

Table 1 shows that HLL7 and HLL15 can achieve a more tunable balance between accuracy and privacy. HLL7 has a relative error of –17% to +13% (8310 to 11,347), which is considerably better than that of Count, and HLL15 results in an even smaller relative error of –1% to 1% (9928 to 10,075). HLL7 and HLL15 generate, on average, 15.73 and 3707 potentially identifiable values. However, adding obfuscation with HLL+Shuffle adds essentially no additional computation time but reduces the risk to less than 1 (0.23 on average) potentially identifiable value. In other words, highly accurate estimates with only 1% error can be obtained with most queries having no risk of reidentification. Even if an adversary obtains the secret random string, the risk of 3707 is much less than 19,174 for HashedIDs.

Figure 4 graphically illustrates the accuracy (the horizontal axis) and risk (the vertical axis) trade-off of the different algorithms. For simplicity, only the upper bound of the relative error is used for accuracy. (The lower bound and absolute errors are not shown.) Although an individual simulation is plotted as a single point in the figure, algorithms are shown as regions because changing the input parameters to the simulation affects the results. For example, the blue region in Figure 4 covers the range of HLLs with queries of different sizes (10 to 10 million matching patients) and sketches of different sizes (HLL1=2 to HLL15=32,768 values).

The key takeaway from Figure 4 is that Count and HashedIDs are extremes that cover only one axis or the other, whereas variations of HLL enable networks to select an algorithm that fits anywhere between the axes. In other words, with HLL, networks can determine an acceptable risk level and pick the sketch size and obfuscation method that will give the most accurate result. Alternatively, they can start with a desired accuracy and pick the most secure method that runs within a given amount of time.

Count+Mask has the worst accuracy but guarantees 10-anonymity (thin horizontal gray box; Figure 4). As each patient in the simulation was, on average, at two hospitals, queries that matched all 100 million distinct patients returned counts from each hospital that added up to 200 million—a 100% overestimate. Queries that only matched a few patients (small queries) had much greater error because of the obfuscation. The worst case, in theory, is when a query matches one distinct patient and that patient happens to be at each of the 100 hospitals. As each hospital returns ≤10, the upper bound estimate assumes that there are 10 patients in each hospital and that there is no overlap. This would result in an upper bound estimate of 100×10=1000 or a relative error of 99,900%. Even when patients are only at one hospital (no overlap), Count+Mask can have a 900% error.

Without obfuscation, the relative error of Count in the simulations remained near 100% for queries of all sizes (thin vertical gray box; Figure 4). However, for small queries, many sites returned potentially identifiable counts less than 10. At the other extreme, HashedIDs always gave correct answers (0% relative error). However, this requires sharing individual data on all matching patients (thin vertical brown box; Figure 4). The risk can be reduced if a different hash function is used for each query (HashedIDs+Rehash) and an adversary is unable to discover the hash functions.

Variations of HLL fill in the space between Count, Count+Mash, and HashedIDs, allowing the networks to tune their estimation method to achieve a more desirable balance of accuracy and risk for a given application. In Figure 4, HLL (the blue region), HLL+Shuffle (the red region), and HLL+Rehash (the thin horizontal green box) have the same accuracy but different levels of risk. In contrast to Count, which has more risk with smaller queries, HLL, like HashedIDs, has a higher risk with larger queries. Doubling the number of buckets in the HLL sketch reduces the error by a factor of sqrt(2); however, without obfuscation, it also doubles the risk.

The benefit of HLL+Shuffle is that buckets can be added to reduce error with only minimal change in risk. For queries that matched fewer than 100,000 patients, even HLL15+Shuffle, which has a relative error of only approximately 1%, had an average privacy risk of less than 1. HLL+Rehash reduced risk even further but required over a minute of extra computational time in some experiments, whereas the computational time of HLL+Shuffle is negligible. HLL+Mask guarantees 10-anonymity, but its error was often almost as large as Count+Mask. The benefit of HLL+Mask is that it can leverage the improved accuracy of HLL when possible, while ensuring that no added risk is introduced.

Table 2 provides a qualitative summary of the results. In general, HLL, especially with obfuscation, is much more accurate than aggregate counts, lower risk than sharing hash values of all matching patients, and more scalable than privacy guaranteeing algorithms. The relevant benefits of certain methods depend on the number of patients who match the query. For example, as the number of patients increases, the risk of Count decreases, as indicated by “(–)”, while the risk of HLL7 increases, as indicated by “(+).”

Multimedia Appendix 3 shows the theoretical upper bounds on the computational costs of each method plus obfuscation technique, theoretical exact communication costs (the space complexity of the amount of data that the hospitals and hub have to send over the network), and the actual empirical results of both computational and communication costs.

In this study, we surveyed and benchmarked a range of methods for determining the number of distinct patients who matched a federated query, exploring the trade-offs in accuracy, privacy, and speed. We explicitly do not endorse a single one-size-fits-all method because different networks and institutions will have different needs. With data use agreements and a trusted third party, HashedIDs provides the most accurate results. When minimizing privacy risk is the most important factor, networks can choose between (1) fast but inaccurate methods such as Count+Mask, (2) accurate but slow algorithms such as HLL+Rehash, or (3) privacy-guaranteed methods that only work on small networks. A key goal of the ACT network is real-time queries that enable rapid exploration of the data. As a result, adding even a few seconds of computational time to ACT queries might not be acceptable. When runtimes must be minimized, methods such as HLL7+Mask and HLL7+Shuffle are fast and have a good balance between accuracy and privacy.

In practice, we envision a combination approach. Queries can first be run using a fast, private method, such as Count+Mask or Count+MPC. Given these rough results and the needs of the researcher, hospitals can then be asked to return the HLL sketches for the patients who matched the query. The initial count estimate and the privacy risk allowed by the network could be used to select the HLL sketch size and obfuscation method that would return the most accurate result in a reasonable amount of time. In the final stage of research (eg, in preparation for a full clinical trial), investigators could request permission from institutions to run accurate but potentially identifiable queries, such as HLL15 or HashedIDs.

It is important for each institution to assess their own risk models. In particular, our risk model assumes that given a sketch for a given condition (eg, hypertension), the adversary already has access to the list of patients at the hospital and wants to identify patients that have the condition. The filled buckets of an HLL sketch correspond to hashes of patients who have the condition, and our goal is to ensure that for every patient with the condition, at least nine other patients without that condition could have hashed to the same value, ensuring 10-anonymity. Statistics that do not meet this requirement count for the privacy loss score. For example, our privacy risk analysis differs considerably from that of Desfontaines et al [27] who argue that “cardinality estimators do not preserve privacy.” However, their threat model assumes that an adversary can access the sketches as they are being generated, one patient at a time. In contrast, our risk model is based on each hospital’s final sketch, which represents all patients who match the query.

In addition, some amount of information is leaked about the patients not included in the sketch, precisely because they were not included. This does not allow an adversary to pinpoint patients with a condition but may sometimes allow them to determine a patient lacking that condition. Of course, this type of leakage is to some extent a problem with any aggregate query system, because if an adversary learns that only 1% of patients at a hospital have a condition, then they know with high certainty that most patients do not. In line with our analysis mentioned earlier, however, for this type of leakage, Count is more private than HLL, which is more private than HashedIDs, so the same privacy-accuracy trade-off applies.

We only considered a federated or distributed network in which no patient-level clinical data leave the institution and queries only return aggregate counts. This is in contrast to privacy-preserving record linkage approaches whose goal is to assemble a centralized deduplicated limited or deidentified data set through an honest broker without exchanging identifiable information. With the appropriate technologies, a secure infrastructure, and the proper institutional agreements in place, it is possible to merge data sets, even on large scales. PCORNet, in particular, has used methods similar to HashedIDs and HashedIDs+Rehash to do this for subsets of hospitals in its network [28,29]. There are multiple advantages of centralized data, including exact results and ease of use. However, in this study, we showed that (1) linking and deduplicating data at the individual patient level is not necessary to obtain accurate estimates and (2) this can be done in a computationally efficient manner. There are benefits to this federated model. It reduces concerns that hospitals might have in sharing data, it does not require updating and relinking the central database, and it places less dependency on having an honest broker.

We believe that as federated data networks expand to include more institutions and data types (clinical, genomic, environmental, etc), researchers will increasingly depend on fast, accurate, and secure query tools to obtain the greatest possible scientific value from the networks. However, because no single algorithm meets all these requirements, having the ability to select among different methods for a particular application is essential. In this study, we introduce HLL and several obfuscation techniques to provide networks with a tunable approach to determine the number of distinct patients who match a query, which is more balanced than commonly used methods that greatly sacrifice accuracy (Count+Mask), privacy (HashedIDs), or scalability.