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
来源：
SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 05期
关键词：
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
    DIETZFELBINGER, M
    KARLIN, A
    MEHLHORN, K
    AUFDERHEIDE, FM
    ROHNERT, H
    TARJAN, RE
    [J]. 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
    ELIAS, P
    [J]. JOURNAL OF THE ACM, 1974, 21 (02) : 246 - 260
  • [9] COMPLEXITY OF SOME SIMPLE RETRIEVAL PROBLEMS
    ELIAS, P
    FLOWER, RA
    [J]. JOURNAL OF THE ACM, 1975, 22 (03) : 367 - 379
  • [10] IMPLICIT O(1) PROBE SEARCH
    FIAT, A
    NAOR, M
    [J]. SIAM JOURNAL ON COMPUTING, 1993, 22 (01) : 1 - 10
123