E-viri
Recenzirano
Odprti dostop
-
Wan, Xiaolong; Wang, Hongzhi
Information sciences, June 2022, 2022-06-00, Letnik: 599Journal Article
•A novel and efficient semi-external DFS algorithm EP-DFS is presented.•EP-DFS requires simpler CPU calculation and less memory space.•A novel index is devised to reduce the disk random accesses.•Extensive experiments are conducted on both real and synthetic datasets. As graphs grow in size, many real-world graphs are difficult to load into the primary memory of a computer. Thus, computing depth-first search (DFS) results (i.e., depth-first order or DFS-Tree) on the semi-external memory model is important to investigate. Semi-external algorithms assume that the primary memory can at least hold a spanning tree T of a graph G and gradually restructure T into a DFS-Tree, which is nontrivial. In this paper, we present a comprehensive study for the semi-external DFS problem. Based on a theoretical analysis of this problem, we introduce a new semi-external DFS algorithm called EP-DFS with a lightweight index N+-index. Unlike traditional algorithms, we focus on addressing such a complex problem efficiently with fewer I/Os, simpler CPU calculations (implementation-friendly), and less random I/O accesses (key-to-efficiency). Extensive experimental evaluations are performed on both synthetic and real graphs, and experimental results confirm that the proposed EP-DFS algorithm markedly outperforms existing algorithms.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.