Skip to main content
SpringerLink
Log in

On the Succinct Representation of Equivalence Classes

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models.

  • Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of \(\sum _{i=1}^n \lfloor {n \over i} \rfloor \) is necessary and sufficient. In other words, \(\lg n + \lg \lg n + O(1)\) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \(\lceil \lg n \rceil \) for the label length, if each vertex need not get a unique label.

  • Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , n\}\), we first show that \(\varTheta (\sqrt{n})\) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses \(O(\sqrt{n} \lg n)\) bits to support equivalence queries and unions in \(O(\lg n/\lg \lg n)\) worst case time or \(O(\alpha (n))\) expected amortized time where \(\alpha (n)\) is the inverse Ackermann function.

  • Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , cn\}\) for any constant \(c > 1\), we show that \(\varTheta (\lg n)\) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model.

We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. We use \(\lg n\) to denote \(\log _2 n\).

References

  1. Alstrup, S., Ben-Amram, A.M., Rauhe, T.: Worst-case and amortised optimality in union-find (extended abstract). In: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC ’99, pp. 499–506. ACM, New York, NY, USA (1999)

  2. Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12–14, 2003, Baltimore, Maryland, USA, pp. 689–698 (2003)

  3. Andersson, A., Miltersen, P.B., Thorup, M.: Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. 215(12), 337–344 (1999)

    Article  MATH  Google Scholar 

  4. Barbay, J., Aleardi, L.C., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: Tokuyama, T. (ed.) Algorithms and Computation, pp. 316–328. Springer, Berlin, Heidelberg (2007)

  5. Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275–292 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Blandford, D.K., Blelloch, G.E.: Compact representations of ordered sets. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, pp. 11–19. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2004)

  7. Blum, N.: On the single-operation worst-case time complexity of the disjoint set union problem. SIAM J. Comput. 15(4), 1021–1024 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  8. Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM J. Comput. 28(5), 1627–1640 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  9. Delpratt, O., Rahman, N., Raman, R.: Compressed prefix sums. In: van Leeuwen, J., Italiano, G., van der Hoek, W., Meinel, C., Sack, H., Plil, F. (eds.) SOFSEM 2007: Theory and Practice of Computer Science. Lecture Notes in Computer Science, vol. 4362, pp. 235–247. Springer, Berlin, Heidelberg (2007)

  10. Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., Tarjan, R.: Dynamic perfect hashing: upper and lower bounds. SIAM J. Comput. 23(4), 738–761 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  11. Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194–203 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  12. Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: Halperin, D., Mehlhorn, K. (eds.) Algorithms-ESA 2008, pp. 393–404. Springer, Berlin, Heidelberg (2008)

  13. Farzan, A., Munro, J.I.: A uniform paradigm to succinctly encode various families of trees. Algorithmica 68(1), 16–40 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  14. Franceschini, G., Muthukrishnan, S., Pătraşcu, M.: Radix sorting with no extra space. In: Proceedings of the 15th Annual European Conference on Algorithms, ESA’07, pp. 94–205. Springer, Berlin, Heidelberg (2007)

  15. Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424–436 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  16. Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11–14, 2004, pp. 1–10 (2004)

  17. Grossi, R., Orlandi, A., Raman, R., Rao, S.S.: More haste, less waste: lowering the redundancy in fully indexable dictionaries. In: Proceedings of 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26–28, 2009, Freiburg, Germany, pp. 517–528 (2009)

  18. Gupta, A., Hon, W.-K., Shah, R., Vitter, J.: Compressed data structures: dictionaries and data-aware measures. In: Proceedings of Data Compression Conference, 2006, DCC 2006, pp. 213–222, March (2006)

  19. Hagerup, T.: Sorting and searching on the word ram. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 98. Lecture Notes in Computer Science, vol. 1373, pp. 366–398. Springer, Berlin, Heidelberg (1998)

  20. Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 2(1), 75–115 (1918)

    Article  MATH  Google Scholar 

  21. Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University (1988)

  22. Kannan, S., Naor, M., Rudich, S.: Implicat representation of graphs. SIAM J. Discrete Math. 5(4), 596–603 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23–40 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  24. Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) Foundations of Software Technology and Theoretical Computer Science, pp. 37–42. Springer, Berlin, Heidelberg (1996)

  25. Munro, J.I., Nicholson, P.K.: Succinct posets. In: Proceedings of Algorithms-ESA 2012-20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, pp. 743–754 (2012)

  26. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19–22, 1997, pp. 118–126 (1997)

  27. Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39(2), 205–222 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  28. Overmars, M.H.: The Design of Dynamic Data Structures, vol. 156. Springer, Berlin (1983)

    MATH  Google Scholar 

  29. Raman, R.: Generating random graphs efficiently. In: Dehne, F., Fiala, F., Koczkodaj, W. (eds.) Advances in Computing and Information ICCI ’91. Lecture Notes in Computer Science, vol. 497, pp. 149–160. Springer, Berlin, Heidelberg (1991)

  30. Raman, R.: Eliminating Amortization: On Data Structures with Guaranteed Response Time. PhD thesis, Rochester, NY, USA. UMI Order No. GAX93-13880 (1993)

  31. Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans Algorithms (TALG) 3(4), 43 (2007)

    Article  MathSciNet  Google Scholar 

  32. Smid, M.H.: A data structure for the union-find problem having good single-operation complexity. Algorithms Rev. 1(1), 1–12 (1990)

    Google Scholar 

  33. Willard, D.E.: Log-logarithmic worst-case range queries are possible in space (n). Inf. Process. Lett. 17(2), 81–84 (1983)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. David Cheriton School of Computer Science, University of Waterloo, Ontario, Canada

    Hicham El-Zein, J. Ian Munro & Timothy M. Chan

  2. Department of Computer Science, Bar Ilan University, Ramat Gan, Israel

    Moshe Lewenstein

  3. The Institute of Mathematical Sciences, Chennai, India

    Venkatesh Raman

Authors
  1. Hicham El-Zein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Moshe Lewenstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. Ian Munro
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Venkatesh Raman
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Timothy M. Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hicham El-Zein.

Additional information

This work was sponsored by the NSERC of Canada and the Canada Research Chairs Program.

A preliminary version of this paper appeared in proceedings of the 24th and 25th International Symposium on Algorithms and Computation (ISAAC 2013 and ISAAC 2014).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

El-Zein, H., Lewenstein, M., Munro, J.I. et al. On the Succinct Representation of Equivalence Classes. Algorithmica 78, 1020–1040 (2017). https://doi.org/10.1007/s00453-016-0192-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0192-1

Keywords

Search

Navigation