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!
|
| _version_ | 1841539754540138496 |
|---|---|
| author | HENZi-yang C ANGXuan W ANGXian T |
| author_facet | HENZi-yang C ANGXuan W ANGXian T |
| author_sort | HENZi-yang C |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a35a88015802400da4a787b46db7f8b0 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2014-07-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-a35a88015802400da4a787b46db7f8b02025-01-14T06:43:42ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2014-07-0135465559682536Efficiently computing RKN for keyword queries on XML dataHENZi-yang CANGXuan WANGXian TSubtree 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.http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.07.006/XMLsubtree results constructionELCARKN |
| spellingShingle | HENZi-yang C ANGXuan W ANGXian T Efficiently computing RKN for keyword queries on XML data Tongxin xuebao XML subtree results construction ELCA RKN |
| title | Efficiently computing RKN for keyword queries on XML data |
| title_full | Efficiently computing RKN for keyword queries on XML data |
| title_fullStr | Efficiently computing RKN for keyword queries on XML data |
| title_full_unstemmed | Efficiently computing RKN for keyword queries on XML data |
| title_short | Efficiently computing RKN for keyword queries on XML data |
| title_sort | efficiently computing rkn for keyword queries on xml data |
| topic | XML subtree results construction ELCA RKN |
| url | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2014.07.006/ |
| work_keys_str_mv | AT henziyangc efficientlycomputingrknforkeywordqueriesonxmldata AT angxuanw efficientlycomputingrknforkeywordqueriesonxmldata AT angxiant efficientlycomputingrknforkeywordqueriesonxmldata |