Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
EliasFano
Search
Shunsuke Kanda
November 30, 2019
Research
1
180
EliasFano
10th StringBeginnersでの発表資料
Shunsuke Kanda
November 30, 2019
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.1k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
1
300
トライとダブル配列の基礎
kampersanda
0
890
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
170
ICDM2020
kampersanda
0
160
SIGSPATIAL20
kampersanda
0
130
Fast Succinct Trie
kampersanda
1
620
StringBeginners#1
kampersanda
2
160
Other Decks in Research
See All in Research
SSII2024 [OS1] 画像認識におけるモデル・データの共進化
ssii
PRO
0
510
いしかわ暮らしセミナー~移住にまつわるお金の話~
matyuda
0
130
MIRU2024チュートリアル「様々なセンサやモダリティを用いたシーン状態推定」
miso2024
3
2.1k
Matching 2D Images in 3D: Metric Relative Pose from Metric Correspondences
sgk
1
290
「並列化時代の乱数生成」
abap34
3
760
Y.Morita_20240726_JBUG_Fukuoka#18
ymorita613
0
250
[CV勉強会@関東 CVPR2024] Visual Layout Composer: Image-Vector Dual Diffusion Model for Design Layout Generation / kantocv 61th CVPR 2024
shunk031
1
380
snlp2024_multiheadMoE
takase
0
390
工学としてのSRE再訪 / Revisiting SRE as Engineering
yuukit
19
10k
尺度開発における質的研究アプローチ(自主企画シンポジウム7:認知行動療法における尺度開発のこれから)
litalicolab
0
310
第 2 部 11 章「大規模言語モデルの研究開発から実運用に向けて」に向けて / MLOps Book Chapter 11
upura
0
310
Weekly AI Agents News! 6月号 論文のアーカイブ
masatoto
1
170
Featured
See All Featured
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
167
49k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
25
1.8k
A Philosophy of Restraint
colly
203
16k
Building Better People: How to give real-time feedback that sticks.
wjessup
362
19k
Why You Should Never Use an ORM
jnunemaker
PRO
53
9k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
13
1.8k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
131
33k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
28
9k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
26
2k
KATA
mclloyd
29
13k
Learning to Love Humans: Emotional Interface Design
aarron
272
40k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
41
9.2k
Transcript
EliasFano 10th StringBeginners → Kanda →
K and A → K & A → K ampersand A →
⟫ × "$& n '% S[0,n) × i.e.,
S[i-1] ≤ S[i] for each 0 < i < n ⟫ ! × Access / Predecessor / Successor ( × #( 2 0 1 2 3 4 5 6 7 S 2 7 18 28 42 43 44 59 Access(4) = 42 Predecessor(10) = 7 Successor(43) = 44
EliasFano 3 S 2 7 18 28 42 43 44
59 000 000 010 011 101 101 101 111 n = 8 u log $ log % & 010 111 010 100 010 011 100 011 2 1 3 1 1 001 100 110 0 0 0 log H = 110 0 10 10 0 1110 0 10 2 0 1 1 0 0 1 3 ( ) L = 010 111 010 100 010 011 100 011 ()
2" + " log ' ( 4 L
= 010 111 010 100 010 011 100 011 H = 110 0 10 10 0 1110 0 10 0 1 2 3 4 5 6 7 S 2 7 18 28 42 43 44 59 EliasFano log ) " " log ' ( " 2" 2 *+, ( ≈ "
2" + " log ' ( "6 ⟫
[0,u) 2 n (,/ (i.e. 4) -) #. % $*0+3 6 5 S 2 4 5 8 9 0010110011 2 45 89 n 5'& 2 u ' ( 1 5!5 3 log ' (
2" + " log ' ( 4 ⟫
[0,u) 1 n *- +& !, # "'.(2 4 6 S 2 4 4 5 8 9 0010011010001010 2 5 ')( ( / 33 (0)) 44 8 9 n 3%$1 u+n Less than half a bit per element away (Quasi-succinct) 2 log ')( ( ≈ " log ')( (
⟫ Access(i) = S[i] ⟫ Predecessor(x) = max{S[i] :
S[i] ≤ x} ⟫ Successor(x) = min{S[i] : S[i] > x} 7 O(1) O(log $ % ) 0 1 2 3 4 5 6 7 S 2 7 18 28 42 43 44 59 Access(4) = 42 Predecessor(10) = 7 Successor(43) = 44
Access&O(1) $ ⟫ &Access(4) = 42 = 101 0102 8
L = 010 111 010 100 010 011 100 011 H = 110 0 10 10 0 1110 0 10 ① !"# $ % i ! Select1 (4) – 4 = 9 – 4 = 5 = 1012 ② !"# % Select1 (i) – i H Select " o(n) Selectb (H, i)&H i ! b # %
SuccessorO(log $ % ) ⟫ Successor(43) = 44 =
101 1002 9 L = 010 111 010 100 010 011 100 011 H = 110 0 10 10 0 1110 0 10 Select0 (4) = 8 Select0 (5) = 12 log $ % = 3 3 × (Select0 (4) – 4) = 12 3 × (Select0 (5) – 5) = 21 101 0112 5 ② O(&'( ) * ) ① &'( * Select
/6 EliasFano7) ⟫ # (;+' AA ×
10%?*& × =98. " × TRIE 2! × 3<5,4!@: -> 10 10 7 5 0 1 4 8 6 9 3 a t e t a a t e c c 2 $A