Tree compression with top trees

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Preprint , Conference object 01 Jan 2013Embargo end date: 01 Jan 2013 Denmark English Publisher:Elsevier BVJournal:Information and Computation, volume 243, pages 166-177 (issn: 0890-5401,

Copyright policy )Funded by:NSF | AF: Medium: Collaborative...

Authors: Philip Bille; Inge Li Gørtz; Gad M. Landau; Oren Weimann;

doi: 10.1016/j.ic.2014.12.012 , 10.1007/978-3-642-39206-1_14 , 10.48550/arxiv.1304.5702

arXiv: 1304.5702

Tree compression with top trees

- Summary
- Subjects
- Metrics

Abstract

We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.

An extended abstract of this paper appeared at the 40th International Colloquium on Automata, Languages and Programming

Country

Denmark

Related Organizations

Keywords

FOS: Computer and information sciences, Data structures, Tree compression, top trees, tree compression, pattern matching, Top trees, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Pattern matching, Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science), Searching and sorting

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	33
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%