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.