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
190
EliasFano
10th StringBeginnersでの発表資料
Shunsuke Kanda
November 30, 2019
Tweet
Share
More Decks by Shunsuke Kanda
See All by Shunsuke Kanda
Leveraging LLMs for Unsupervised Dense Retriever Ranking (SIGIR 2024)
kampersanda
2
280
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.2k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
2
340
トライとダブル配列の基礎
kampersanda
0
990
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
190
ICDM2020
kampersanda
0
180
SIGSPATIAL20
kampersanda
0
140
Fast Succinct Trie
kampersanda
1
650
Other Decks in Research
See All in Research
チュートリアル:Mamba, Vision Mamba (Vim)
hf149
6
2k
2024/10/30 産総研AIセミナー発表資料
keisuke198619
1
410
研究の進め方 ランダムネスとの付き合い方について
joisino
PRO
58
23k
機械学習でヒトの行動を変える
hiromu1996
1
450
文献紹介:A Multidimensional Framework for Evaluating Lexical Semantic Change with Social Science Applications
a1da4
1
250
[依頼講演] 適応的実験計画法に基づく効率的無線システム設計
k_sato
0
220
Weekly AI Agents News! 9月号 論文のアーカイブ
masatoto
1
170
QGISハンズオン事に質問のあったProjectのGeoPackageへの保存方法についての、補足の資料です。
wata909
0
110
Bluesky Game Dev
trezy
0
100
The many faces of AI and the role of mathematics
gpeyre
1
1.5k
研究を支える拡張性の高い ワークフローツールの提案 / Proposal of highly expandable workflow tools to support research
linyows
0
260
Poster: Feasibility of Runtime-Neutral Wasm Instrumentation for Edge-Cloud Workload Handover
chikuwait
0
280
Featured
See All Featured
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
28
2.2k
Intergalactic Javascript Robots from Outer Space
tanoku
270
27k
Fontdeck: Realign not Redesign
paulrobertlloyd
82
5.3k
Fashionably flexible responsive web design (full day workshop)
malarkey
406
66k
Art, The Web, and Tiny UX
lynnandtonic
298
20k
YesSQL, Process and Tooling at Scale
rocio
170
14k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.6k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
3
240
Gamification - CAS2011
davidbonilla
80
5.1k
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
What's in a price? How to price your products and services
michaelherold
244
12k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
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