BiRch:a bidirectional search algorithm for k-step reachability queries
A new bidirectional processing algorithm,namely BiRch was proposed.When checking whether a vertex u can reach v within k steps,BiRch firstly compared the out-degree of u and the in-degree of v,and processed the one with smaller degree,such that to avoid large indexes and the inefficiency due to larg...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2015-08-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015230/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539667159154688 |
|---|---|
| author | Jun-feng ZHOU Wei CHEN Chun-ping FEI Zi-yang CHEN |
| author_facet | Jun-feng ZHOU Wei CHEN Chun-ping FEI Zi-yang CHEN |
| author_sort | Jun-feng ZHOU |
| collection | DOAJ |
| description | A new bidirectional processing algorithm,namely BiRch was proposed.When checking whether a vertex u can reach v within k steps,BiRch firstly compared the out-degree of u and the in-degree of v,and processed the one with smaller degree,such that to avoid large indexes and the inefficiency due to large degree.Two pruning strategies were proposed based on bidirectional breadth-first levels and bidirectional topological levels,such that to reduce the number of visited vertexes.Experimental results on 19 real datasets verify the efficiency of the proposed method in terms of different metrics,including indexing time,index size,query processing time,the number of visited vertexes,and scalability. |
| format | Article |
| id | doaj-art-8a7a7d7d139b4fc3b57ae3ca032f79d6 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2015-08-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-8a7a7d7d139b4fc3b57ae3ca032f79d62025-01-14T06:53:19ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2015-08-0136506059694755BiRch:a bidirectional search algorithm for k-step reachability queriesJun-feng ZHOUWei CHENChun-ping FEIZi-yang CHENA new bidirectional processing algorithm,namely BiRch was proposed.When checking whether a vertex u can reach v within k steps,BiRch firstly compared the out-degree of u and the in-degree of v,and processed the one with smaller degree,such that to avoid large indexes and the inefficiency due to large degree.Two pruning strategies were proposed based on bidirectional breadth-first levels and bidirectional topological levels,such that to reduce the number of visited vertexes.Experimental results on 19 real datasets verify the efficiency of the proposed method in terms of different metrics,including indexing time,index size,query processing time,the number of visited vertexes,and scalability.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015230/k-step reachability querybidirectional searchbreadth leveltopological level |
| spellingShingle | Jun-feng ZHOU Wei CHEN Chun-ping FEI Zi-yang CHEN BiRch:a bidirectional search algorithm for k-step reachability queries Tongxin xuebao k-step reachability query bidirectional search breadth level topological level |
| title | BiRch:a bidirectional search algorithm for k-step reachability queries |
| title_full | BiRch:a bidirectional search algorithm for k-step reachability queries |
| title_fullStr | BiRch:a bidirectional search algorithm for k-step reachability queries |
| title_full_unstemmed | BiRch:a bidirectional search algorithm for k-step reachability queries |
| title_short | BiRch:a bidirectional search algorithm for k-step reachability queries |
| title_sort | birch a bidirectional search algorithm for k step reachability queries |
| topic | k-step reachability query bidirectional search breadth level topological level |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015230/ |
| work_keys_str_mv | AT junfengzhou birchabidirectionalsearchalgorithmforkstepreachabilityqueries AT weichen birchabidirectionalsearchalgorithmforkstepreachabilityqueries AT chunpingfei birchabidirectionalsearchalgorithmforkstepreachabilityqueries AT ziyangchen birchabidirectionalsearchalgorithmforkstepreachabilityqueries |