Ranking in Genealogy: Search Results Fusion at Ancestry

Peng Jiang, Yingrui Yang, Gann Bierner, Fengjie Alex Li, Ruhan Wang, Azadeh MoghtaderiKDD 2019 · DOI · arXiv

Abstract

Genealogical search presents unique challenges due to the high disparity of record types and the need for both relevance and diversity in results. This paper introduces a two-stage ranking framework developed at Ancestry that utilizes a customized Coordinate Ascent (CA) algorithm for efficient intra-record ranking and a Nelder-Mead-based Stochastic Search for inter-record fusion. Additionally, a new metric, Normalized Cumulative Entropy (NCE), is proposed to measure local diversity in search results. Experimental results demonstrate a 10x speedup in training and significant improvements in ranking performance and result diversity compared to state-of-the-art baselines.

Introduction

Finding ancestors in massive, heterogeneous datasets—ranging from 19th-century census data to handwritten birth certificates—requires more than standard web search techniques. In genealogy, "relevance" is multifaceted; a user needs a diverse array of evidence to construct a complete family tree. This paper addresses the problem of record disparity and the need for interleaved, diverse search results.

The Challenge of Record Disparity

Genealogical research is hindered by the fact that different record types (e.g., birth, probate, census) contain non-overlapping data points. Scoring these equitably is difficult because a high-scoring match in one category might be less valuable than a medium-scoring match in another that provides a missing piece of the family puzzle. Furthermore, users require diversity; seeing ten versions of the same census record is less helpful than seeing one census, one birth, and one death record.

Proposed Architecture

The authors propose a two-stage architecture to handle these challenges: Record-Specific Search followed by Global Search (Collation).

Figure 1: The two-stage search architecture at Ancestry, showing the flow from client query to federated search and final collation.

1. Customized Coordinate Ascent (CA)

For ranking within a specific record type, the framework uses a customized CA algorithm. To overcome the slow convergence of standard CA, the authors introduced a weight initialization schema based on feature frequency in relevant versus irrelevant records, particularly effective for the binary features common in Ancestry’s data.

2. Stochastic Search (SS) for Fusion

To combine results from different record types into a single "Global Search" list, a linear combination model is employed. The weights for this model are optimized using the Nelder-Mead (Downhill Simplex) algorithm.

Figure 5: The various operations of the Nelder-Mead (Downhill Simplex) algorithm used for derivative-free optimization in result fusion.

Because Nelder-Mead is derivative-free, it allows direct optimization of non-differentiable metrics like NDCG. The algorithm is "warm-started" with weights from a RankSVM model to avoid local optima.

3. Normalized Cumulative Entropy (NCE)

To better measure the quality of search results, the authors introduced Normalized Cumulative Entropy (NCE). Unlike traditional diversity metrics that measure global presence, NCE measures local diversity—rewarding lists where different record types are interleaved (e.g., [Birth, Census, Death]) rather than clumped.

Key Results

The proposed methods yielded significant improvements across several dimensions:

  • Training Efficiency: The customized CA algorithm achieved convergence 10 times faster than canonical CA without sacrificing ranking performance.
  • Ranking Performance: The Stochastic Search (SS) model outperformed state-of-the-art models like LambdaMART and RankNet, achieving an NDCG@100 of 0.7131 compared to a 0.6072 baseline.
  • Training Speed: SS was nearly 12x faster to train than LambdaMART (1,172s vs. 14,021s).
  • Diversity: Both SS and CA models showed measurable improvements in diversity via the NCE metric.

Conclusion and Future Work

The two-stage ranking framework and the NCE metric provide a robust solution for the complexities of genealogical search. By leveraging derivative-free optimization and focusing on local diversity, Ancestry has improved both the speed and quality of its search engine. Future work will explore non-uniform diversity assumptions and personalized search based on a user's existing family tree.

Summary updated

BibTeX
@inproceedings{jiang2019ranking,
  author = {Peng Jiang and Yingrui Yang and Gann Bierner and Fengjie Alex Li and Ruhan Wang and Azadeh Moghtaderi},
  title = {{Ranking in Genealogy: Search Results Fusion at Ancestry}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  doi = {10.1145/3292500.3330772},
}
Figure