	Log in \| Register \|

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

On Placing Skips Optimally In Expectation

author: Alessandro Panconesi, University of Rome

You might be experiencing some problems with Your Video player.

*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

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.