A bottom-up subtree P of a labeled unordered tree T is such that, for each internal vertex u of P, all the children of u in T are also vertices of P, and the labels in corresponding positions also match. We aim at finding all the occurrences of a pattern tree P of m vertices as a bottom-up subtree of a text tree T of n vertices, m ≤ n. If the labels are single characters of a constant or of an n-integer alphabet the problem is solved in O(m + log n) time and (m) additional space, after a preprocessing of T is done in (n) time and (n) additional space. Note that the number of occurrences of P in T does not appear in the search time. For more complex labels the running times increase, becoming a function of the total length of all the labels in T and P if such labels are sequences of characters. Regarding T as a static text and P as the contents of a query on T, and assuming m = o(n), the response time for each P is sublinear in the size of the overall structure.

Bottom-up Subtree Isomorphism for Unordered Labeled Trees

LUCCIO, FABRIZIO;PAGLI, LINDA
2007

Abstract

A bottom-up subtree P of a labeled unordered tree T is such that, for each internal vertex u of P, all the children of u in T are also vertices of P, and the labels in corresponding positions also match. We aim at finding all the occurrences of a pattern tree P of m vertices as a bottom-up subtree of a text tree T of n vertices, m ≤ n. If the labels are single characters of a constant or of an n-integer alphabet the problem is solved in O(m + log n) time and (m) additional space, after a preprocessing of T is done in (n) time and (n) additional space. Note that the number of occurrences of P in T does not appear in the search time. For more complex labels the running times increase, becoming a function of the total length of all the labels in T and P if such labels are sequences of characters. Regarding T as a static text and P as the contents of a query on T, and assuming m = o(n), the response time for each P is sublinear in the size of the overall structure.
Luccio, Fabrizio; A., MESA ENRIQUEZ; P., OLIVARES RIEUMONT; Pagli, Linda
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/206214
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact