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

Scalable disk-based topic modeling for memory limited devices

INFORMATION SCIENCES 2020年第0期516卷 353-369页

作者： Kim, Byungju Lee, Dongha Oh, Jinoh Yu, Hwanjo Pohang Univ Sci & Technol Pohang South Korea Adobe Syst Inc San Jose CA USA

disk-based algorithms have the ability to process large-scale data which do not fit into the memory, so they provide good scalability to a mobile device with limited memory resources. In general, the speed of disk I/O is much slower than that of memory access, the total amount of disk I/O is the most crucial factor which determines the efficiency of disk-based algorithms. This paper proposes BlockLDA, an efficient disk-based Latent Dirichlet Allocation (LDA) inference algorithm which can efficiently infer an LDA model when both of the data and model do not fit into the memory. BlockLDA manages the data and model as a set of small blocks so that it can support efficient disk I/O as well as process the LDA inference in a block-wise manner. In addition, it utilizes advanced techniques which help to minimize the amount of disk I/O, including 1) a space reduction algorithm to dynamically manage the block-wise model considering its changing sparsity and 2) a local scheduling algorithm to carefully select the next data blocks so that the number of page faults is minimized. Our experimental results demonstrate that BlockLDA shows better scalability and efficiency than its disk-based and in-memory competitors under the memory-limited environment. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Latent Dirichlet Allocation Parallel algorithm disk-based algorithm

来源：评论

学校读者我要写书评

暂无评论

SGMiner: A Fast and Scalable GPU-based Frequent Pattern Miner on SSDs

引用

IEEE ACCESS 2022年 10卷 62502-62519页

作者： Chon, Kang-Wook Yi, Eunjeong Kim, Min-Soo Korea Inst Sci & Technol Informat Div Natl Supercomp Daejeon South Korea Daegu Gyeongbuk Inst Sci & Technol Dept Informat & Commun Engn Daegu South Korea Korea Adv Inst Sci & Technol Sch Comp Daejeon South Korea

Frequent itemset mining is extensively employed as an essential data mining technique. Nevertheless, as the data size grows, the applicability of this method decreases owing to the relatively poor performance of the existing methods. Though numerous efficient sequential frequent itemset mining methods have been developed, the performance that can be achieved is clearly limited by the fact that they exploit only one thread. To overcome these limitations, a number of parallel methods using multi-core central processing units (CPUs), multiple machines or many-core graphic processing units (GPU) have been proposed. However, these methods are relatively slow in performance and have low scalability, mainly owing to large memory requirements for intermediate data, significant disk I/Os, and heavy computation. In this study, to resolve the aforementioned problems, we propose SGMiner, which is a new, fast, and scalable GPU-and disk-based method on a single machine equipped with multiple graphic processing units (GPUs) and multiple solid-state drives (SSDs) for extracting frequent patterns. It is based on an algorithm similar to the Apriori algorithm and neither has intermediate data nor large disk I/O overheads owing to its exploitation of SSDs. Moreover, we propose storing transaction databases, namely bitmap transaction chunks, in SSDs, streaming the chunks to GPU device memory via the main memory with reduced I/O overhead, and performing fast support counting with GPUs based on the chunks. In addition, when exploiting multiple GPUs and SSDs, it proposes a concept of replicating bitmap transaction chunks stored in SSDs to GPUs in a streaming fashion. This could allow an almost equal workload to be distributed evenly across multiple GPUs with reduced I/O overheads. The experiments we conducted demonstrate that SGMiner outperforms the existing methods in terms of scalability and performance with enhanced robustness.

关键词： Big data frequent pattern mining parallel algorithm GPUs scalable algorithm disk-based algorithm

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Pattern Search Using Reduced-Space On-disk Suffix Arrays

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第8期26卷 1918-1931页

作者： Gog, Simon Moffat, Alistair Culpepper, J. Shane Turpin, Andrew Wirth, Anthony Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic 3001 Australia

