[theora] Indexing Ogg files for faster seeking
Bernard Jungen
bjung50169 at euphonynet.be
Fri Jan 22 16:14:26 PST 2010
On Fri, Jan 22, 2010 at 08:29:59AM -0500, Gregory Maxwell wrote:
> On Fri, Jan 22, 2010 at 8:13 AM, Bernard Jungen
> <bjung50169 at euphonynet.be> wrote:
> > On Fri, Jan 22, 2010 at 04:17:40PM +1300, Chris Pearce wrote:
> >> Seems that delta+deflate initially performs about 5-10% worse than
> >> delta+variable_length, until it converges at around 2000 keypoints in
> >> the media (about 2 hours long), where it's about 1-2% better. I think we
> >> should keep it simple.
> >
> > Can you make the raw index data for your example(s) available somewhere so I
> > can have a look? Thanks.
>
> http://myrandomnode.dyndns.org:8080/~gmaxwell/aa/
I had a look at the example data and here are some stats and results using a
theoretical constant-bit-length encoder, along with some comments.
=== Stats for the Vorbis index:
Keypoints: 3790
Offset deltas (after -29622 correction): 0 to 3255700
Time stamp deltas (after /1 and -2374 corrections): 0 to 935
1-bit offset deltas: 1
15-bit offset deltas: 3
16-bit offset deltas: 18
17-bit offset deltas: 105
18-bit offset deltas: 694
19-bit offset deltas: 1562
20-bit offset deltas: 1083
21-bit offset deltas: 317
22-bit offset deltas: 6
1-bit time stamp deltas: 1
3-bit time stamp deltas: 1
5-bit time stamp deltas: 2
6-bit time stamp deltas: 11
7-bit time stamp deltas: 361
8-bit time stamp deltas: 643
9-bit time stamp deltas: 1588
10-bit time stamp deltas: 1182
Keypoint size: 22+10+32 = 64 bits (vs 160) = 40 %
=== Stats for the Theora index:
Keypoints: 3723
Offset deltas (after -21108 correction): 0 to 3879141
Time stamp deltas (after /40 and -51 corrections): 0 to 63
1-bit offset deltas: 1
15-bit offset deltas: 5
16-bit offset deltas: 16
17-bit offset deltas: 111
18-bit offset deltas: 667
19-bit offset deltas: 1441
20-bit offset deltas: 1122
21-bit offset deltas: 344
22-bit offset deltas: 15
1-bit time stamp deltas: 116
2-bit time stamp deltas: 58
3-bit time stamp deltas: 145
4-bit time stamp deltas: 2307
5-bit time stamp deltas: 423
6-bit time stamp deltas: 673
Keypoint size: 22+6+32 = 60 bits (vs 160) = 37.5 %
=== Comments
As can be seen in the "correction" numbers for the Theora index, time stamp
deltas are few and can be significantly simplified to take less space. We
could fold the multiplicative factor (the "40" above) correction into the
presentation time denominator parameter if it's ok with its purpose.
In the Theora index, one single time stamp delta occurs very often (2144 times
or 58 %, surely something to do with the keyframe interval parameters set at
compression and index generation), and sometimes in relatively long runs.
We could add a run-length capability for that specific (i.e. with highest
count) value nearly for free. Tests of run-length encoding on the example
save an extra 1.7 bit per value, or a percentage point better for the whole
keypoint. Some tests on video material with higher keyframe density would be
interesting. Also, the other deltas probabilities look like a flat exponential,
and may be good meat for entropy encoders, as can be seen in the following
table:
TS[13]=2144 TS[ 0]= 72 TS[ 5]= 45 TS[ 1]= 44 TS[15]= 38
TS[21]= 38 TS[ 2]= 32 TS[19]= 31 TS[10]= 31 TS[30]= 31
TS[17]= 29 TS[24]= 29 TS[ 6]= 29 TS[22]= 28 TS[11]= 28
TS[18]= 28 TS[31]= 28 TS[33]= 28 TS[40]= 28 TS[ 7]= 27
TS[25]= 27 TS[42]= 27 TS[56]= 27 TS[ 3]= 26 TS[45]= 26
TS[47]= 26 TS[32]= 26 TS[14]= 25 TS[49]= 25 TS[41]= 25
TS[62]= 25 TS[50]= 24 TS[ 9]= 24 TS[35]= 24 TS[16]= 23
TS[37]= 23 TS[39]= 23 TS[ 4]= 23 TS[28]= 23 TS[29]= 23
TS[27]= 22 TS[34]= 22 TS[20]= 22 TS[55]= 22 TS[36]= 22
TS[26]= 22 TS[ 8]= 21 TS[58]= 20 TS[23]= 19 TS[63]= 19
TS[59]= 18 TS[57]= 18 TS[53]= 18 TS[51]= 17 TS[52]= 17
TS[48]= 17 TS[12]= 17 TS[44]= 17 TS[54]= 16 TS[46]= 16
TS[38]= 15 TS[60]= 15 TS[61]= 14 TS[43]= 13
Here are the run length stats for the time stamp delta with highest count (13):
length=2: 158
length=3: 115
length=4: 56
length=5: 37
length=6: 23
length=7: 9
length=8: 3
length=9: 7
length=10: 7
length=11: 1
length=12: 2
length=13: 1
length=14: 5
length=17: 1
length=18: 2
length=19: 1
length=24: 1
length=25: 1
length=31: 1
length=59: 1
However, for Vorbis, I see the time stamp deltas are quite random. An unfortunate
(in this case) property of Vorbis I suppose? The probabilities distribution
of deltas, when sorted, seems to be exponential as can be seen in the
following table, and an entropy coder may be able to work well on it:
TS[570]= 133 TS[122]= 79 TS[186]= 74 TS[506]= 63 TS[442]= 51
TS[549]= 50 TS[101]= 45 TS[527]= 45 TS[490]= 40 TS[143]= 39
TS[538]= 39 TS[514]= 36 TS[546]= 36 TS[463]= 36 TS[530]= 36
TS[522]= 33 TS[548]= 33 TS[165]= 31 TS[562]= 30 TS[474]= 29
TS[164]= 28 TS[554]= 28 TS[482]= 28 TS[485]= 28 TS[466]= 27
TS[498]= 27 TS[525]= 26 TS[458]= 26 TS[528]= 25 TS[557]= 23
TS[509]= 23 TS[493]= 23 TS[535]= 22 TS[519]= 22 TS[144]= 22
TS[207]= 21 TS[511]= 21 TS[503]= 20 TS[495]= 20 TS[437]= 19
TS[421]= 19 TS[487]= 19 TS[551]= 18 TS[543]= 18 TS[138]= 18
TS[533]= 18 TS[565]= 18 TS[541]= 18 TS[594]= 18 TS[402]= 17
TS[418]= 17 TS[559]= 16 TS[100]= 16 TS[501]= 16 TS[146]= 16
TS[314]= 16 TS[410]= 15 TS[517]= 15 TS[500]= 15 TS[453]= 15
TS[162]= 15 TS[378]= 15 TS[426]= 15 TS[591]= 15 TS[229]= 15
TS[469]= 14 TS[455]= 14 TS[477]= 14 TS[544]= 14 TS[564]= 14
TS[445]= 14 TS[532]= 14 TS[484]= 14 TS[508]= 14 TS[434]= 13
TS[464]= 13 TS[ 90]= 13 TS[578]= 13 TS[560]= 13 TS[450]= 13
TS[394]= 12 TS[170]= 12 TS[567]= 12 TS[405]= 12 TS[250]= 12
TS[125]= 12 TS[592]= 12 TS[106]= 12 TS[370]= 11 TS[461]= 11
TS[488]= 11 TS[575]= 11 TS[ 98]= 11 TS[130]= 11 TS[154]= 11
TS[524]= 11 TS[373]= 10 TS[536]= 10 TS[194]= 10 TS[496]= 10
TS[413]= 10 TS[381]= 10 TS[420]= 10 TS[573]= 10 TS[343]= 10
TS[399]= 10 TS[583]= 10 TS[428]= 10 TS[429]= 10 TS[114]= 10
TS[602]= 10 TS[157]= 9 TS[516]= 9 TS[431]= 9 TS[452]= 9
TS[520]= 9 TS[581]= 9 TS[423]= 9 TS[584]= 9 TS[586]= 9
TS[133]= 9 TS[476]= 9 TS[440]= 9 TS[362]= 9 TS[408]= 8
TS[359]= 8 TS[492]= 8 TS[ 77]= 8 TS[151]= 8 TS[372]= 8
TS[109]= 8 TS[568]= 8 TS[375]= 8 TS[124]= 8 TS[159]= 8
TS[576]= 8 TS[386]= 8 TS[388]= 8 TS[141]= 8 TS[258]= 8
TS[479]= 8 TS[111]= 8 TS[127]= 8 TS[407]= 8 TS[447]= 8
TS[605]= 8 TS[103]= 7 TS[181]= 7 TS[132]= 7 TS[462]= 7
TS[271]= 7 TS[293]= 7 TS[309]= 7 TS[439]= 7 TS[471]= 7
TS[116]= 7 TS[504]= 7 TS[415]= 7 TS[540]= 7 TS[335]= 7
TS[135]= 7 TS[480]= 7 TS[512]= 7 TS[448]= 7 TS[391]= 7
TS[226]= 7 TS[597]= 7 TS[424]= 7 TS[556]= 7 TS[175]= 6
TS[178]= 6 TS[263]= 6 TS[104]= 6 TS[380]= 6 TS[272]= 6
TS[460]= 6 TS[382]= 6 TS[ 79]= 6 TS[ 95]= 6 TS[534]= 6
TS[148]= 6 TS[330]= 6 TS[432]= 6 TS[580]= 6 TS[470]= 6
TS[213]= 6 TS[542]= 6 TS[472]= 6 TS[589]= 6 TS[119]= 6
TS[357]= 6 TS[228]= 6 TS[120]= 6 TS[599]= 6 TS[239]= 6
TS[604]= 6 TS[412]= 6 TS[607]= 6 TS[218]= 5 TS[303]= 5
TS[221]= 5 TS[223]= 5 TS[436]= 5 TS[319]= 5 TS[396]= 5
TS[397]= 5 TS[398]= 5 TS[444]= 5 TS[328]= 5 TS[572]= 5
TS[112]= 5 TS[ 87]= 5 TS[140]= 5 TS[344]= 5 TS[167]= 5
TS[247]= 5 TS[248]= 5 TS[539]= 5 TS[368]= 5 TS[191]= 5
TS[168]= 5 TS[134]= 5 TS[505]= 5 TS[545]= 5 TS[266]= 5
TS[208]= 5 TS[173]= 5 TS[279]= 5 TS[552]= 5 TS[608]= 5
TS[610]= 5 TS[128]= 4 TS[468]= 4 TS[ 93]= 4 TS[202]= 4
TS[160]= 4 TS[561]= 4 TS[518]= 4 TS[117]= 4 TS[387]= 4
TS[337]= 4 TS[389]= 4 TS[338]= 4 TS[341]= 4 TS[260]= 4
TS[261]= 4 TS[531]= 4 TS[354]= 4 TS[210]= 4 TS[400]= 4
TS[149]= 4 TS[446]= 4 TS[404]= 4 TS[180]= 4 TS[364]= 4
TS[365]= 4 TS[499]= 4 TS[409]= 4 TS[366]= 4 TS[113]= 4
TS[183]= 4 TS[184]= 4 TS[416]= 4 TS[108]= 4 TS[189]= 4
TS[613]= 4 TS[379]= 3 TS[277]= 3 TS[529]= 3 TS[454]= 3
TS[212]= 3 TS[456]= 3 TS[282]= 3 TS[290]= 3 TS[292]= 3
TS[152]= 3 TS[300]= 3 TS[302]= 3 TS[392]= 3 TS[126]= 3
TS[304]= 3 TS[155]= 3 TS[156]= 3 TS[317]= 3 TS[318]= 3
TS[547]= 3 TS[475]= 3 TS[ 94]= 3 TS[550]= 3 TS[322]= 3
TS[326]= 3 TS[553]= 3 TS[327]= 3 TS[481]= 3 TS[158]= 3
TS[ 85]= 3 TS[331]= 3 TS[234]= 3 TS[237]= 3 TS[414]= 3
TS[129]= 3 TS[340]= 3 TS[494]= 3 TS[188]= 3 TS[ 63]= 3
TS[ 88]= 3 TS[345]= 3 TS[346]= 3 TS[253]= 3 TS[502]= 3
TS[356]= 3 TS[582]= 3 TS[255]= 3 TS[147]= 3 TS[360]= 3
TS[588]= 3 TS[200]= 3 TS[590]= 3 TS[435]= 3 TS[ 80]= 3
TS[262]= 3 TS[596]= 3 TS[204]= 3 TS[ 92]= 3 TS[ 81]= 3
TS[172]= 3 TS[274]= 3 TS[275]= 3 TS[376]= 3 TS[377]= 3
TS[276]= 3 TS[621]= 3 TS[624]= 3 TS[626]= 3 TS[358]= 2
TS[ 74]= 2 TS[526]= 2 TS[278]= 2 TS[166]= 2 TS[280]= 2
TS[137]= 2 TS[285]= 2 TS[286]= 2 TS[369]= 2 TS[287]= 2
TS[107]= 2 TS[231]= 2 TS[192]= 2 TS[295]= 2 TS[296]= 2
TS[298]= 2 TS[457]= 2 TS[139]= 2 TS[238]= 2 TS[198]= 2
TS[240]= 2 TS[384]= 2 TS[385]= 2 TS[306]= 2 TS[307]= 2
TS[308]= 2 TS[171]= 2 TS[390]= 2 TS[310]= 2 TS[473]= 2
TS[313]= 2 TS[ 31]= 2 TS[249]= 2 TS[ 82]= 2 TS[205]= 2
TS[320]= 2 TS[206]= 2 TS[401]= 2 TS[483]= 2 TS[569]= 2
TS[325]= 2 TS[571]= 2 TS[257]= 2 TS[174]= 2 TS[406]= 2
TS[259]= 2 TS[491]= 2 TS[142]= 2 TS[ 84]= 2 TS[332]= 2
TS[411]= 2 TS[333]= 2 TS[211]= 2 TS[587]= 2 TS[121]= 2
TS[264]= 2 TS[ 69]= 2 TS[267]= 2 TS[342]= 2 TS[269]= 2
TS[422]= 2 TS[270]= 2 TS[215]= 2 TS[123]= 2 TS[427]= 2
TS[348]= 2 TS[351]= 2 TS[430]= 2 TS[353]= 2 TS[612]= 2
TS[220]= 2 TS[616]= 2 TS[433]= 2 TS[ 86]= 2 TS[222]= 2
TS[629]= 2 TS[110]= 1 TS[513]= 1 TS[163]= 1 TS[515]= 1
TS[425]= 1 TS[ 64]= 1 TS[136]= 1 TS[ 66]= 1 TS[347]= 1
TS[521]= 1 TS[273]= 1 TS[523]= 1 TS[349]= 1 TS[350]= 1
TS[ 68]= 1 TS[352]= 1 TS[ 0]= 1 TS[ 70]= 1 TS[ 72]= 1
TS[438]= 1 TS[118]= 1 TS[219]= 1 TS[441]= 1 TS[ 39]= 1
TS[443]= 1 TS[537]= 1 TS[281]= 1 TS[361]= 1 TS[ 75]= 1
TS[363]= 1 TS[284]= 1 TS[449]= 1 TS[145]= 1 TS[451]= 1
TS[176]= 1 TS[367]= 1 TS[225]= 1 TS[288]= 1 TS[177]= 1
TS[291]= 1 TS[ 97]= 1 TS[459]= 1 TS[179]= 1 TS[ 46]= 1
TS[232]= 1 TS[558]= 1 TS[297]= 1 TS[233]= 1 TS[299]= 1
TS[ 99]= 1 TS[235]= 1 TS[236]= 1 TS[566]= 1 TS[182]= 1
TS[305]= 1 TS[ 78]= 1 TS[150]= 1 TS[185]= 1 TS[242]= 1
TS[243]= 1 TS[574]= 1 TS[312]= 1 TS[244]= 1 TS[245]= 1
TS[579]= 1 TS[316]= 1 TS[246]= 1 TS[ 47]= 1 TS[ 48]= 1
TS[153]= 1 TS[585]= 1 TS[ 53]= 1 TS[489]= 1 TS[323]= 1
TS[324]= 1 TS[252]= 1 TS[105]= 1 TS[254]= 1 TS[ 54]= 1
TS[195]= 1 TS[497]= 1 TS[197]= 1 TS[600]= 1 TS[ 83]= 1
TS[603]= 1 TS[199]= 1 TS[334]= 1 TS[131]= 1 TS[336]= 1
TS[417]= 1 TS[201]= 1 TS[419]= 1 TS[614]= 1 TS[615]= 1
TS[507]= 1 TS[618]= 1 TS[620]= 1 TS[ 60]= 1 TS[623]= 1
TS[203]= 1 TS[510]= 1 TS[628]= 1 TS[ 6]= 1 TS[631]= 1
TS[634]= 1 TS[650]= 1 TS[651]= 1 TS[698]= 1 TS[911]= 1
TS[935]= 1
So, now let's compare the previous results with those of an entropy encoder.
I guess an entropy encoder is no better, and may be worse, for offsets, but
better for time stamps. The question will be: is the added complexity worth it?
Cheers,
Bernard.
--
http://home.euphonynet.be/bjung/
GPG: D3ED A92F D243 FC07 1881 BE2E E68A A45D A54A DA90
More information about the theora
mailing list