Efficiently computing RKN for keyword queries on XML data
Subtree results construction is a core problem in keyword query processing over XML data,for which com-puting the set of relevant keyword nodes (RKN) for each subtree's root node will greatly affect the overall system per-formance. Considering that existing methods cannot correctly identify RKN...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2014-07-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.07.006/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Subtree results construction is a core problem in keyword query processing over XML data,for which com-puting the set of relevant keyword nodes (RKN) for each subtree's root node will greatly affect the overall system per-formance. Considering that existing methods cannot correctly identify RKN for ELCA semantics,the definitions of RKN and the RKN-Base algorithm were proposed,which can correctly judge whether a given node is an RKN of some ELCA node by sequentially scanning the set of inverted lists once. As RKN-Base cannot avoid processing all useless nodes,an optimized algorithm,namely RKN-Optimized,was then proposed,which computes RKN sets based on the set of ELCA nodes, rather than the set of inverted lists as RKN-Base does. As a result,RKN-Optimized avoids processing useless nodes, and reduces the time complexity. The experimental results verified the efficiency of the proposed algorithms. |
|---|---|
| ISSN: | 1000-436X |