Counting relaxed twig matches in a tree

Dongwon Lee, Divesh Srivastava

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We consider the problem of accurately estimating the number of approximate XML answers for a given query, and propose an efficient method that (1) accurately computes selectivity estimates for each relaxed XML query, using a natural generalization of the correlated subpath tree (CST) summary structure, and (2) carefully combines these estimates by analyzing the nature of overlap between the different relaxed twig queries.

Original languageEnglish (US)
Pages (from-to)88-99
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Dec 1 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Counting relaxed twig matches in a tree'. Together they form a unique fingerprint.

Cite this