Implicit data structure

Implicit data structure

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. Implicit data structures are frequently also succinct data structures.

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.

Implicit Data Structures

Examples of implicit data structures include
*Heap
*Beap

Further Research

To probe further see works of [http://photon.poly.edu/~hbr/ Hervé Brönnimann] , [http://www.cs.uwaterloo.ca/~imunro/ J. Ian Munro] , [http://www.cs.purdue.edu/people/gnf Greg Frederickson ]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Data model — Overview of data modeling context: A data model provides the details of information to be stored, and is of primary use when the final product is the generation of computer software code for an application or the preparation of a functional… …   Wikipedia

  • Implicit address — An implicit address structure and technique are disclosed for rapidly accessing storage registers by eliminating the need for generating a separate address before referencing the register. A structure is provided for generating an address… …   Wikipedia

  • Implicit solvation — (sometimes known as continuum solvation) is a method of representing solvent as a continuous medium instead of individual “explicit” solvent molecules most often used in molecular dynamics simulations and in other applications of molecular… …   Wikipedia

  • Data-flow analysis — is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program s control flow graph (CFG) is used to determine those parts of a program to which a particular value assigned… …   Wikipedia

  • social structure — structure (def. 9). [1825 35] * * * Introduction       in sociology, the distinctive, stable arrangement of institutions whereby human beings in a society interact and live together. Social structure is often treated together with the concept of… …   Universalium

  • The Structure and Interpretation of the Computer Science Curriculum — is a monograph published in 2004 [Journal of Functional Programming, Volume 14 , Issue 4 (July 2004) Pages: 365 378 ] by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi comparing and contrasting the pedagogical… …   Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Binary heap — Example of a complete binary max heap Example of a complete binary min heap A binary …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”