Membership in constant time and almost-minimum space

被引:81
作者
Brodnik, A
Munro, JI
机构
[1] Univ Ljubljana, Inst Math Phys & Mech, Dept Theoret Comp Sci, Ljubljana 1111, Slovenia
[2] Lulea Univ Technol, Dept Comp Sci, SE-97187 Lulea, Sweden
[3] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada
关键词
information retrieval; search strategy; data structures; minimum space; dictionary problem; efficient algorithms hashing; lower bound;
D O I
10.1137/S0097539795294165
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper deals with the problem of storing a subset of elements from the bounded universe M = {0, ..., M - 1} so that membership queries can be performed efficiently. In particular, we introduce a data structure to represent a subset of N elements of M in a number of bits close to the information-theoretic minimum, B = [lg ((M)(N))], and use the structure to answer membership queries in constant time.
引用
收藏
页码:1627 / 1640
页数:14
相关论文
共 23 条
[1]  
BOAS PV, 1990, HDB THEORETICAL COMP, VA, P1
[2]  
BRODNIK A, 1994, LECT NOTES COMPUT SC, V855, P72
[3]  
BRODNIK A, 1995, CS9541 U WAT
[4]  
CHOUEKA Y, 1986, 9TH P ACM SIGIR C PI, P88
[5]  
DIETZFELBINGER M, 1992, LECT NOTES COMPUT SC, V623, P235
[6]   DYNAMIC PERFECT HASHING - UPPER AND LOWER BOUNDS [J].
DIETZFELBINGER, M ;
KARLIN, A ;
MEHLHORN, K ;
AUFDERHEIDE, FM ;
ROHNERT, H ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1994, 23 (04) :738-761
[7]  
DIETZFELBINGER M, 1990, LECT NOTES COMPUT SC, V443, P6, DOI 10.1007/BFb0032018
[8]   EFFICIENT STORAGE AND RETRIEVAL BY CONTENT AND ADDRESS OF STATIC FILES [J].
ELIAS, P .
JOURNAL OF THE ACM, 1974, 21 (02) :246-260
[9]   COMPLEXITY OF SOME SIMPLE RETRIEVAL PROBLEMS [J].
ELIAS, P ;
FLOWER, RA .
JOURNAL OF THE ACM, 1975, 22 (03) :367-379
[10]   IMPLICIT O(1) PROBE SEARCH [J].
FIAT, A ;
NAOR, M .
SIAM JOURNAL ON COMPUTING, 1993, 22 (01) :1-10