检索结果-内蒙古大学图书馆

An Efficient external memory Algorithm for Terrain Viewshed Computation

ACM TRANSACTIONS ON SPATIAL algorithms AND SYSTEMS 2016年第2期2卷 1–17页

作者： Ferreira, Chaulio R. Andrade, Marcus V. A. Magalhaes, Salles V. G. Franklin, W. Randolph DPI Fed Univ Vicosa Vicosa MG Brazil Rensselaer Polytech Inst Elect Comp & Syst Engn Dept Troy NY 12180 USA

This article presents TILEDVS, a fast external algorithm and implementation for computing viewsheds. TILEDVS is intended for terrains that are too large for internal memory, even more than 100,000x100,000 points. It subdivides the terrain into tiles that are stored compressed on disk and then paged into memory with a custom cache data structure and least recently used algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TILEDVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TILEDVS is very fast, for instance, processing a 104,000x104,000 terrain on a modest computer with only 512MB of RAM took only 112 hours. On large datasets, TILEDVS was several times faster than competing algorithms, such as the ones included in GRASS. The source code of TILEDVS is freely available for nonprofit researchers to study, use, and extend. A preliminary version of this algorithm appeared in a four-page ACM SIGSPATIAL GIS 2012 conference paper, "More Efficient Terrain Viewshed Computation on Massive Datasets Using external memory." This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons.

关键词： Design algorithms external memory algorithms terrain visibility geographic information systems

来源：评论

学校读者我要写书评

暂无评论

Flash memory efficient LTL model checking

引用

SCIENCE OF COMPUTER PROGRAMMING 2011年第2期76卷 136-157页

作者： Edelkamp, S. Sulewski, D. Barnat, J. Brim, L. Simecek, P. Univ Bremen D-2800 Bremen 33 Germany Masaryk Univ Brno Brno Czech Republic

As the capacity and speed of flash memories in form of solid state disks grow, they are becoming a practical alternative for standard magnetic drives. Currently, most solid-state disks are based on NAND technology and much faster than magnetic disks in random reads, while in random writes they are generally not. So far, large-scale LTL model checking algorithms have been designed to employ external memory optimized for magnetic disks. We propose algorithms optimized for flash memory access. In contrast to approaches relying on the delayed detection of duplicate states, in this work, we design and exploit appropriate hash functions to re-invent immediate duplicate detection. For flash memory efficient on-the-fly LTL model checking, which aims at finding any counter-example to the specified LTL property, we study hash functions adapted to the two-level hierarchy of RAM and flash memory. For flash memory efficient off-line LTL model checking, which aims at generating a minimal counterexample and scans the entire state space at least once, we analyze the effect of outsourcing a memory-based perfect hash function from RAM to flash memory. Since the characteristics of flash memories are different to magnetic hard disks, the existing I/O complexity model is no longer sufficient. Therefore, we provide an extended model for the computation of the I/O complexity adapted to flash memories that has a better fit to the observed behavior of our algorithms. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Model checking external memory algorithms Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

external-memory Multimaps

引用

ALGORITHMICA 2013年第1期67卷 23-48页

作者： Angelino, Elaine Goodrich, Michael T. Mitzenmacher, Michael Thaler, Justin Harvard Univ SEAS Cambridge MA 02138 USA Univ Calif Irvine Dept Comp Sci Irvine CA USA

Many data structures support dictionaries, also known as maps or associative arrays, which store and manage a set of key-value pairs. A multimap is generalization that allows multiple values to be associated with the same key. For example, the inverted file data structure that is used prevalently in the infrastructure supporting search engines is a type of multimap, where words are used as keys and document pointers are used as values. We study the multimap abstract data type and how it can be implemented efficiently online in external memory frameworks, with constant expected I/O performance. The key technique used to achieve our results is a combination of cuckoo hashing using buckets that hold multiple items with a multiqueue implementation to cope with varying numbers of values per key. Our external-memory results are for the standard two-level memory model.

关键词： external memory algorithms Cuckoo hashing Dictionaries Multimaps

来源：评论

学校读者我要写书评

暂无评论

RAM-Efficient external memory Sorting

RAM-Efficient External Memory Sorting

引用

24th International Symposium on algorithms and Computation

作者： Arge, Lars Thorup, Mikkel Aarhus Univ Dept Comp Sci Ctr Mass Data Algorithm MADALGO DK-8000 Aarhus Denmark Univ Copenhagen Dept Comp Sci Copenhagen Denmark

ISBN: (纸本)9783642450297

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we initiate a study of algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation. For sorting the conventional wisdom is to use merging base algorithms in external memory but we describe how this leads to suboptimal RAM performance. However, by using a splitting based algorithm in combination with existing RAM sorting techniques we obtain a sorting algorithm that is both I/O and RAM model efficient. Furthermore, we design an I/O- and RAM-efficient priority queue. Finally, we prove a sorting lower bound that shows that in most cases our results are optimal both in terms of I/O and internal computation.

关键词： I/O algorithms RAM algorithms external memory algorithms Sorting Priority queue

来源：评论

学校读者我要写书评

暂无评论

Engineering a Lightweight external memory Suffix Array Construction Algorithm

引用

MATHEMATICS IN COMPUTER SCIENCE 2017年第2期11卷 137-149页

作者： Karkkainen, Juha Kempa, Dominik Univ Helsinki Dept Comp Sci POB 68Gustaf Hallstromin Katu 2b FIN-00014 Helsinki Finland

