# US 9,438,704 B2 · Communication and message-efficient protocol for computing the intersection between different sets of data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,438,704 B2
- Document ID: US9438704B2
- Status: Granted
- Kind: B2
- Application number: 15/064,187
- Filed: 2016-03-08
- Published: 2016-06-16
- Granted: 2016-09-06
- Earliest claimed: 2013-12-16
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: David P. Woodruff; Grigory Yaroslavtsev
- Web page: https://patentgrep.com/patent/US9438704B2

## CPC

- H04L 69/24: Negotiation of communication capabilities
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F 16/40: of multimedia data, e.g. slideshows comprising image and additional audio data (retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70)
- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- H04L 69/166: IP fragmentation; TCP segmentation
- H04L 69/26: {Special purpose or proprietary protocols or architectures (network applications for proprietary or special purpose networking environments H04L67/12)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments relate to data processing. A method includes analyzing a plurality of data items in a relational database, where different portions of the data items are stored in a plurality of servers. The method also includes determining a maximum size of a subset of the data items stored in each of at least two servers among the plurality of servers, calculating a logarithm function based on the maximum size of the subset of the data items in each of the two servers, and calculating a highest number of sequences of communications between the two servers such that when the logarithmic function is iteratively applied, a value of the logarithmic function remains smaller than one. A protocol is then generated between the two servers for performing an intersection operation using the highest number of sequences calculated.

## Claims

### Claim 1

A method comprising:
analyzing a plurality of data items in a relational database, wherein different portions of the data items are stored in a plurality of servers;
determining a maximum size of a subset of the data items stored in each of at least two servers among the plurality of servers;
calculating a logarithm function based on the maximum size of the subset of the data items in each of the at least two servers, wherein the logarithmic function includes an upper bound and a lower bound in its functional calculation;
calculating a highest number of sequences of communications between the at least two servers such that when the logarithmic function is iteratively calculated, a result of the logarithmic function remains smaller than 1, wherein the highest number of sequences is defined as O(k) bits where k is the maximum size of the subset of the data items in each of the at least two servers, wherein the maximum size of the subset of the data items is defined as n and the logarithmic function is defined as O (k log n) bits of communication, wherein the value of n is alterable when at least one of a new data item is added and when an existing data item is removed from the relational database such that O (k log n) is further calculated by the logarithmic function O (log*k) for the at least two servers, wherein the at least two servers deterministically exchange their inputs using only O(k log(n/k)) bits of communication, wherein the at least two servers hash their data items in elements of O(log k)-bit strings, and wherein the at least two servers exchange the hashed values in order to determine which elements are in the intersection of their data items; and
generating a protocol between the at least two servers for performing an intersection operation using the highest number of sequences calculated, wherein the intersection operation determines common data items stored in the at least two servers through communications between the at least two servers such that the number of times the communications are exchanged does not exceed the highest number of sequences calculated, and wherein the intersection operation is used to compute a number of distinct elements in a union of the data items between the at least two servers.