Name
Abstract | ||
|---|---|---|
Some new improvements on the Interpolation search are presented. They yield an average-case performance within an additive constant from optimal for uniformly distributed elements. The method is much less sensitive to non-uniform distributions than Interpolation search, and will have almost O(lg lgn) behavior for many distributions. Simulation results show, for example, that an element in a table of 30000 exponentially distributed elements can be found in less than 10 accesses on the average, without using any knowledge of the distribution. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/3-540-19487-8_3 | SWAT |
Keywords | Field | DocType |
interpolation search,uniform distribution,exponential distribution | Stochastic simulation,Discrete mathematics,Laplace distribution,Computer science,Interpolation search,Interpolation,Natural exponential family,Extrapolation,Exponential distribution,Triangular distribution | Conference |
Volume | ISSN | ISBN |
318 | 0302-9743 | 3-540-19487-8 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Christer Mattsson | 2 | 21 | 2.45 |