forked from Tribler/tribler.github.com
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
129 lines (103 loc) · 4.71 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>Tribler</title>
<link rel="stylesheet" href="/css/style.css" />
<link rel="stylesheet" href="/css/animate.min.css">
<link rel="stylesheet" href="/css/trac.css" type="text/css" />
<link rel="shortcut icon" href="/img/favicon.ico" type="image/x-icon" />
<link rel="icon" href="/img/favicon.ico" type="image/x-icon" />
<!--[if lt IE 9]>
<script src="/js/html5shiv.js"></script>
<![endif]-->
<script src="/js/wow.min.js"></script>
<script>
new WOW().init();
</script>
<script type="text/javascript" src="/js/jquery-1.10.2.min.js"></script>
<script type="text/javascript">
var uservoiceOptions = {
/* required */
key: 'tribler',
host: 'tribler.uservoice.com',
forum: '90409',
showTab: true,
/* optional */
alignment: 'right',
background_color:'#f00',
text_color: 'white',
hover_color: '#009ec3',
lang: 'en'
};
function _loadUserVoice() {
var s = document.createElement('script');
s.setAttribute('type', 'text/javascript');
s.setAttribute('src', ("https:" == document.location.protocol ? "https://" : "http://") + "cdn.uservoice.com/javascripts/widgets/tab.js");
document.getElementsByTagName('head')[0].appendChild(s);
}
_loadSuper = window.onload;
window.onload = (typeof window.onload != 'function') ? _loadUserVoice : function() { _loadSuper(); _loadUserVoice(); };
</script>
</head>
<body>
<header>
<div class="wow fadeInDown">
<div class="wow fadeInLeft">
<a href="https://www.facebook.com/TriblerTeam"><img class="facebook-icon" src="/img/facebook-icon.png" /></a>
<a href="https://twitter.com/TriblerTeam"><img class="twitter-icon" src="/img/twitter-icon.png" /></a>
<a href="https://github.com/Tribler"><img class="github-icon" src="/img/github-icon.png" /></a>
</div>
<a href="/"><img class="header-logo" src="/img/tribler-logo.png" alt="Return to the homepage" /></a>
<nav>
<ul>
<li><a href="/">Tribler</a>
<ul>
<li><a href="/about.html">About Tribler</a></li>
<li><a href="/anonymity.html">Towards Anonymity</a></li>
<li><a href="https://release.tribler.org/dashboard/">Statistics</a></li>
</ul>
</li>
<li><a href="/download.html">Download</a></li>
<li><a href="/support-index.html">Support</a>
<ul>
<li><a href="/howto.html">Get Started</a></li>
<li><a href="/faq.html">FAQ</a></li>
</ul>
</li>
<li><a href="/developer-index.html">Developers</a>
<ul>
<li><a href="https://github.com/Tribler/tribler">Github</a></li>
<li><a href="https://github.com/Tribler/tribler/wiki">Wiki</a></li>
<li><a href="/TitleIndex">Archive</a></li>
</ul>
</li>
<li><a href="http://forum.tribler.org">Forum</a></li>
</ul>
</nav>
</header>
<section id="trac"><table><tr><td><h1 id="BinMaps"><a class="wiki" href="/BinMaps">BinMaps</a></h1>
<p>
This paper addresses the classical problem of keeping huge bitmaps predominantly consisting of long ranges of zeros and ones. The problem is most often encountered in filesystems (free space tracking) and network protocols (transmission progress tracking).
</p>
<p>
Three classical solutions to the problem are plain bitmaps (NTFS), extent lists (TCP SACK) and extent binary trees (XFS, Btrfs). Bitmaps are simple but have high fixed space requirements. Lists are able to aggregate solid ranges, but they don't scale well with regard to search. Extent binary trees are able of aggregation, allow scalable search, but have high overhead and extremely bad worst case behavior, potentially exploding to sizes a couple orders of magnitude higher than plain bitmaps.
The latter problem is sometimes resolved by ad-hoc means, e.g. by converting parts of an extent tree to bitmaps (Btrfs). Another possible workaround is to impose a divide-and-conquer multilayered unit system (<a class="wiki" href="/BitTorrent">BitTorrent</a>).
</p>
<p>
We introduce a new data structure named "binmap", a hybrid of bitmap and binary tree, which resolves the shortcomings of the extent binary tree approach. Namely (a) it has lower average-case overhead (b) it is tolerant to patchy bitmaps and (c) its worst-case behavior is dramatically better.
</p>
<p>
<em>see the attached article</em>
</p>
<div id="attachments">
<h3 class="foldable">Attachments</h3>
<ul>
<li><a href="http://kayapo.tribler.org/trac/raw-attachment/wiki/BinMaps/binmaps-alenex.pdf">binmaps-alenex.pdf</a>
(<span>1.4MB</span>)</li></ul>
</div></td>
</tr>
</table>
</section>
</body>
</html>