Augmented map (original) (raw)
In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity (i.e., forms a monoid). We extend the definition of the associative function as follows:
| Property | Value |
|---|---|
| dbo:abstract | In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity (i.e., forms a monoid). We extend the definition of the associative function as follows: Then the augmented value of an ordered map is defined as follows: Accordingly, an augmented map can be formally defined as a seven-tuple . For example, an augmented map with integral keys and values, on which the augmented value is defined as the sum of all values in the map, is defined as: As an abstract data type, the augmented map is often used to model problems and serves as an abstraction with a useful interface. It is designed for supporting fast range sums, which means to quickly return the augmented value of all entries in a certain key range. (en) |
| dbo:wikiPageID | 58463358 (xsd:integer) |
| dbo:wikiPageLength | 10040 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093145663 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Interval_tree dbr:Inverted_index dbr:Range_tree dbr:Monoid dbr:Computer_science dbr:PAM_library dbr:Abstract_data_type dbc:Data_types dbr:Associativity dbc:Abstract_data_types dbr:Associative_array dbc:Data_structures dbr:Identity_(mathematics) dbr:Associative dbr:Sweepline_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Notelist dbt:Reflist dbt:Data_types dbt:Data_structures |
| dct:subject | dbc:Data_types dbc:Abstract_data_types dbc:Data_structures |
| rdfs:comment | In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity (i.e., forms a monoid). We extend the definition of the associative function as follows: (en) |
| rdfs:label | Augmented map (en) |
| owl:sameAs | wikidata:Augmented map https://global.dbpedia.org/id/9GWEo |
| prov:wasDerivedFrom | wikipedia-en:Augmented_map?oldid=1093145663&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Augmented_map |
| is dbo:wikiPageWikiLink of | dbr:PAM_library dbr:Join-based_tree_algorithms |
| is foaf:primaryTopic of | wikipedia-en:Augmented_map |