Boosting twig joins in probabilistic XML

Siqi Liu; Guoren Wang

doi:10.1007/978-3-642-23091-2_5

Boosting twig joins in probabilistic XML

Siqi Liu^*, Guoren Wang

^*Corresponding author for this work

Northeastern University China

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

In practice, uncertainty of data is inherent. Probabilistic XML has been proposed to manage semistructured uncertain data. In this paper, we study twig query evaluation over probabilistic XML with probability thresholds. First we propose an encoding scheme for probabilistic XML. Then we design a novel streaming scheme which enables us to prune off useless inputs. Based on the encoding scheme and streaming scheme, we develop an algorithm to evaluate twig queries over probabilistic XML. Finally, we conduct experiments to study the performance of our algorithm.

Original language	English
Title of host publication	Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings
Pages	51-58
Number of pages	8
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-23091-2_5
Publication status	Published - 2011
Externally published	Yes
Event	22nd International Conference on Database and Expert Systems Applications, DEXA 2011 - Toulouse, France Duration: 29 Aug 2011 → 2 Sept 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6861 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on Database and Expert Systems Applications, DEXA 2011
Country/Territory	France
City	Toulouse
Period	29/08/11 → 2/09/11

Access to Document

10.1007/978-3-642-23091-2_5

Cite this

Liu, S., & Wang, G. (2011). Boosting twig joins in probabilistic XML. In Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings (PART 2 ed., pp. 51-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6861 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-23091-2_5

@inproceedings{dd84716015774066991506b7d2402c7b,

title = "Boosting twig joins in probabilistic XML",

abstract = "In practice, uncertainty of data is inherent. Probabilistic XML has been proposed to manage semistructured uncertain data. In this paper, we study twig query evaluation over probabilistic XML with probability thresholds. First we propose an encoding scheme for probabilistic XML. Then we design a novel streaming scheme which enables us to prune off useless inputs. Based on the encoding scheme and streaming scheme, we develop an algorithm to evaluate twig queries over probabilistic XML. Finally, we conduct experiments to study the performance of our algorithm.",

author = "Siqi Liu and Guoren Wang",

year = "2011",

doi = "10.1007/978-3-642-23091-2_5",

language = "English",

isbn = "9783642230905",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "51--58",

booktitle = "Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings",

edition = "PART 2",

note = "22nd International Conference on Database and Expert Systems Applications, DEXA 2011 ; Conference date: 29-08-2011 Through 02-09-2011",

}

Liu, S & Wang, G 2011, Boosting twig joins in probabilistic XML. in Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6861 LNCS, pp. 51-58, 22nd International Conference on Database and Expert Systems Applications, DEXA 2011, Toulouse, France, 29/08/11. https://doi.org/10.1007/978-3-642-23091-2_5

Boosting twig joins in probabilistic XML. / Liu, Siqi; Wang, Guoren.
Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings. PART 2. ed. 2011. p. 51-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6861 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Boosting twig joins in probabilistic XML

AU - Liu, Siqi

AU - Wang, Guoren

PY - 2011

Y1 - 2011

N2 - In practice, uncertainty of data is inherent. Probabilistic XML has been proposed to manage semistructured uncertain data. In this paper, we study twig query evaluation over probabilistic XML with probability thresholds. First we propose an encoding scheme for probabilistic XML. Then we design a novel streaming scheme which enables us to prune off useless inputs. Based on the encoding scheme and streaming scheme, we develop an algorithm to evaluate twig queries over probabilistic XML. Finally, we conduct experiments to study the performance of our algorithm.

AB - In practice, uncertainty of data is inherent. Probabilistic XML has been proposed to manage semistructured uncertain data. In this paper, we study twig query evaluation over probabilistic XML with probability thresholds. First we propose an encoding scheme for probabilistic XML. Then we design a novel streaming scheme which enables us to prune off useless inputs. Based on the encoding scheme and streaming scheme, we develop an algorithm to evaluate twig queries over probabilistic XML. Finally, we conduct experiments to study the performance of our algorithm.

UR - http://www.scopus.com/inward/record.url?scp=80052790671&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23091-2_5

DO - 10.1007/978-3-642-23091-2_5

M3 - Conference contribution

AN - SCOPUS:80052790671

SN - 9783642230905

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 58

BT - Database and Expert Systems Applications - 22nd International Conference, DEXA 2011, Proceedings

T2 - 22nd International Conference on Database and Expert Systems Applications, DEXA 2011

Y2 - 29 August 2011 through 2 September 2011

ER -

Boosting twig joins in probabilistic XML

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this