Content deleted Content added
m Typo/general fixes, replaced: ''de-facto'' → ''de facto'' |
Artoria2e5 (talk | contribs) No edit summary Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 58:
This approach needs linear time in {{mvar|n}} for construction, and constant evaluation time. The representation size is in {{math|''O''(''n'')}}, and depends on the achieved range. For example, with {{math|''m'' {{=}} 1.23''n''}} {{harvtxt|Belazzougui|Botelho|Dietzfelbinger|2009}} achieved a representation size between 3.03 bits/key and 1.40 bits/key for their given example set of 10 million entries, with lower values needing a higher computation time. The space lower bound in this scenario is 0.88 bits/key.<ref name="CHD" />
{{missing information|section|RecSplit & "fingerprinting" [https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 recsplit paper]}}
===Pseudocode===
'''algorithm''' ''hash, displace, and compress'' '''is'''
| |||