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.

PropertyValue
dbpprop:abstract
  • 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 counterpart.
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • 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.
rdfs:label
  • Implicit data structure
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of