Invention Grant
- Patent Title: Communication and message-efficient protocol for computing the intersection between different sets of data
- Patent Title (中): 通信和消息高效协议,用于计算不同数据集之间的交集
-
Application No.: US15064187Application Date: 2016-03-08
-
Publication No.: US09438704B2Publication Date: 2016-09-06
- Inventor: David P. Woodruff , Grigory Yaroslavtsev
- Applicant: International Business Machines Corporation
- Applicant Address: US NY Armonk
- Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION
- Current Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION
- Current Assignee Address: US NY Armonk
- Agency: Cantor Colburn LLP
- Main IPC: G06F7/04
- IPC: G06F7/04 ; G06F17/30 ; H04L29/06 ; H04L29/08

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.
Public/Granted literature
Information query