Page 19 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 19
le 1: Comparison between the cache-oblivious data structure (C-O) and the quadtree (QT).
Construction time Query time Size
Number of points C-O QT C-O QT C-O QT
100.000 30 s 0,06 s 5 ms 43 ms ∼1 GB 2MB
200.000 69 s 0,12 s 28 ms 90 ms ∼2,5 GB 4MB
1.000.000 7,5 min 0,7 s 132 ms 453 ms ∼7 GB 24MB
2.000.000 17 min 1.5 s 413 ms 951 ms ∼16 GB 50MB
10.000.000 ∼2 h 22 s 2817 ms 6259 ms ∼80 GB 300MB
100.000.000 ∼8 h 115 s 32523 ms 341282 ms ∼950 GB 3,5GB
to-leaf and leaf-to-root traversals. Each computation to space. So there is actually a trade-off between the speed of
find the index of the parent/child of a specific node takes the queries and the space.
O(log2 N ) time, so we decided to precompute the indexes
for all the topologies of the trees, which drastically reduced 5. REFERENCES
the construction time.
[1] P. Afshani, C. Hamilton, and N. Zeh. Cache-oblivious
We decided to compare the cache-oblivious data structure range reporting with optimal queries requires
with a quadtree, probably the most used data structure superlinear space. In SCG ’09: Proceedings of the 25th
for range queries in the RAM model. We compared the annual symposium on Computational geometry. ACM
query time, construction time and the size of the data struc- Request Permissions, June 2009.
ture. We tested on problems of different sizes, varying from
100.000 to 100.000.000 points. All the coordinates were ran- [2] P. K. Agarwal, L. Arge, A. Danner, and
dom 32-bits decimal numbers. All the queries were of type B. Holland-Minkley. Cache-oblivious data structures for
(−∞, ∞) × (−∞, ∞), so all the points had to be returned. orthogonal range searching. pages 237–245, 2003.
All the tests were run five times and the average results are
shown in Table 1. All the tests were run on a Core 2 Duo @ [3] A. Aggarwal and J. Vitter. The input/output
2.53 GHz and 4GB of RAM. complexity of sorting and related problems.
Communications of the ACM, 31(9):1116–1127, 1988.
From the results of the tests, it can be seen that the cache-
oblivious is much faster in answering the queries. The shaded [4] L. Arge and N. Zeh. Simple and semi-dynamic
cells in Table 1 show, that the data structure for that specific structures for cache-oblivious planar orthogonal range
size was already bigger than the available main memory, so searching. In SCG ’06: Proceedings of the
swapping occured. Note, that because of high locality for twenty-second annual symposium on Computational
the cache-oblivious data structure, swapping didn’t affect it geometry. ACM Request Permissions, June 2006.
as much as it affected the quadtree.
[5] M. A. Bender, E. D. Demaine, and M. Farach-Colton.
On the other side, the size of the whole cache-oblivious data Cache-oblivious B-trees. SIAM J. Comput.,
structure is much bigger than the quadtree. The main reason 35(2):341–358, 2005.
is that even if the key ingredient of the cache-oblivious data
structure (the two-sided data structure) has linear space [6] M. Frigo, C. E. Leiserson, H. Prokop, and
complexity, we need a lot of them (O(log22 N ) exactly). When S. Ramachandran. Cache-Oblivious Algorithms. In
N is getting bigger, this factor is not negligible. FOCS ’99: Proceedings of the 40th Annual Symposium
on Foundations of Computer Science. IEEE Computer
The difference in the construction time is probably of the Society, Oct. 1999.
least importance, as the cache-oblivious data structure is a
static data structure, so it can be precomputed. Despite [7] H. Prokop. Cache-oblivious algorithms. Master thesis,
that, it is interesting to notice, that 2/3 of the construction Massachusetts Institute of Technology, Cambridge.
time is sorting the points, as the four-sided data structure
needs the points sorted by their y-coordinate, the three-sided
needs them sorted by their x-coordinate. So for every three-
sided data structure we need to sort all the points. The same
happens for every two-sided data structure, as it needs them
sorted by their x coordinate.
4. CONCLUSIONS
This is the first imeplementation of this data structure to
the author’s knowledge. It can be seen from the results,
that the cache-oblivious data structure, once constructed, is
not affected by the swapping of blocks made by the oper-
ating system, as the theory suggested. On the other side,
to achieve that, the implemented solution takes a lot more
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 19
Koper, Slovenia, 10-11 October
Construction time Query time Size
Number of points C-O QT C-O QT C-O QT
100.000 30 s 0,06 s 5 ms 43 ms ∼1 GB 2MB
200.000 69 s 0,12 s 28 ms 90 ms ∼2,5 GB 4MB
1.000.000 7,5 min 0,7 s 132 ms 453 ms ∼7 GB 24MB
2.000.000 17 min 1.5 s 413 ms 951 ms ∼16 GB 50MB
10.000.000 ∼2 h 22 s 2817 ms 6259 ms ∼80 GB 300MB
100.000.000 ∼8 h 115 s 32523 ms 341282 ms ∼950 GB 3,5GB
to-leaf and leaf-to-root traversals. Each computation to space. So there is actually a trade-off between the speed of
find the index of the parent/child of a specific node takes the queries and the space.
O(log2 N ) time, so we decided to precompute the indexes
for all the topologies of the trees, which drastically reduced 5. REFERENCES
the construction time.
[1] P. Afshani, C. Hamilton, and N. Zeh. Cache-oblivious
We decided to compare the cache-oblivious data structure range reporting with optimal queries requires
with a quadtree, probably the most used data structure superlinear space. In SCG ’09: Proceedings of the 25th
for range queries in the RAM model. We compared the annual symposium on Computational geometry. ACM
query time, construction time and the size of the data struc- Request Permissions, June 2009.
ture. We tested on problems of different sizes, varying from
100.000 to 100.000.000 points. All the coordinates were ran- [2] P. K. Agarwal, L. Arge, A. Danner, and
dom 32-bits decimal numbers. All the queries were of type B. Holland-Minkley. Cache-oblivious data structures for
(−∞, ∞) × (−∞, ∞), so all the points had to be returned. orthogonal range searching. pages 237–245, 2003.
All the tests were run five times and the average results are
shown in Table 1. All the tests were run on a Core 2 Duo @ [3] A. Aggarwal and J. Vitter. The input/output
2.53 GHz and 4GB of RAM. complexity of sorting and related problems.
Communications of the ACM, 31(9):1116–1127, 1988.
From the results of the tests, it can be seen that the cache-
oblivious is much faster in answering the queries. The shaded [4] L. Arge and N. Zeh. Simple and semi-dynamic
cells in Table 1 show, that the data structure for that specific structures for cache-oblivious planar orthogonal range
size was already bigger than the available main memory, so searching. In SCG ’06: Proceedings of the
swapping occured. Note, that because of high locality for twenty-second annual symposium on Computational
the cache-oblivious data structure, swapping didn’t affect it geometry. ACM Request Permissions, June 2006.
as much as it affected the quadtree.
[5] M. A. Bender, E. D. Demaine, and M. Farach-Colton.
On the other side, the size of the whole cache-oblivious data Cache-oblivious B-trees. SIAM J. Comput.,
structure is much bigger than the quadtree. The main reason 35(2):341–358, 2005.
is that even if the key ingredient of the cache-oblivious data
structure (the two-sided data structure) has linear space [6] M. Frigo, C. E. Leiserson, H. Prokop, and
complexity, we need a lot of them (O(log22 N ) exactly). When S. Ramachandran. Cache-Oblivious Algorithms. In
N is getting bigger, this factor is not negligible. FOCS ’99: Proceedings of the 40th Annual Symposium
on Foundations of Computer Science. IEEE Computer
The difference in the construction time is probably of the Society, Oct. 1999.
least importance, as the cache-oblivious data structure is a
static data structure, so it can be precomputed. Despite [7] H. Prokop. Cache-oblivious algorithms. Master thesis,
that, it is interesting to notice, that 2/3 of the construction Massachusetts Institute of Technology, Cambridge.
time is sorting the points, as the four-sided data structure
needs the points sorted by their y-coordinate, the three-sided
needs them sorted by their x-coordinate. So for every three-
sided data structure we need to sort all the points. The same
happens for every two-sided data structure, as it needs them
sorted by their x coordinate.
4. CONCLUSIONS
This is the first imeplementation of this data structure to
the author’s knowledge. It can be seen from the results,
that the cache-oblivious data structure, once constructed, is
not affected by the swapping of blocks made by the oper-
ating system, as the theory suggested. On the other side,
to achieve that, the implemented solution takes a lot more
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 19
Koper, Slovenia, 10-11 October
