Back to results
US 12,222,963 B2Granted
Data-sharding for efficient record search
AssigneeAncestry.com Operations Inc.
InventorsGann Bierner, Robert Weis
Life of this patent
Estimating the term…
Abstract
Data-sharding systems and/or methods for cost- and time-efficient record search are described. Data-sharding embodiments utilize a name-sharding dimension, optionally in combination with one or more additional dimensions such as record type and year, to reduce latency and reduce search-associated costs. The data-sharding systems and methods embodiments utilize an optimization algorithm to determine a distribution of records related to names. The optimization algorithm may use a three-character prefix for surnames in records to distribute shards across documents, with specific shards relating to no-name and multi-name records allocated.
Claims20
A computer-implemented method, comprising:
- receiving a collection of data that includes a plurality of names of individuals;
- extracting the names of the individuals as a searchable field from the collection of data;
- transforming the names of the individuals in the searchable field to prefixes, wherein transforming the names of the individuals to prefixes comprises:
- coding the prefixes into phonetic spellings, wherein a particular prefix corresponds to a particular phonetic spelling,
- identifying a set of the names that are mappable to the particular phonetic spelling, and
- associating the set of the names that are mappable to the particular phonetic spelling to the particular prefix;
- assigning the prefixes to the collection of data;
- generating a distribution of the prefixes based in part on query frequencies of the prefixes including the phonetic spellings corresponding to the prefixes, wherein the query frequencies of the prefixes are determined by tracking numbers of incoming queries associated with respective prefixes, and the incoming queries include queries with phonetic matches;
- storing the collection of data to a plurality of shards based on the distribution of the prefixes;
- and
- indexing the data in the collection stored on the plurality of shards of a database at least partially based on the names of the individuals that are transformed to the prefixes, the indexing comprising associating the prefixes with corresponding shards in a table.
8 more elements
A system comprising:
- a processor;
- and
- memory coupled to the processor, the memory configured to store code comprising instructions, wherein the instructions, when executed by the processor, cause the processor to:
- receive a collection of data that includes a plurality of names of individuals;
- extract the names of the individuals as a searchable field from the collection of data;
- transform the names of the individuals in the searchable field to prefixes, wherein transforming the names of the individuals to prefixes comprises:
- coding the prefixes into phonetic spellings, wherein a particular prefix corresponds to a particular phonetic spelling,
- identifying a set of the names that are mappable to the particular phonetic spelling, and
- associating the set of the names that are mappable to the particular phonetic spelling to the particular prefix;
- assign the prefixes to the collection of data;
- generate a distribution of the prefixes based in part on query frequencies of the prefixes including the phonetic spellings corresponding to the prefixes, wherein the query frequencies of the prefixes are determined by tracking numbers of incoming queries associated with respective prefixes, and the incoming queries include queries with phonetic matches;
- store the collection of data to a plurality of shards based on the distribution of the prefixes;
- and
- index the data of the collection stored on the plurality of shards of a database at least partially based on the names of the individuals that are transformed to the prefixes, the indexing comprising associating the prefixes with corresponding shards in a table.
11 more elements
A non-transitory computer readable storage medium configured to store code comprising instructions, wherein the instructions, when executed by a processor, cause the processor to:
- receive a collection of data that includes a plurality of names of individuals;
- extract the names of the individuals as a searchable field from the collection of data;
- transform the names of the individuals in the searchable field to prefixes, wherein transforming the names of the individuals to prefixes comprises:
- coding the prefixes into phonetic spellings, wherein a particular prefix corresponds to a particular phonetic spelling,
- identifying a set of the names that are mappable to the particular phonetic spelling, and
- associating the set of the names that are mappable to the particular phonetic spelling to the particular prefix;
- assign the prefixes to the collection of data;
- generate a distribution of the prefixes based in part on query frequencies of the prefixes including the phonetic spellings corresponding to the prefixes, wherein the query frequencies of the prefixes are determined by tracking numbers of incoming queries associated with respective prefixes, and the incoming queries include queries with phonetic matches;
- store the collection of data to a plurality of shards based on the distribution of the prefixes;
- and
- index the data of the collection stored on the plurality of shards of a database at least partially based on the names of the individuals that are transformed to the prefixes, the indexing comprising associating the prefixes with corresponding shards in a table.
8 more elements
Dependencies are inferred from the claim text.