Name
Abstract | ||
|---|---|---|
A problem arising in statistical data analysis and pat- tern recognition is to find a longest interval free of data points, given a set of data points in the unit interval. We use the inverse length of the empty interval as a pa- rameter in the complexity bounds, since it is small in statistically relevant cases. For sorted point sets we get nearly optimal strategies. While the asymptotic com- plexities are trivial, achieving an optimal number of op- erations appears to be dicult. Constant factors can be of practical interest for huge data sets. We derive de- terministic and randomized upper and lower bounds. Matching bounds and smooth trade-os between the dierent operations (reads, comparisons, subtractions) are open questions. For unsorted point sets, the com- plexity is at least linear. Therefore we also use statistical inference to get approximate solutions in sublinear time. We also point out some extensions to multidimensional analogues of the problems. |
Year | Venue | Keywords |
|---|---|---|
2008 | CCCG | statistical inference,upper and lower bounds |
Field | DocType | Citations |
Data point,Randomized algorithm,Discrete mathematics,Inverse,Data set,Combinatorics,Upper and lower bounds,Unit interval,Statistical inference,Group testing,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 9 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |