Name
Title | ||
|---|---|---|
Faster Algorithms for Tree Similarity Based on Compressed Enumeration of Bounded-Sized Ordered Subtrees. |
Abstract | ||
|---|---|---|
In this paper, we study efficient computation of tree similarity for ordered trees based on compressed subtree enumeration. The compressed subtree enumeration is a new paradigm of enumeration algorithms that enumerates all subtrees of an input tree T in the form of their compressed bit signatures. For the task of enumerating all compressed bit signatures of k-subtrees in an ordered tree T, we first present an enumeration algorithm in O(k)-delay, and then, present another enumeration algorithm in constant-delay using O(n) time preprocessing that directly outputs bit signatures. These algorithms are designed based on bit-parallel speed-up technique for signature maintenance. By experiments on real and artificial datasets, both algorithms showed approximately 22% to 36% speed-up over the algorithms without bit-parallel signature maintenance. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-41062-8_8 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Feature vector,Computer science,Enumeration,Tree (data structure),Algorithm,Preprocessor,Enumeration algorithm,Computation,Bounded function | Conference | 8199 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kunihiro Wasa | 1 | 13 | 10.85 |
| Kouichi Hirata | 2 | 130 | 32.04 |
| Takeaki Uno | 3 | 1319 | 107.99 |
| Hiroki Arimura | 4 | 1130 | 92.90 |