Composable Coreset

Select Connection: INPUT[inlineListSuggester(optionQuery(#permanent_note), optionQuery(#literature_note), optionQuery(#fleeting_note)):connections]

Definition

Partition $P$ into subsets $P_1,P_2,...,P_l$ and extract a small coreset $T_i$ from each $P_i$. Run best known sequential algorithm for ${\Pi }_i$ on $T={\cup }_{i=1}^l{T}_i$

Effective if:

• each $T_i$ can be extracted efficiently from $P_i$ in parallel
• final coreset $T$ is still small and the solution on $T$ is a good solution for $\Pi$ with respect to the entire input $P$