In the era of big-data, personal data is produced, collected and consumed at different sites. A public directory connects data producers and consumers over the Internet and should be constructed securely given the privacy-sensitive nature of personal data. This work tackles the research problem of distributed, privacy-preserving directory publication, with strong security and practical efficiency. For proven security, we follow the protocols of secure multi-party computations (MPC). For efficiency, we propose a pre-computation framework that minimizes the private computation and conducts aggressive pre-computation on public data. Several pre-computation policies are proposed with varying degrees of aggressiveness. For systems-level efficiency, the pre-computation is implemented with data parallelism on general-purpose graphics processing units (GPGPU).We apply the proposed scheme to real health-care scenarios for constructing patient-locator services in emerging Health Information Exchange (or HIE) networks. We conduct extensive performance studies on real datasets and with an implementation based on open-source MPC software. With experiments on local and geo-distributed settings, our performance results show that the proposed pre-computation achieves a speedup of more than an order of magnitude without security loss.