Distribution-sensitive data structures attempt to exploit patterns in query distributions in order to allow many sequences of queries execute faster than in traditional data structures. In this paper, we survey the history of such data structures, outline open problems in the area, and offer some new results.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-40273-9_10
Bose, P, Howat, J. (John), & Morin, P. (2013). A history of distribution-sensitive data structures. doi:10.1007/978-3-642-40273-9_10