# US 11,442,792 B2 · Systems and methods for dynamic partitioning in distributed environments > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,792 B2 - Document ID: US11442792B2 - Status: Granted - Kind: B2 - Application number: 17/122,849 - Filed: 2020-12-15 - Published: 2021-04-08 - Granted: 2022-09-13 - Earliest claimed: 2016-06-22 - Assignees: Yahoo Assets LLC - Applicants: Yahoo Assets LLC - Inventors: Thu R. Kyaw; Jonathan Ji; Saad Mufti; Sudhir Achuthan; Sang Chul Song - Web page: https://patentgrep.com/patent/US11442792B2 ## CPC - G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)} - G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)} - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/285: {Clustering or classification} - G06F 2209/5017: Task decomposition - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods, systems, and computer-readable media are disclosed for dynamic partitioning in distributed computing environments. One method includes: receiving a first data set and a second data set; mapping the first data set into a first set of key-value pairs; mapping the second data set into a second set of key-value pairs; estimating, using a sketch, a frequency count for each key based on the first set of key-value pairs and the second set of key-value pairs; determining whether the estimated frequency count for each key is greater than or equal to a predetermined threshold; and partitioning the key when the estimated frequency count for the key is greater than or equal to the predetermined threshold. ## Claims ### Claim 1 A computer-implemented method for dynamic partitioning in a distributed computing system, the method comprising: receiving, at a master node of the distributed computing system, a first data set and a second data set; distributing, by the master node, the first data set and the second data set to a plurality of slave nodes of the distributed computing system; mapping, by the plurality of slave nodes, the first data set into a first set of key-value pairs and the second data set into a second set of key-value pairs; estimating, by the plurality of slave nodes, using a local frequency counter of each of the plurality of slave nodes, a frequency count for each key in the first set of key-value pairs and the second set of key-value pairs; determining, by the plurality of slave nodes, whether the estimated frequency count for each key is greater than or equal to a predetermined threshold; and partitioning, by the plurality of slave nodes, each key when the estimated frequency count for the respective key is greater than or equal to the predetermined threshold. ### Claim 2 (depends on 1) The method of claim 1, further comprising: determining an updated frequency count for each key based on a global frequency count for each key from a global frequency counter and the estimated frequency count for each key; and transmitting, by the plurality of slave nodes to the master node, the updated frequency count for each key. ### Claim 3 (depends on 1) The method of claim 1, wherein the local frequency counter utilizes at least one of a lossy algorithm or a count-min sketch. ### Claim 4 (depends on 1) The method of claim 1, further comprising: grouping, by the plurality of slave nodes, values of the key-value pairs by each key to form a set of values grouped by each key. ### Claim 5 (depends on 4) The method of claim 4, further comprising: reducing, by the plurality of slave nodes, the values of each set of values grouped by each key into a set of pairs. ### Claim 6 (depends on 1) The method of claim 1, wherein estimating the frequency count for each key further comprises estimating a number of distinct values for each key in the first and second set of key-value pairs. ### Claim 7 (depends on 1) The method of claim 1, wherein partitioning, by the plurality of slave nodes, each key when the estimated frequency count for the respective key is greater than or equal to the predetermined threshold further comprises creating two or more sub-keys for the respective key. ### Claim 8 A system for dynamic partitioning in distributed computing environments, the system including: a data storage device that stores instructions for dynamic partitioning in distributed computing environments; and at least one processor configured to execute the instructions to perform a method including: receiving, by a master node of the system, a first data set and a second data set; distributing, by the master node, the first data set and the second data set to the plurality of slave nodes of the system; mapping, by the plurality of slave nodes, the first data set into a first set of key-value pairs and the second data set into a second set of key-value pairs; estimating, using a local frequency counter of each of the plurality of slave nodes, a frequency count for each key in the first set of key-value pairs and the second set of key-value pairs; determining, by the plurality of slave nodes, whether the estimated frequency count for each key is greater than or equal to a predetermined threshold; and partitioning, by the plurality of slave nodes, each key when the estimated frequency count for the respective key is greater than or equal to the predetermined threshold. ### Claim 9 (depends on 8) The system of claim 8, wherein the at least one processor is further configured to execute the instructions to perform the method including: determining an updated frequency count for each key based on a global frequency count for each key from a global frequency counter and the estimated frequency count for each key; and transmitting, by the plurality of slave nodes to the master node, the updated frequency count for each key. ### Claim 10 (depends on 8) The system of claim 8, wherein the local frequency counter utilizes at least one of a lossy algorithm or a count-min sketch. ### Claim 11 (depends on 8) The system of claim 8, wherein the at least one processor is further configured to execute the instructions to perform the method including: grouping, by the plurality of slave nodes, values of the key-value pairs by each key to form a set of values grouped by each key. ### Claim 12 (depends on 11) The system of claim 11, wherein the at least one processor is further configured to execute the instructions to perform the method including: reducing, by the plurality of slave nodes, the values of each set of values grouped by each key into a set of pairs. ### Claim 13 (depends on 8) The system of claim 8, wherein estimating the frequency count for each key further comprises estimating a number of distinct values for each key in the first and second set of key-value pairs. ### Claim 14 (depends on 8) The system of claim 8, wherein partitioning each key when the estimated frequency count for the respective key is greater than or equal to the predetermined threshold further comprises creating two or more sub-keys for the respective key. ### Claim 15 A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method for dynamic partitioning in distributed computing environments, the method including: receiving, at a master node, a first data set and a second data set; distributing, by the master node, the first data set and the second data set to a plurality of slave nodes; mapping, by the plurality of slave nodes, the first data set into a first set of key-value pairs and the second data set into a second set of key-value pairs; estimating, by the plurality of slave nodes, using a local frequency counter of each of the plurality of slave nodes, a frequency count for each key in the first set of key-value pairs and the second set of key-value pairs; determining, by the plurality of slave nodes, whether the estimated frequency count for each key is greater than or equal to a predetermined threshold; and partitioning, by the plurality of slave nodes, each key when the estimated frequency count for the respective key is greater than or equal to the predetermined threshold. ### Claim 16 (depends on 15) The computer-readable medium of claim 15, further comprising: determining an updated frequency count for each key based on a global frequency count for each key from a global frequency counter and the estimated frequency count for each key; and transmitting, by the plurality of slave nodes to the master node, an updated frequency count for each key. ### Claim 17 (depends on 15) The computer-readable medium of claim 15, wherein the local frequency counter utilizes at least one of a lossy algorithm or a count-min sketch. ### Claim 18 (depends on 15) The computer-readable medium of claim 15, further comprising: grouping, by the plurality of slave nodes, values of the key-value pairs by each key to form a set of values grouped by each key. ### Claim 19 (depends on 18) The computer-readable medium of claim 18, further comprising: reducing, by the plurality of slave nodes, the values of each set of values grouped by each key into a set of pairs. ### Claim 20 (depends on 15) The computer-readable medium of claim 15, wherein estimating the frequency count for each key further comprises estimating a number of distinct values for each key in the first and second set of key-value pairs.