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
250
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
390
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.4k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
2
420
トライとダブル配列の基礎
kampersanda
1
1.3k
Binary search with modern processors
kampersanda
33
14k
AIP Open Seminar #6
kampersanda
0
240
ICDM2020
kampersanda
0
210
SIGSPATIAL20
kampersanda
0
200
Fast Succinct Trie
kampersanda
1
720
Other Decks in Research
See All in Research
Sat2City:3D City Generation from A Single Satellite Image with Cascaded Latent Diffusion
satai
3
110
Nullspace MPC
mizuhoaoki
1
150
PhD Defense 2025: Visual Understanding of Human Hands in Interactions
tkhkaeio
1
240
AWSで実現した大規模日本語VLM学習用データセット "MOMIJI" 構築パイプライン/buiding-momiji
studio_graph
2
640
大域マッチングコスト最小化とLiDAR-IMUタイトカップリングに基づく三次元地図生成 / GLIM @ Robotics symposia 2022
koide3
0
100
機械学習と数理最適化の融合 (MOAI) による革新
mickey_kubo
1
380
EarthSynth: Generating Informative Earth Observation with Diffusion Models
satai
3
360
[RSJ25] Enhancing VLA Performance in Understanding and Executing Free-form Instructions via Visual Prompt-based Paraphrasing
keio_smilab
PRO
0
140
Creation and environmental applications of 15-year daily inundation and vegetation maps for Siberia by integrating satellite and meteorological datasets
satai
3
380
Pythonでジオを使い倒そう! 〜それとFOSS4G Hiroshima 2026のご紹介を少し〜
wata909
0
730
超高速データサイエンス
matsui_528
1
150
「どう育てるか」より「どう働きたいか」〜スクラムマスターの最初の一歩〜
hirakawa51
0
920
Featured
See All Featured
Art, The Web, and Tiny UX
lynnandtonic
303
21k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Fireside Chat
paigeccino
40
3.7k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.7k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
52
5.6k
Java REST API Framework Comparison - PWX 2021
mraible
33
8.8k
Fantastic passwords and where to find them - at NoRuKo
philnash
52
3.4k
jQuery: Nuts, Bolts and Bling
dougneiner
64
7.9k
Speed Design
sergeychernyshev
32
1.1k
Git: the NoSQL Database
bkeepers
PRO
431
66k
Bash Introduction
62gerente
615
210k
Large-scale JavaScript Application Architecture
addyosmani
514
110k
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