Implicit data structure
From Wikipedia, the free encyclopedia
In computer science, an implicit data structure is a data structure that uses very little memory besides the actual data elements. 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” is vague and can mean from O(1) to O(log n) extra space.
Although one may argue that disk space is no longer a problem and we should not concern ourselves with improving space utilization, 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 the less dependence is on slow I/O devices. Hence, 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 counter part.
[edit] Implicit Data Structures
Examples of implicit data structures include
[edit] Further Research
To probe further see works of Hervé Brönnimann, J. Ian Munro, Greg Frederickson
 |
This computer-related article is a stub. You can help Wikipedia by expanding it. |
