Minimal indices for predecessor search

摘要: We give a new predecessor data structure which improves upon the index size of P?trascu-Thorup structures, reducing from O ( n w 4 / 5 ) bits to log ? bits, with optimal probe complexity. Alternatively, our can be viewed as matching space complexity (probe-suboptimal) z-fast trie Belazzougui et al. Thus, we get best both approaches respect count and size. The penalty pay is an extra inter-register operations. Our also used solve weak prefix search problem, known for any such structure.The technical contributions include highly efficient single word indices, out-degree (compared 1 fusion tree node). To construct these indices device bit selectors which, believe, are independent interest.