Indexing tree structures through caterpillar decomposition

Creative Commons License

YILMAZ F., Demirci M. F.

17th Scandinavian Conference on Image Analysis, SCIA 2011, Ystad, İsveç, 23 - 27 Mayıs 2011, cilt.6688 LNCS, ss.687-696, (Tam Metin Bildiri)

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 6688 LNCS
  • Doi Numarası: 10.1007/978-3-642-21227-7_64
  • Basıldığı Şehir: Ystad
  • Basıldığı Ülke: İsveç
  • Sayfa Sayıları: ss.687-696
  • Anahtar Kelimeler: caterpillar decomposition, indexing, shape retrieval
  • Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
  • Ankara Yıldırım Beyazıt Üniversitesi Adresli: Evet

Özet

Graphs provide effective data structures modeling complex relations and schemaless data such as images, XML documents, circuits, compounds, and proteins. Given a query graph, efficiently finding all database graphs in which the query is a subgraph is an important problem raising in different domains. In this paper, we propose a new method for indexing tree structures based on a graph-theoretic concept called caterpillar decomposition and discuss its advantages over two previous indexing algorithms. Experimental evaluation of the proposed framework including the comparison with the previous approaches demonstrates the efficacy of the overall approach. © 2011 Springer-Verlag.