Abstract
Binary relations are an important abstraction arising in a number of data representation problems. Each existing data structure specializes in the few basic operations required by one single application, and takes only limited advantage of the inherent redundancy of binary relations. We show how to support more general operations efficiently, while taking better advantage of some forms of redundancy in practical instances. As a basis for a more general discussion on binary relation data structures, we list the operations of potential interest for practical applications, and give reductions between operations. We identify a set of operations that yield the support of all others. As a first contribution to the discussion, we present two data structures for binary relations, each of which achieves a distinct tradeoff between the space used to store and index the relation, the set of operations supported in sublinear time, and the time in which those operations are supported. The experimental performance of our data structures shows that they not only offer good time complexities to carry out many operations, but also take advantage of regularities that arise in practical instances to reduce space usage.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baeza-Yates, R., Navarro, G.: Modeling text databases. In: Recent Advances in Applied Probability, pp. 1–25. Springer, Heidelberg (2004)
Barbay, J., Aleardi, L.C., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 316–328. Springer, Heidelberg (2007)
Barbay, J., Golynski, A., Munro, I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. TCS 387(3), 284–297 (2007)
Barbay, J., He, M., Munro, I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: SODA, pp. 680–689 (2007)
Barbay, J., Navarro, G.: Compressed representations of permutations, and applications. In: STACS. pp. 111–122 (2009)
Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: WWW, pp. 595–602 (2004)
Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M.L., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 98–109. Springer, Heidelberg (2009)
Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.: Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In: DCC. pp. 252–261 (2008)
Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., Raghavan, P.: On compressing social networks. In: KDD, pp. 219–228 (2009)
Clark, D.: Compact Pat Trees. Ph.D. thesis, Univ. of Waterloo, Canada (1996)
Claude, F.: Compressed Data Structures for Web Graphs. MSc. thesis, U. Chile (2008)
Claude, F., Navarro, G.: A fast and compact Web graph representation. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 105–116. Springer, Heidelberg (2007)
Claude, F., Navarro, G.: Self-indexed text compression using straight-line programs. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 235–246. Springer, Heidelberg (2009)
Ferragina, P., Manzini, G., Mäkinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM TALG 3(2), article 20 (2007)
Golynski, A., Munro, J.I., Rao, S.S.: Rank/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368–373 (2006)
Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: SODA. pp. 841–850 (2003)
Kärkkäinen, J.: Repetition-Based Text Indexing. Ph.D. thesis, U. Helsinki, Finland (1999)
Mäkinen, V., Navarro, G.: Rank and select revisited and extended. TCS 387(3), 332–347 (2007)
Mäkinen, V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. ACM TALG 4(3), article 32 (2008)
Navarro, G.: Indexing text using the Ziv-Lempel trie. JDA 2(1), 87–114 (2004)
Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA, pp. 233–242 (2002)
Witten, I., Moffat, A., Bell, T.: Managing Gigabytes, 2nd edn. Morgan Kaufmann Publishers, San Francisco (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barbay, J., Claude, F., Navarro, G. (2010). Compact Rich-Functional Binary Relation Representations. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)