First ACM International Conference on Web Search and Data Mining - WSDM 2008

On Placing Skips Optimally In Expectation

author:Alessandro Panconesi, Sapienza University of Rome
published: Feb. 25, 2008, recorded: February 2008, views: 131

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Placing Skips Optimally in Expectation
0:32	Problem Statement
0:44	Answering conjunctive queries (1)
1:08	Answering conjunctive queries (2)
1:29	Merging (1)
1:55	Merging (2)
2:04	Merging (3)
2:07	Merging (4)
2:09	Merging (5)
2:14	Skips (1)
2:50	Skips (2)
2:53	Skips (3)
3:00	Conventional WSDM
3:26	Question
3:38	Problem statement (1)
4:01	Problem statement (2)
4:09	The Power of the Law
4:25	The query distribution contains a lot of information. Can we provably take advantage of it?
4:46	Algorithms to follow work with any query distribution whatsoever (1)
4:59	Algorithms to follow work with any query distribution whatsoever (2)
5:12	Outline
5:48	Skip Placement Policies
5:51	Spaghetti Skips (1)
5:56	Spaghetti Skips (2)
6:20	Simple Skips (1)
6:46	Simple Skips (2)
6:53	A Matter of Definitions
7:02	Useful Documents: 1
7:36	But usefulness does not coincide with relevance
8:07	Useful Documents: 2 (1)
8:35	Useful Documents: 2 (2)
8:55	Useful Documents: 2 (3)
8:57	Useful Documents: 2 (4)
9:05	Useful Documents: 2 (5)
9:14	Useful Documents: 2 (6)
9:42	Useful Documents: 2 (7)
9:46	Useful Documents: 2 (8)
9:48	Useful Documents: 2 (9)
9:50	Useful Documents: 2 (10)
9:53	Useful Documents: 2 (11)
9:54	Useful Documents: 2 (12)
10:01	Useful Documents: 2 (13)
10:42	Induced Distributions (1)
11:14	Induced Distributions (2)
11:49	Induced Distributions (3)
12:01	Induced Distributions (4)
12:15	Making Life Simple (1)
12:51	Making Life Simple (2)
13:10	Algorithms (1)
13:13	Algorithms (2)
13:31	Algorithms (4)
14:14	Algorithms (5)
14:30	Algorithms (6)
14:54	Simple Skips
15:52	Computing M(i) (1)
16:03	Computing M(i) (2)
16:34	Computing M(i) (3)
17:29	Computing M(i) (4)
17:47	Computing M(i) (5)
18:34	Monotonicity of T(i) (1)
18:47	Monotonicity of T(i) (2)
19:01	Monotonicity of T(i) (3)
19:17	Monotonicity of T(i) (4)
19:21	Updating T(i,k) (1)
19:44	Updating T(i,k) (2)
19:48	Updating T(i,k) (3)
20:06	Updating T(i,k) (4)
20:09	Updating T(i,k) (5)
20:30	Updating T(i,k) (6)
20:44	Updating T(i,k) (7)
21:19	The resulting algorithm takes O(N logN) where N is the length of the list
21:21	Experiments
21:22	Space
22:27	Time to merge
23:11	Build up time
23:28	Size of query sample for spaghetti skips
23:30	Size of query sample for simple skips
24:03	The Bottomline
24:08	Summing up
24:22	Extensions

Related content

Visitors who watched this lecture also watched...