{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:19Z","timestamp":1740109279178,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,7,27]],"date-time":"2016-07-27T00:00:00Z","timestamp":1469577600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002784","name":"Canada Excellence Research Chairs, Government of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002784","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0192-1","type":"journal-article","created":{"date-parts":[[2016,7,27]],"date-time":"2016-07-27T11:50:35Z","timestamp":1469620235000},"page":"1020-1040","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Succinct Representation of Equivalence Classes"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8745-9540","authenticated-orcid":false,"given":"Hicham","family":"El-Zein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,27]]},"reference":[{"key":"192_CR1","doi-asserted-by":"crossref","unstructured":"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 \u201999, pp. 499\u2013506. ACM, New York, NY, USA (1999)","DOI":"10.1145\/301250.301383"},{"key":"192_CR2","unstructured":"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\u201314, 2003, Baltimore, Maryland, USA, pp. 689\u2013698 (2003)"},{"issue":"12","key":"192_CR3","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(98)00172-8","volume":"215","author":"A Andersson","year":"1999","unstructured":"Andersson, A., Miltersen, P.B., Thorup, M.: Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. 215(12), 337\u2013344 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"192_CR4","doi-asserted-by":"crossref","unstructured":"Barbay, J., Aleardi, L.C., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: Tokuyama, T. (ed.) Algorithms and Computation, pp. 316\u2013328. Springer, Berlin, Heidelberg (2007)","DOI":"10.1007\/978-3-540-77120-3_29"},{"issue":"4","key":"192_CR5","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"192_CR6","unstructured":"Blandford, D.K., Blelloch, G.E.: Compact representations of ordered sets. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201904, pp. 11\u201319. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2004)"},{"issue":"4","key":"192_CR7","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1137\/0215072","volume":"15","author":"N Blum","year":"1986","unstructured":"Blum, N.: On the single-operation worst-case time complexity of the disjoint set union problem. SIAM J. Comput. 15(4), 1021\u20131024 (1986)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"192_CR8","doi-asserted-by":"crossref","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM J. Comput. 28(5), 1627\u20131640 (1999)","journal-title":"SIAM J. Comput."},{"key":"192_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013247. Springer, Berlin, Heidelberg (2007)","DOI":"10.1007\/978-3-540-69507-3_19"},{"issue":"4","key":"192_CR10","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M Dietzfelbinger","year":"1994","unstructured":"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\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"192_CR11","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"192_CR12","doi-asserted-by":"crossref","unstructured":"Farzan, A., Munro, J.I.: Succinct representations of arbitrary graphs. In: Halperin, D., Mehlhorn, K. (eds.) Algorithms-ESA 2008, pp. 393\u2013404. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-87744-8_33"},{"issue":"1","key":"192_CR13","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/s00453-012-9664-0","volume":"68","author":"A Farzan","year":"2014","unstructured":"Farzan, A., Munro, J.I.: A uniform paradigm to succinctly encode various families of trees. Algorithmica 68(1), 16\u201340 (2014)","journal-title":"Algorithmica"},{"key":"192_CR14","unstructured":"Franceschini, G., Muthukrishnan, S., P\u0103tra\u015fcu, M.: Radix sorting with no extra space. In: Proceedings of the 15th Annual European Conference on Algorithms, ESA\u201907, pp. 94\u2013205. Springer, Berlin, Heidelberg (2007)"},{"issue":"3","key":"192_CR15","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"192_CR16","unstructured":"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\u201314, 2004, pp. 1\u201310 (2004)"},{"key":"192_CR17","unstructured":"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\u201328, 2009, Freiburg, Germany, pp. 517\u2013528 (2009)"},{"key":"192_CR18","doi-asserted-by":"crossref","unstructured":"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\u2013222, March (2006)","DOI":"10.1109\/DCC.2006.12"},{"key":"192_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013398. Springer, Berlin, Heidelberg (1998)","DOI":"10.1007\/BFb0028575"},{"issue":"1","key":"192_CR20","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","volume":"2","author":"GH Hardy","year":"1918","unstructured":"Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 2(1), 75\u2013115 (1918)","journal-title":"Proc. Lond. Math. Soc."},{"key":"192_CR21","unstructured":"Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University (1988)"},{"issue":"4","key":"192_CR22","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicat representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"192_CR23","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"192_CR24","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) Foundations of Software Technology and Theoretical Computer Science, pp. 37\u201342. Springer, Berlin, Heidelberg (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"192_CR25","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Nicholson, P.K.: Succinct posets. In: Proceedings of Algorithms-ESA 2012-20th Annual European Symposium, Ljubljana, Slovenia, September 10\u201312, 2012, pp. 743\u2013754 (2012)","DOI":"10.1007\/978-3-642-33090-2_64"},{"key":"192_CR26","doi-asserted-by":"crossref","unstructured":"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 \u201997, Miami Beach, Florida, USA, October 19\u201322, 1997, pp. 118\u2013126 (1997)","DOI":"10.1109\/SFCS.1997.646100"},{"issue":"2","key":"192_CR27","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1151","volume":"39","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms 39(2), 205\u2013222 (2001)","journal-title":"J. Algorithms"},{"key":"192_CR28","volume-title":"The Design of Dynamic Data Structures","author":"MH Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures, vol. 156. Springer, Berlin (1983)"},{"key":"192_CR29","doi-asserted-by":"crossref","unstructured":"Raman, R.: Generating random graphs efficiently. In: Dehne, F., Fiala, F., Koczkodaj, W. (eds.) Advances in Computing and Information ICCI \u201991. Lecture Notes in Computer Science, vol. 497, pp. 149\u2013160. Springer, Berlin, Heidelberg (1991)","DOI":"10.1007\/3-540-54029-6_164"},{"key":"192_CR30","unstructured":"Raman, R.: Eliminating Amortization: On Data Structures with Guaranteed Response Time. PhD thesis, Rochester, NY, USA. UMI Order No. GAX93-13880 (1993)"},{"issue":"4","key":"192_CR31","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"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)","journal-title":"ACM Trans Algorithms (TALG)"},{"issue":"1","key":"192_CR32","first-page":"1","volume":"1","author":"MH Smid","year":"1990","unstructured":"Smid, M.H.: A data structure for the union-find problem having good single-operation complexity. Algorithms Rev. 1(1), 1\u201312 (1990)","journal-title":"Algorithms Rev."},{"issue":"2","key":"192_CR33","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space (n). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0192-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0192-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0192-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0192-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T16:16:09Z","timestamp":1568218569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0192-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,27]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["192"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0192-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,7,27]]}}}