On compact representations of all-pairs-shortest-path-distance matrices
Ferragina P., Nitto I., Venturini R.
Computer Science(all) Succinct data structures Theoretical Computer Science Compressed indexes for strings and trees General Computer Science All-Pairs-Shortest-Path Distances Shortest Paths Succinct Data Structures
Let G be an unweighted and undirected graph of n nodes, and let be the n×n matrix storing the All-Pairs-Shortest-Path Distances in G. Since contains integers in [n] U +∞, its plain storage takes n. log(n+1) bits. However, a simple counting argument shows that n. /2 bits are necessary to store . In this paper we investigate the question of finding a succinct representation of that requires O(n. ) bits of storage and still supports constant-time access to each of its entries. This is asymptotically optimal in the worst case, and far from the information-theoretic lower bound by a multiplicative factor log_2 3. As a result O(1) bits per pairs of nodes in G are enough to retain constant-time access to their shortest-path distance. We achieve this result by reducing the storage of to the succinct storage of labeled trees and ternary sequences, for which we properly adapt and orchestrate the use of known compressed data structures. This approach can be easily and optimally extended to graphs whose edge weights are positive integers bounded by a constant value.
Source: Theoretical computer science 411 (2010): 3293–3300. doi:10.1016/j.tcs.2010.05.021
Publisher: Elsevier, Lausanne ;, Paesi Bassi
[2] Michael A. Bender, Martin Farach-Colton, The level ancestor problem simplified, Theoretical Computer Science 321 (1) (2004) 5 12.
[3] D. Benoit, E. Demaine, I. Munro, R. Raman, V. Raman, S. Rao, Representing trees of higher degree, Algorithmica 43 (2005) 275 292.
[4] P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, in: Proc. 46th IEEE Symposium on Foundations of Computer Science, FOCS, 2005, pp. 184 193.
[5] P. Ferragina, G. Navarro, Pizza&Chili corpus home page. http://pizzachili.dcc.uchile.cl/ or http://pizzachili.di.unipi.it/.
[6] P. Ferragina, R. Venturini, A simple storage scheme for strings achieving entropy bounds, Theoretical Computer Science 372 (1) (2007) 115 121.
[7] Paolo Ferragina, Roberto Grossi, Ankur Gupta, Rahul Shah, Jeffrey Scott Vitter, On searching compressed string collections cache-obliviously, in: PODS, 2008, pp. 181 190.
[8] L. Foschini, R. Grossi, A. Gupta, J. Vitter, Fast compression with a static model in high order entropy, in: Procs of IEEE Data Compression Conference, DCC, 2004, pp. 62 71.
[9] R. Grossi, A. Gupta, J. Vitter, High-order entropy-compressed text indexes, in: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, SODA, 2003, pp. 841 850.
[10] R. Grossi, A. Gupta, J. Vitter, When indexing equals compression: Experiments on compressing suffix arrays and applications, in: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms, SODA, 2004, pp. 636 645.
[11] A. Gupta, W.K. Hon, R. Shah, J.S. Vitter, Compressed data structures: dictionaries and data-aware measures, Theoretical Computer Science 387 (3) (2007) 313 331.
[12] G. Jacobson, Space-efficient static trees and graphs, in: Proc. 30th IEEE Symposium on Foundations of Computer Science, FOCS, 1989, pp. 549 554.
[13] J. Jansson, K. Sadakane, W.K. Sung, Ultra-succinct representation of ordered trees, in: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, SODA, 2007, pp. 575 584.
[14] V. Mäkinen, G. Navarro, Rank and select revisited and extended, Theoretical Computer Science 387 (3) (2007) 332 347.
[15] M. Mendel, A. Naor, Ramsey partitions and proximity data structures, in: Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2006, pp. 109 118.
[16] I. Munro, Tables, in: Proceeding of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, in: LNCS, vol. 1180, Springer-Verlag, 1996, pp. 37 42.
[17] I. Munro, V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, in: Proc. of the 38th IEEE Symposium on Foundations of Computer Science, FOCS, 1997, pp. 118 126.
[18] I. Munro, V. Raman, Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing 31 (2001) 762 776.
[19] G. Navarro, V. Mäkinen, Compressed full-text indexes, ACM Computing Surveys 39 (1) (2007).
[20] R. Pagh, Low redundancy in static dictionaries with constant query time, SIAM Journal on Computing 31 (2) (2001) 353 363.
[21] R. Raman, V. Raman, S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, SODA, 2002, pp. 233 242.
[22] M. Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM 51 (6) (2004) 993 1024.
[23] M. Thorup, U. Zwick, Approximate distance oracles, in: Proc. of the 33rd Symposium on Theory of Computing, STOC, 2001, pp. 183 192.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:44335,
title = {On compact representations of all-pairs-shortest-path-distance matrices},
author = {Ferragina P. and Nitto I. and Venturini R.},
publisher = {Elsevier, Lausanne ;, Paesi Bassi},
doi = {10.1016/j.tcs.2010.05.021},
journal = {Theoretical computer science},
volume = {411},
pages = {3293–3300},
year = {2010}
}
0000-0002-9830-3936