The suffix array is an efficient data structure for in-memory pattern search. Suffix arrays can also be used for external-memory pattern search, via two-level structures that use an internal index to identify the correct block of suffix pointers. In this paper, we describe a new two-level suffix array-based index structure that requires significantly less disk space than previous approaches. Key to the saving is the use of disk blocks that are based on prefixes rather than the more usual uniform-sampling approach, allowing reductions between blocks and subparts of other blocks. We also describe a new in-memory structure-the condensed BWT-and show that it allows common patterns to be resolved without access to the text. Experiments using 64 GB of English web text on a computer with 4 GB of main memory demonstrate the speed and versatility of the new approach. For this data, the index is around one-third the size of previous two-level mechanisms;and the memory footprint of as little as 1% of the text size means that queries can be processed more quickly than is possible with a compact FM-INDEX.

关键词： String search pattern matching suffix array Burrows-Wheeler transform succinct data structure disk-based algorithm experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Adding Compression and Blended Search to a Compact Two-Level Suffix Array

Adding Compression and Blended Search to a Compact Two-Level...

引用

20th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Gog, Simon Moffat, Alistair Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia

ISBN: (纸本)9783319024325;9783319024318

The suffix array is an efficient in-memory data structure for pattern search;and two-level variants also exist that are suited to external searching and can handle strings larger than the available memory. Assuming the latter situation, we introduce a factor-based mechanism for compressing the text string that integrates seamlessly with the in-memory index search structure, rather than requiring a separate dictionary. We also introduce a mixture of indexed and sequential pattern search in a trade-off that allows further space savings. Experiments on a 4 GB computer with 62.5 GB of English text show that a two-level arrangement is possible in which around 2.5% of the text size is required as an index and for which the disk-resident components, including the text itself, occupy less than twice the space of the original text;and with which count queries can be carried out using two disk accesses and less than two milliseconds of CPU time.

关键词： string search pattern matching suffix array Burrows-Wheeler transform succinct data structure disk-based algorithm experimental evaluation.

来源：评论

学校读者我要写书评

暂无评论

Strategic Pattern Search in Factor-Compressed Text 21

Strategic Pattern Search in Factor-Compressed Text

引用

21st International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Gog, Simon Moffat, Alistair Petri, Matthias Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia

ISBN: (纸本)9783319119182;9783319119175

We consider the problem of pattern-search in compressed text in a context in which: (a) the text is stored as a sequence of factors against a static phrase-book;(b) decoding of factors is from right-to-left;and (c) extraction of each symbol in each factor requires Theta(log sigma) time, where sigma is the size of the original alphabet. To determine possible alignments given information about decoded characters we introduce two Boyer-Moore-like searching mechanisms, including one that makes use of a suffix array constructed over the pattern. The new mechanisms decode fewer than half the symbols that are required by a sequential left-to-right search such as the Knuth-Morris-Pratt approach, a saving that translates directly into improved execution time. Experiments with a two-level suffix array index structure for 4 GB of English text demonstrate the usefulness of the new techniques.

关键词： string search pattern matching suffix array Burrows-Wheeler transform succinct data structure disk-based algorithm experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

SSDMiner: A Scalable and Fast disk-based Frequent Pattern Miner 7th

SSDMiner: A Scalable and Fast Disk-Based Frequent Pattern Mi...

引用

7th International Conference on Emerging Databases - Technologies, Applications, and Theory (EDB)

作者： Chon, Kang-Wook Kim, Min-Soo DGIST Daegu South Korea

ISBN: (纸本)9789811065200;9789811065194

Frequent itemset mining is widely used as a fundamental data mining technique. Recently, there have been proposed a number of disk-based methods. However, the existing methods still do not have a good scalability due to large-scale intermediate data and non-trivial disk I/Os. We propose SSDMiner, a new fast and scalable disk-based method for frequent itemset mining that is based on Apriori-like method and has no intermediate data and small disk I/O overheads by exploiting SSD. We propose a concept of bitmap chunks for storing transactional database in disks and a fast support counting based on bitmap chunks. Through experiments, we demonstrate that SSDMiner has the enhanced scalability and the good performance similar to that in memory-based methods with robustness.

关键词： Frequent pattern mining Scalable algorithm SSD disk-based algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：