Tree compression with top trees

Philip Bille, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We introduce a new compression scheme for labeled trees based on top trees [3]. 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.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I
PublisherSpringer
Publication date2013
Pages160-171
ISBN (Print)978-3-642-39205-4
ISBN (Electronic)978-3-642-39206-1
DOIs
Publication statusPublished - 2013
Event40th International Colloquium on Automata, Languages and Programming (ICALP 2013) - Riga, Latvia
Duration: 8 Jul 201312 Jul 2013
http://www.icalp2013.lu.lv/

Conference

Conference40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
CountryLatvia
CityRiga
Period08/07/201312/07/2013
Internet address
SeriesLecture Notes in Computer Science
Volume7965
ISSN0302-9743

Cite this