@inproceedings{10.1007/978-3-540-69068-9_26,
    abstract = "k-ary trees are a fundamental data structure in many text-processing algorithms (e.g., text searching). The traditional pointer-based representation of trees is space consuming, and hence only relatively small trees can be kept in main memory. Nowadays, however, many applications need to store a huge amount of information. In this paper we present a succinct representation for dynamic k-ary trees of n nodes, requiring 2n + n log k + o(n log k) bits of space, which is close to the information-theoretic lower bound. Unlike alternative representations where the operations on the tree can be usually computed in O(logn) time, our data structure is able to take advantage of asymptotically smaller values of k, supporting the basic operations parent and child in O(log k + log log n) time, which is o(log n) time whenever log k = o(log n). Insertions and deletions of leaves in the tree are supported in amortized time. Our representation also supports more specialized operations (like subtreesize, depth, etc.), and provides a new trade-off when k = O(1) allowing faster updates (in O(log log n) amortized time, versus the amortized time of O((log log n)1 + ε ), for ε > 0, from Raman and Rao [21]), at the cost of slower basic operations (in O(log log n) time, versus O(1) time of [21]). © 2008 Springer-Verlag Berlin Heidelberg.",
    year = "2008",
    title = "An improved succinct representation for dynamic k-ary trees",
    volume = "5029 LNCS",
    pages = "277-289",
    doi = "10.1007/978-3-540-69068-9\_26",
    booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)"
}

{"_id":"PQWeRdvNvihGKvddS","bibbaseid":"anonymous-animprovedsuccinctrepresentationfordynamickarytrees-2008","downloads":0,"creationDate":"2017-03-31T19:29:34.764Z","title":"An improved succinct representation for dynamic k-ary trees","author_short":null,"year":2008,"bibtype":"inproceedings","biburl":"https://1fichier.com/?j9cpurkmnv","bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"k-ary trees are a fundamental data structure in many text-processing algorithms (e.g., text searching). The traditional pointer-based representation of trees is space consuming, and hence only relatively small trees can be kept in main memory. Nowadays, however, many applications need to store a huge amount of information. In this paper we present a succinct representation for dynamic k-ary trees of n nodes, requiring 2n + n log k + o(n log k) bits of space, which is close to the information-theoretic lower bound. Unlike alternative representations where the operations on the tree can be usually computed in O(logn) time, our data structure is able to take advantage of asymptotically smaller values of k, supporting the basic operations parent and child in O(log k + log log n) time, which is o(log n) time whenever log k = o(log n). Insertions and deletions of leaves in the tree are supported in amortized time. Our representation also supports more specialized operations (like subtreesize, depth, etc.), and provides a new trade-off when k = O(1) allowing faster updates (in O(log log n) amortized time, versus the amortized time of O((log log n)1 + ε ), for ε > 0, from Raman and Rao [21]), at the cost of slower basic operations (in O(log log n) time, versus O(1) time of [21]). © 2008 Springer-Verlag Berlin Heidelberg.","year":"2008","title":"An improved succinct representation for dynamic k-ary trees","volume":"5029 LNCS","pages":"277-289","doi":"10.1007/978-3-540-69068-9_26","booktitle":"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","bibtex":"@inproceedings{10.1007/978-3-540-69068-9_26,\n abstract = \"k-ary trees are a fundamental data structure in many text-processing algorithms (e.g., text searching). The traditional pointer-based representation of trees is space consuming, and hence only relatively small trees can be kept in main memory. Nowadays, however, many applications need to store a huge amount of information. In this paper we present a succinct representation for dynamic k-ary trees of n nodes, requiring 2n + n log k + o(n log k) bits of space, which is close to the information-theoretic lower bound. Unlike alternative representations where the operations on the tree can be usually computed in O(logn) time, our data structure is able to take advantage of asymptotically smaller values of k, supporting the basic operations parent and child in O(log k + log log n) time, which is o(log n) time whenever log k = o(log n). Insertions and deletions of leaves in the tree are supported in amortized time. Our representation also supports more specialized operations (like subtreesize, depth, etc.), and provides a new trade-off when k = O(1) allowing faster updates (in O(log log n) amortized time, versus the amortized time of O((log log n)1 + ε ), for ε > 0, from Raman and Rao [21]), at the cost of slower basic operations (in O(log log n) time, versus O(1) time of [21]). © 2008 Springer-Verlag Berlin Heidelberg.\",\n year = \"2008\",\n title = \"An improved succinct representation for dynamic k-ary trees\",\n volume = \"5029 LNCS\",\n pages = \"277-289\",\n doi = \"10.1007/978-3-540-69068-9\\_26\",\n booktitle = \"Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)\"\n}\n\n","key":"10.1007/978-3-540-69068-9_26","id":"10.1007/978-3-540-69068-9_26","bibbaseid":"anonymous-animprovedsuccinctrepresentationfordynamickarytrees-2008","urls":{},"downloads":0,"html":""},"search_terms":["improved","succinct","representation","dynamic","ary","trees"],"keywords":[],"authorIDs":[],"dataSources":["gKiCRHjjC2iGthGEx"]}