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
170
EliasFano
10th StringBeginnersでの発表資料
Shunsuke Kanda
November 30, 2019
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
0
8
トライとダブル配列の基礎
kampersanda
0
630
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
140
ICDM2020
kampersanda
0
120
SIGSPATIAL20
kampersanda
0
90
Fast Succinct Trie
kampersanda
1
560
StringBeginners#1
kampersanda
2
150
Ph.D. Thesis
kampersanda
0
360
Other Decks in Research
See All in Research
Accurate Method and Variable Tracking in Commit History
tsantalis
0
300
Rの機械学習フレームワークの紹介〜tidymodelsを中心に〜 / machine_learning_with_r2024
s_uryu
0
260
【論文紹介】Large Language Models Sensitivity to The Order of Options in Multiple-Choice Questions
ichiroex
0
110
Julia Tokyo #11 トーク: 「Juliaで歩く自動微分」
abap34
2
1.3k
Equivalence of Geodesics and Importance Weighting from the Perspective of Information Geometry
mkimura
0
140
メタ動画データセットによる動作認識の現状と可能性
yuyay
0
250
LLMマルチエージェントを俯瞰する
masatoto
26
17k
訓練データ作成のためのCloudCompareを利用した点群の手動ラベリング
kentaitakura
0
590
Bridging Continuous and Discrete Spaces: Interpretable Sentence Representation Learning via Compositional Operations
rudorudo11
0
160
CSC590 Lecture 01
javiergs
PRO
0
130
Deep State Space Models 101 / Mamba
kurita
9
3.8k
Cross-Media Information Spaces and Architectures
signer
PRO
0
130
Featured
See All Featured
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
22
1.6k
Automating Front-end Workflow
addyosmani
1357
200k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
221
21k
Bootstrapping a Software Product
garrettdimon
PRO
302
110k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
323
20k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
26
2.3k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
275
13k
Designing the Hi-DPI Web
ddemaree
276
33k
Stop Working from a Prison Cell
hatefulcrawdad
266
19k
Building Effective Engineering Teams - LeadDev
addyosmani
33
1.9k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
1
130
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
84
45k
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