ELCA evaluation for keyword search on probabilistic XML data

As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive...

Full description

Saved in:
Bibliographic Details
Published in:World wide web (Bussum) 2013-03, Vol.16 (2), p.171-193
Main Authors: Zhou, Rui, Liu, Chengfei, Li, Jianxin, Yu, Jeffrey Xu
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Data management
Database Management
Extensible Markup Language
Information Systems Applications (incl.Internet)
Operating Systems
Probabilistic methods
Probability theory
Query processing
Searching
Semantics
XML
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result probability, time and space efficiency, and scalability.
ISSN:1386-145X
1573-1413
DOI:10.1007/s11280-012-0166-4