Computing optimal k-regret minimizing sets with top-k depth contours
| Autor: | Chester, Sean, Thomo, Alex, Venkatesh, S., Whitesides, Sue |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Regret minimizing sets are a very recent approach to representing a dataset D with a small subset S of representative tuples. The set S is chosen such that executing any top-1 query on S rather than D is minimally perceptible to any user. To discover an optimal regret minimizing set of a predetermined cardinality is conjectured to be a hard problem. In this paper, we generalize the problem to that of finding an optimal k$regret minimizing set, wherein the difference is computed over top-k queries, rather than top-1 queries. We adapt known geometric ideas of top-k depth contours and the reverse top-k problem. We show that the depth contours themselves offer a means of comparing the optimality of regret minimizing sets using L2 distance. We design an O(cn^2) plane sweep algorithm for two dimensions to compute an optimal regret minimizing set of cardinality c. For higher dimensions, we introduce a greedy algorithm that progresses towards increasingly optimal solutions by exploiting the transitivity of L2 distance. Comment: 10 pages, 9 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|