Quicker Queries: Queaps and the Queueish Property

John Howat

Distribution-sensitive data structures take advantage of underlying patterns in the distribution of queries in order to speed up query times. One such property is the working set property, which loosely states that queries that were made recently should be fast if made again soon. Iacono and Langerman present a complementary property: queries that have not been made recently should be fast, a property termed the queueish property. A heap with the queueish property is presented, as is a dictionary data structure that supports a slightly weaker version of the queueish property.