In computer science, a y-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n) space, where n is the number of stored values and M is the maximum value in the domain. The structure was proposed by Dan Willard in 1982 to decrease the O(n log M) space used by an x-fast trie.
| Property | Value |
|---|---|
| dbo:abstract |
|
| dbo:thumbnail | |
| dbo:wikiPageExternalLink | |
| dbo:wikiPageID |
|
| dbo:wikiPageLength |
|
| dbo:wikiPageRevisionID |
|
| dbo:wikiPageWikiLink | |
| dbp:deleteAvg |
|
| dbp:insertAvg |
|
| dbp:inventedBy | |
| dbp:inventedYear |
|
| dbp:name |
|
| dbp:searchAvg |
|
| dbp:spaceAvg |
|
| dbp:type | |
| dbp:wikiPageUsesTemplate | |
| dcterms:subject | |
| gold:hypernym | |
| rdf:type | |
| rdfs:comment |
|
| rdfs:label |
|
| owl:sameAs | |
| prov:wasDerivedFrom | |
| foaf:depiction | |
| foaf:isPrimaryTopicOf | |
| is dbo:wikiPageWikiLink of | |
| is foaf:primaryTopic of |
