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
220
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
330
Lucene/Elasticsearch の Character Filter でユニコード正規化するとトークンのオフセットがズレるバグへの Workaround - Search Engineering Tech Talk 2024 Spring
kampersanda
0
1.3k
Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval
kampersanda
2
370
トライとダブル配列の基礎
kampersanda
0
1.1k
Binary search with modern processors
kampersanda
30
13k
AIP Open Seminar #6
kampersanda
0
220
ICDM2020
kampersanda
0
190
SIGSPATIAL20
kampersanda
0
180
Fast Succinct Trie
kampersanda
1
680
Other Decks in Research
See All in Research
2025年度 生成AIの使い方/接し方
hkefka385
0
460
Prithvi-EO-2.0: A Versatile Multi-Temporal Foundation Model for Earth Observation Applications
satai
3
330
Satellite Sunroof: High-res Digital Surface Models and Roof Segmentation for Global Solar Mapping
satai
3
280
Pix2Poly: A Sequence Prediction Method for End-to-end Polygonal Building Footprint Extraction from Remote Sensing Imagery
satai
3
270
JSAI NeurIPS 2024 参加報告会(AI アライメント)
akifumi_wachi
5
950
20241226_くまもと公共交通新時代シンポジウム
trafficbrain
0
500
Data-centric AI勉強会 「ロボットにおけるData-centric AI」
haraduka
0
560
GeoCLIP: Clip-Inspired Alignment between Locations and Images for Effective Worldwide Geo-localization
satai
3
120
Weekly AI Agents News! 2月号 アーカイブ
masatoto
1
150
eAI (Engineerable AI) プロジェクトの全体像 / Overview of eAI Project
ishikawafyu
0
440
地理空間情報と自然言語処理:「地球の歩き方旅行記データセット」の高付加価値化を通じて
hiroki13
1
230
Dynamic World, Near real-time global 10 m land use land cover mapping
satai
3
210
Featured
See All Featured
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
34
2.2k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
13
1.4k
It's Worth the Effort
3n
184
28k
We Have a Design System, Now What?
morganepeng
52
7.5k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
21k
A designer walks into a library…
pauljervisheath
205
24k
Six Lessons from altMBA
skipperchong
27
3.7k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
32
5.4k
Making Projects Easy
brettharned
116
6.1k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
BBQ
matthewcrist
88
9.6k
RailsConf 2023
tenderlove
30
1.1k
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