@techreport{TD:100274,
	att_abstract={{We consider the dictionary problem in external memory and improve the
update time of the well-known emph{buffer tree} by roughly a
logarithmic factor. For any $lambda ge max { lglg n, log_{M/B}
(n/B) }$, we can support updates in time $O(frac{lambda}{B})$ and
queries in time $O(log_lambda n)$. We also present a lower bound in
the cell-probe model showing that our data structure is optimal.

In the RAM, hash tables have been use to solve the dictionary problem
faster than binary search for more than half a century. By contrast,
our data structure is the first to beat the comparison barrier in
external memory. Ours is also the first data structure to depart
convincingly from the emph{indivisibility} paradigm.
}},
	att_authors={mp6431},
	att_categories={C_CCF.1},
	att_copyright={{ACM}},
	att_copyright_notice={{(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of teh ACM/SIAM Symposium on Discrete Algorithms (SODA), 2012 {{, 2012-01-17}}.
}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={},
	att_techdoc={true},
	att_techdoc_key={TD:100274},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100274_DS1_2010-11-05T19:53:38.380Z.pdf},
	author={Mihai Patrascu and John Iacono},
	institution={{Proceedings of teh ACM/SIAM Symposium on Discrete Algorithms (SODA), 2012}},
	month={January},
	title={{Using Hashing to Solve the Dictionary Problem (In External Memory)}},
	year=2012,
}