We describe an external memory suffix array construction algorithm based on constructing suffix arrays for blocks of text and merging them into the full suffix array. The basic idea goes back over 20 years and there has been a couple of later improvements, but we describe several further improvements that make the algorithm much faster. In particular, we reduce the I/O volume of the algorithm by a factor . Our experiments show that the algorithm is the fastest suffix array construction algorithm when the size of the text is within a factor of about five from the size of the RAM in either direction, which is a common situation in practice.

关键词： Suffix array construction external memory algorithms Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Lempel-Ziv Parsing in external memory

Lempel-Ziv Parsing in External Memory

引用

Data Compression Conference (DCC)

作者： Karkkainen, Juha Kempa, Dominik Puglisi, Simon J. Univ Helsinki Helsinki Inst Informat Technol HIIT Helsinki Finland Univ Helsinki Dept Comp Sci Helsinki Finland

ISBN: (纸本)9781479938827

In the 35 years since its discovery, the Lempel-Ziv factorization (or LZ77 parsing) has become a fundamental method for data compression and string processing. In many applications, computation of the factorization is a time-space bottleneck. However, and despite the increasing need to apply LZ77 to massive data sets (for both storage and indexing), no algorithm to date scales to inputs that exceed the size of RAM. In this paper we describe the first algorithms for computing the LZ77 parsing efficiently using external memory.

关键词： external memory algorithms Lempel-Ziv factorization Text compression

来源：评论

学校读者我要写书评

暂无评论

Adiar Binary Decision Diagrams in external memory 28th

Adiar Binary Decision Diagrams in External Memory

引用

28th International Conference on Tools and algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the 25th European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Solvsten, Steffan Christ van de Pol, Jaco Jakobsen, Anna Blume Thomasen, Mathias Weller Berg Aarhus Univ Aarhus Denmark

ISBN: (纸本)9783030995270;9783030995263

We follow up on the idea of Lars Arge to rephrase the Reduce and Apply operations of Binary Decision Diagrams (BDDs) as iterative I/O-efficient algorithms. We identify multiple avenues to simplify and improve the performance of his proposed algorithms. Furthermore, we extend the technique to other common BDD operations, many of which are not derivable using Apply operations alone. We provide asymptotic improvements to the few procedures that can be derived using Apply. Our work has culminated in a BDD package named Adiar that is able to efficiently manipulate BDDs that outgrow main memory. This makes Adiar surpass the limits of conventional BDD packages that use recursive depth-first algorithms. It is able to do so while still achieving a satisfactory performance compared to other BDD packages: Adiar, in parts using the disk, is on instances larger than 9.5 GiB only 1.47 to 3.69 times slower compared to CUDD and Sylvan, exclusively using main memory. Yet, Adiar is able to obtain this performance at a fraction of the main memory needed by conventional BDD packages to function.

关键词： Time-forward Processing external memory algorithms Binary Decision Diagrams

来源：评论

学校读者我要写书评

暂无评论

Adiar 1.1 Zero-Suppressed Decision Diagrams in external memory 15th

Adiar 1.1 Zero-Suppressed Decision Diagrams in External Memo...

引用

15th International Symposium on NASA Formal Methods (NFM)

作者： Solvsten, Steffan Christ van de Pol, Jaco Aarhus Univ Aarhus Denmark

We outline how support for Zero-suppressed Decision Diagrams (ZDDs) has been achieved for the external memory BDD package Adiar. This allows one to use ZDDs to solve various problems despite their size exceed the mach... 详细信息

ISBN: (纸本)9783031331695;9783031331701

关键词： Zero-suppressed Decision Diagrams external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Listing Dense Subgraphs in Small memory 9

Listing Dense Subgraphs in Small Memory

引用

9th Latin American Web Congress (LA-WEB)

作者： Pinto, Patricio Cruces, Nataly Hernandez, Cecilia Univ Concepcion Dept Comp Sci Concepcion Chile

ISBN: (纸本)9781479969531

Listing relevant patterns from graphs is becoming increasingly challenging as Web and social graphs are growing in size at a great rate. This scenario requires to process information more efficiently, including the need of processing data that cannot fit in main memory. Typical approaches for processing data using limited main memory include the streaming and external memory models. This paper addresses the problem of listing dense subgraphs from Web and social graphs using little memory. We propose an external memory algorithm based on K-way merge-sort for clustering and reordering input graphs. We also propose mining heuristics that work well with different stream orders such as URL, BFS, and cluster-based. Our experimental evaluation shows that on Web graphs, in comparison with the in-memory algorithm, the streaming mining heuristic is able to find between 70 and 96% of edges participating in dense subgraphs, uses only between 17 and 25% of the memory, and running times are between 34 and 65%. We further consider an application that uses these dense subgraphs for compressing Web graphs with a representation that enables querying the collection of subgraphs for pattern recovery and basic statistics without decompression.

关键词： Web Graphs Graph Pattern Listing Streaming algorithms external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

LCP array construction in external memory

引用

ACM Journal of Experimental Algorithmics 2016年第2期21卷 1–22页

作者： Kärkkäinen, Juha Kempa, Dominik Helsinki Institute of Information Technology Department of Computer Science University of Helsinki P.O. Box 68 (Gustaf Hällströmin katu 2b) FI-00014 Finland

One of the most important data structures for string processing-the suffix array-needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use an external memory suffix array construction algorithm (SACA) with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any SACA, including a better one developed in the future. © 2016 ACM.

关键词： external memory algorithms LCP array Suffix array

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：