36th Annual Symposium on Foundations of Computer Science (FOCS'95) Sublogarithmic searching without multiplications Milwaukee, Wisconsin October 23-October 25 ISBN: 0-8186-7183-1
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(/spl radic/(logn)) worst-case time and range queries in O(/spl radic/(logn)+size of output) worst-case time. The operations rely on AC/sup 0/ 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 /spl Theta/O(logn) searches in O(lognloglogn) time.
Index Terms:
computational complexity; tree data structures; search problems; sublogarithmic searching; unit-cost RAM; worst-case time; data structure; search; insert; delete; nearest neighbour
Citation:
A. Andersson, "Sublogarithmic searching without multiplications," focs, pp.655, 36th Annual Symposium on Foundations of Computer Science (FOCS'95), 1995 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb