Implicit data structure
 | This article may require copy editing for grammar, style, cohesion, tone, or spelling. (June 2014) |
In computer science, an implicit data structure, stores very little information other than the main data. These storage schemes retain no pointers, represent the file of n k-key records as a simple n by k array n, and thus retrieve much faster. In implicit data structures, the only structural information to be given is to allow the array to grow and shrink as n. No extra information is required. It is called "implicit" because most of the structure of the elements is expressed implicitly by their order. Another term used interchangeably is space efficient. Definitions of “very little” are vague and can mean from O(1) to O(log n) extra space. Everything is accessed in-place, by reading bits at various positions in the data. To achieve optimal coding, we use bits instead of bytes. Implicit data structures are frequently also succinct data structures.
Although it may be argued that disk space is no longer a problem and improving space utilization should not be a priority, the issue that implicit data structures are designed to improve is main memory utilization. Hard disks, or any other means of large data capacity, I/O devices, are orders of magnitudes slower than main memory. Hence, the higher percentage of a task can fit in buffers in main memory, with less dependence on slow I/O devices. Also, if a larger chunk of an implicit data structure fits in main memory, the operations performed on it can be faster, even if the asymptotic running time is not as good as its space-oblivious counterpart. Furthermore, since the CPU-cache is usually much smaller than main memory, implicit data structures can improve cache-efficiency and thus running speed, especially if the method used improves locality.
Implicit data structure for weighted element
For presentation of elements with different weights, several data structures are required. The structure uses one more location besides those required for values of elements. The first structure supports worst case search time in terms of rank of weight of elements with respect to set of weights. If the elements are drawn from uniform distribution, then variation of this structure takes average time. The same result obtains for the data structures in which the intervals between consecutive values have access probabilities.
Examples
Examples of implicit data structures include
Further reading
- See publications of Hervé Brönnimann, J. Ian Munro, Greg Frederickson