# US 12,222,963 B2 · Data-sharding for efficient record search > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,963 B2 - Document ID: US12222963B2 - Status: Granted - Kind: B2 - Application number: 17/871,427 - Filed: 2022-07-22 - Published: 2023-01-26 - Granted: 2025-02-11 - Earliest claimed: 2021-07-23 - Assignees: Ancestry.com Operations Inc. - Applicants: Ancestry.com Operations Inc. - Inventors: Gann Bierner; Robert Weis - Web page: https://patentgrep.com/patent/US12222963B2 ## CPC - G06F 16/2228: {Indexing structures} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases} - G06F 16/254: {Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses} - G06F 16/951: Indexing; Web crawling techniques - G06F 40/232: Orthographic correction, e.g. spell checking or vowelisation - G06F 40/274: Converting codes to words; Guess-ahead of partial word inputs - G06F 40/295: Named entity recognition - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, the method further comprising searching pertinent shards of the plurality of shards upon receiving a search query. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein searching pertinent shards of the plurality of shards upon receiving a search query comprises: extracting at least one searchable field from the search query; transforming the extracted at least one searchable field to at least one prefix; identifying a shard corresponding to the at least one prefix; and searching the searchable field from the identified shard. ### Claim 4 (depends on 2) The computer-implemented method of claim 2, further comprising: mapping prefixes to phonetic spellings; determining that the search query includes a phonetic spelling; mapping the phonetic spelling to at least one prefix; identifying a shard corresponding to the at least one prefix; and searching the searchable field from the identified shard. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the searchable field includes a surname. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the prefixes are three-character prefixes. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, wherein the distribution includes categories of shards, including at least one of a no-name shard, a multi-name shard, or a single-name shard. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein the transforming the extracted field includes normalizing surnames. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, further comprising extracting at least one of a surname field, a record type field, or a year field as another searchable field. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the database is sharded previously according to record type or year. ### Claim 11 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. ### Claim 12 (depends on 11) The system of claim 11, wherein the instructions, when executed, further cause the processor to search only pertinent shards of the plurality of shards upon receiving a search query. ### Claim 13 (depends on 12) The system of claim 12, wherein searching only pertinent shards of the plurality of shards upon receiving a search query comprises: extracting at least one searchable field from the search query; transforming the extracted at least one searchable field to at least one prefix; identifying a shard corresponding to the at least one prefix; and searching the searchable field from the identified shard. ### Claim 14 (depends on 12) The system of claim 12, wherein the instructions, when executed, further cause the processor to: map prefixes to phonetic spellings; determine that the search query includes a phonetic spelling; map the phonetic spelling to at least one prefix; identify a shard corresponding to the at least one prefix; and search the searchable field from the identified shard. ### Claim 15 (depends on 11) The system of claim 11, wherein the at least one searchable field is a surname. ### Claim 16 (depends on 11) The system of claim 11, wherein the prefixes are three-character prefixes. ### Claim 17 (depends on 11) The system of claim 11, wherein the distribution includes categories of shards, including at least one of a no-name shard, a multi-name shard, or a single-name shard. ### Claim 18 (depends on 11) The system of claim 11, wherein the transforming the extracted field includes normalizing surnames. ### Claim 19 (depends on 11) The system of claim 11, wherein the instructions, when executed, further cause the processor to: extract at least one of a surname field, a record type field, or a year field as another searchable field. ### Claim 20 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.