Abstract: A new dynamic InterpolationSearch (IS) data structure is
presented that achieves O(log log n) search time with high probability
on unknown continuous or even discrete input distributions with mea-
surable probability of key collisions, including power law and Binomial
distributions. No such previous result holds for IS when the probabil-
ity of key collisions is measurable. Moreover, our data structure exhibits
O(1) expected search time with high probability for a wide class of in-
put distributions that contains all those for which o(log log n) expected
search time was previously known.
Abstract: We present the interpolationsearch B-tree (ISB-tree), a new cache-aware indexing scheme
that supports update operations (insertions and deletions) in O(1) worst-case block
transfers and search operations in O(logB logn) expected block transfers, where B
represents the disk block size and n denotes the number of stored elements. The expected
search bound holds with high probability for a large class of (unknown) input distributions.
The worst-case search bound of our indexing scheme is O(logB n) block transfers. Our
update and expected search bounds constitute a considerable improvement over the
O(logB n) worst-case block transfer bounds for search and update operations achieved
by the B-tree and its numerous variants. This is also verified by an accompanying
experimental study.
Abstract: We present the interpolationsearch tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in O(1) worst-case (w.c.) block transfers and search operations in O(logB log n) expected block transfers, where B represents the disk block size and n denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The w.c. search bound of our indexing scheme is O(logB n) block transfers. Our update and expected search bounds constitute a considerable improvement over the O(logB n) w.c. block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also suggested by a set of preliminary experiments we have carried out. Our indexing scheme is based on an externalization of a main memory data structure based on interpolationsearch.
