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
230
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
370
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
390
トライとダブル配列の基礎
kampersanda
1
1.2k
Binary search with modern processors
kampersanda
33
14k
AIP Open Seminar #6
kampersanda
0
230
ICDM2020
kampersanda
0
210
SIGSPATIAL20
kampersanda
0
190
Fast Succinct Trie
kampersanda
1
710
Other Decks in Research
See All in Research
公立高校入試等に対する受入保留アルゴリズム(DA)導入の提言
shunyanoda
0
5.8k
SSII2025 [TS2] リモートセンシング画像処理の最前線
ssii
PRO
7
2.8k
(NULLCON Goa 2025)Windows Keylogger Detection: Targeting Past and Present Keylogging Techniques
asuna_jp
1
530
最適決定木を用いた処方的価格最適化
mickey_kubo
4
1.7k
RHO-1: Not All Tokens Are What You Need
sansan_randd
1
110
Computational OT #4 - Gradient flow and diffusion models
gpeyre
0
300
SSII2025 [SS1] レンズレスカメラ
ssii
PRO
2
970
20250624_熊本経済同友会6月例会講演
trafficbrain
1
120
Google Agent Development Kit (ADK) 入門 🚀
mickey_kubo
2
1k
クラウドのテレメトリーシステム研究動向2025年
yuukit
3
960
利用シーンを意識した推薦システム〜SpotifyとAmazonの事例から〜
kuri8ive
1
200
Towards a More Efficient Reasoning LLM: AIMO2 Solution Summary and Introduction to Fast-Math Models
analokmaus
2
230
Featured
See All Featured
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.5k
Adopting Sorbet at Scale
ufuk
77
9.4k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Optimizing for Happiness
mojombo
379
70k
Code Review Best Practice
trishagee
69
18k
Scaling GitHub
holman
459
140k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
35
2.4k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Mobile First: as difficult as doing things right
swwweet
223
9.7k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Being A Developer After 40
akosma
90
590k
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