Title :
Sublogarithmic searching without multiplications
Author_Institution :
Dept. of Comput. Sci., Lund Univ.
Abstract :
We show that a unit-cost RAM with word length w can maintain an ordered set of w-bit integers (or binary strings) under the operations search, insert, delete, nearest neighbour in O(√(logn)) worst-case time and range queries in O(√(logn)+size of output) worst-case time. The operations rely on AC0 instructions only, thereby solving an open problem posed by Fredman and Willard. The data structure is simple. We also present a static data structure that can process a set of ΘO(logn) searches in O(lognloglogn) time
Keywords :
computational complexity; search problems; tree data structures; data structure; delete; insert; nearest neighbour; search; sublogarithmic searching; unit-cost RAM; worst-case time; Binary search trees; Computer science; Costs; Data structures; Read-write memory; Sorting; Table lookup; Tree data structures;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492667