DocumentCode :
3398632
Title :
Sublogarithmic searching without multiplications
Author :
Andersson, A.
Author_Institution :
Dept. of Comput. Sci., Lund Univ.
fYear :
1995
fDate :
23-25 Oct 1995
Firstpage :
655
Lastpage :
663
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
ISSN :
0272-5428
Print_ISBN :
0-8186-7183-1
Type :
conf
DOI :
10.1109/SFCS.1995.492667
Filename :
492667
Link To Document :
بازگشت