Sublogarithmic searching without multiplications
- 19 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 655-663
- https://doi.org/10.1109/sfcs.1995.492667
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(/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.Keywords
This publication has 9 references indexed in Scilit:
- Sorting in linear time?Published by Association for Computing Machinery (ACM) ,1995
- Trans-dichotomous algorithms for minimum spanning trees and shortest pathsJournal of Computer and System Sciences, 1994
- Lower bounds for union-split-find related problems on random access machinesPublished by Association for Computing Machinery (ACM) ,1994
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- New trie data structures which support very fast search operationsJournal of Computer and System Sciences, 1984
- Data Structures and Algorithms 1Published by Springer Nature ,1984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Preserving order in a forest in less than logarithmic time and linear spaceInformation Processing Letters, 1977
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976