Name
Abstract | ||
|---|---|---|
In the preprocessing model for uncertain data we are given a set of regions R which model the uncertainty associated with an unknown set of points P. In this model there are two phases: a preprocessing phase, in which we have access only to R, followed by a reconstruction phase, in which we have access to points in P at a certain retrieval cost C per point. We study the following algorithmic question: how fast can we construct the pareto front of P in the preprocessing model? We show that if R is a set of pairwise-disjoint axis-aligned rectangles, then we can preprocess R to reconstruct the Pareto front of P efficiently. To refine our algorithmic analysis, we introduce a new notion of algorithmic optimality which relates to the entropy of the uncertainty regions. Our proposed uncertainty-region optimality falls on the spectrum between worst-case optimality and instance optimality. We prove that instance optimality is unobtainable in the preprocessing model, whenever the classic algorithmic problem reduces to sorting. Our results are worst-case optimal in the preprocessing phase; in the reconstruction phase, our results are uncertainty-region optimal with respect to real RAM instructions, and instance optimal with respect to point retrievals. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/1.9781611977073.122 | ACM-SIAM Symposium on Discrete Algorithms (SODA) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ivor van der Hoog | 1 | 1 | 2.51 |
| Irina Kostitsyna | 2 | 33 | 18.08 |
| Maarten Löffler | 3 | 551 | 62.87 |
| Bettina Speckmann | 4 | 876 | 79.40 |