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

A theoretical and experimental study on the construction of suffix arrays in external memory

ALGORITHMICA 2002年第1期32卷 1-35页

作者： Crauser, A Ferragina, P Max Planck Inst Informat Saarbrucken Germany Univ Pisa Dipartimento Informat Pisa Italy

The construction of full-text indexes on very large text collections is nowadays a hot problem. The suffix array [32] is one of the most attractive full-text indexing data structures due to its simplicity, space efficiency and powerful/fast search operations supported. In this paper we analyze, both theoretically and experimentally, the I/O complexity and the working space of six algorithms for constructing large suffix arrays. Three of them are state-of-the-art, the other three algorithms are our new proposals. We perform a set of experiments based on three different data sets (English texts, amino-acid sequences and random texts) and give a precise hierarchy of these algorithms according to their working-space versus construction-time tradeoff. Given the current trends in model design [12], [32] and disk technology [29], [30], we pose particular attention to differentiate between "random' and "contiguous" disk accesses, in order to explain reasonably some practical I/O phenomena which are related to the experimental behavior of these algorithms and that would otherwise be meaningless in the light of other simpler external-memory models. We also address two other issues. The former is concerned with the problem of building word indexes;we show that our results can be successfully applied to this case too, without any loss in efficiency and without compromising the simplicity of programming to achieve a uniform, simple and efficient approach to both the two indexing models. The latter issue is related to the intriguing and apparently counterintuitive "contradiction" between the effective practical performance of the well-known Baeza-Yates Gonnet-Snider algorithm [17], verified in our experiments, and its unappealing worst-case behavior. We devise a new external-memory algorithm that follows the basic philosophy underlying that algorithm but in a significantly different manner, thus resulting in a novel approach which combines good worst-case bounds with efficient pr

关键词： suffix array large data sets external-memory model text indexing full-text and word-based models

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithms for Two Extensions of LPF Table: The Power of suffix arrays

Efficient Algorithms for Two Extensions of LPF Table: The Po...

引用

36th Conference on Current Trends in Theory and Practice of Computer Science

作者： Crochemore, Maxime Iliopoulos, Costas S. Kubica, Marcin Rytter, Wojciech Walen, Tomasz Kings Coll London Dept Comp Sci London WC2R 2LS England Univ Warsaw Inst Informat Warsaw Poland Univ Paris Est Paris France Curtin Univ Technol Digital Ecosyst & Business Intelligence Inst Perth WA 6845 Australia Copernicus Univ Fac Math & Informat Torun Poland

ISBN: (纸本)9783642112652

suffix arrays provide a powerful data structure to solve several questions related to the structure of all the factors of a string. We show how they can be used to compute efficiently two new tables storing different types of previous factors (past segments) of a string. The concept of a longest previous factor is inherent to Ziv-Lempel factorization of strings in text compression, as well as in statistics of repetitions and symmetries. The longest previous reverse factor for a given position is the longest factor starting at i, such that its reverse copy occurs before, while the longest previous non-overlapping factor is the longest;factor v starting at i which has an exact copy occurring before. The previous copies of the factors are required to occur in the prefix ending at position i - 1. We design algorithms computing the table of longest previous reverse factors (LPrF table) and the table of longest previous non-overlapping factors (LPnF table). The latter table is useful to compute repetitions while the former is a useful tool for extracting symmetries. These tables are computed, using two previously computed read-only arrays (SUF and LCP) composing the suffix array, in linear time on any integer alphabet. The tables have not been explicitly considered before, but they have several applications and they are natural extensions of the LPF table which has been studied thoroughly before. Our results improve on the previous ones in several ways. The running time of the computation no longer depends on the size of the alphabet, which drops a log factor. Moreover the newly introduced tables store additional information on the structure of the string, helpful to improve, for example, gapped palindrome detection and text compression using reverse factors.

关键词： Longest previous reverse factor longest previous non-overlapping factor longest previous factor palindrome runs suffix array text compression

来源：评论

学校读者我要写书评

暂无评论

Collapsing the Hierarchy of Compressed Data Structures: suffix arrays in Optimal Compressed Space 64

Collapsing the Hierarchy of Compressed Data Structures: Suff...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Kempa, Dominik Kociumaka, Tomasz SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

ISBN: (纸本)9798350318944

The last two decades have witnessed a dramatic increase in the amount of highly repetitive datasets consisting of sequential data (strings, texts). Processing these massive amounts of data using conventional data structures is infeasible. This fueled the development of compressed text indexes, which efficiently answer various queries on a given text, typically in polylogarithmic time, while occupying space proportional to the compressed representation of the text. There exist numerous structures supporting queries ranging from simple "local" queries, such as random access, through more complex ones, including longest common extension (LCE) queries, to the most powerful queries, such as the suffix array (SA) functionality. Alongside the rich repertoire of queries followed a detailed study of the trade-off between the size and functionality of compressed indexes (see: Navarro;ACM Comput. Surv. 2021). It is widely accepted that this hierarchy of structures tells a simple story: the more powerful the queries, the more space is needed. On the one hand, random access, the most basic query, can be supported using O(delta log n log sigma/delta log n) space (where n is the length of the text, sigma is the alphabet size, and delta is the text's substring complexity), which is known to be the asymptotically smallest space sufficient to represent any string with parameters n, sigma, and delta (Kociumaka, Navarro, and Prezza;IEEE Trans. Inf. Theory 2023). The other end of the hierarchy is occupied by indexes supporting the suffix array queries. The currently smallest one takes O(r log n/r) space, where r >= delta is the number of runs in the Burrows-Wheeler Transform of the text (Gagie, Navarro, and Prezza;J. ACM 2020). We present a new compressed index, referred to as delta-SA, that supports the powerful SA functionality and needs only O(delta log n log sigma/delta log n) space. This collapses the hierarchy of compressed data structures into a single point: The space required t

关键词： data compression text indexing compressed indexing suffix array

来源：评论

学校读者我要写书评

暂无评论

Inexact Local Alignment Search over suffix arrays

Inexact Local Alignment Search over Suffix Arrays

引用

IEEE International Conference on Bioinformatics and Biomedicine (BIBMW 2009)

作者： Ghodsi, Mohammadreza Pop, Mihai Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Ctr Bioinformat & Computat Biol College Pk MD 20742 USA

ISBN: (纸本)9780769538853

We describe an algorithm for finding approximate seeds for DNA homology searches. In contrast to previous algorithms that use exact or spaced seeds, our approximate seeds may contain insertions and deletions. We present a generalized heuristic for finding such seeds efficiently and prove that the heuristic does not affect sensitivity. We show how to adapt this algorithm to work over the memory efficient suffix array with provably minimal overhead in running time. We demonstrate the effectiveness of our algorithm on two tasks: whole genome alignment of bacteria and alignment of the DNA sequences of 177 genes that are orthologous in human and mouse. We show our algorithm achieves better sensitivity and uses less memory than other commonly used local alignment tools.

关键词： local alignment inexact seeds suffix array

来源：评论

学校读者我要写书评

暂无评论

PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial suffix arrays

PSAEC: An Improved Algorithm for Short Read Error Correction...

引用

Joint 5th International Frontiers in Algorithmics Workshop (FAW) / 7th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Zhao, Zhiheng Yin, Jianping Zhan, Yubin Xiong, Wei Li, Yong Liu, Fayao Natl Univ Def Technol Sch Comp Changsha 410073 Hunan Peoples R China

ISBN: (纸本)9783642212048

Sequencing errors in high-throughput sequencing data constitute one of the major problems in analyzing such data. Error correction can reduce the error rate. However, it is a computation and data intensive process for large-scale data. This poses challenges for more efficient and scalable algorithms. In this paper, we propose PSAEC, an improved algorithm for short read error correction using partial suffix arrays in high-throughput sequencing data. Our algorithm optimizes the HiTEC program by replacing full suffix arrays with partial suffix arrays to index reads which is more time and space efficient. Moreover, PSAEC is a scalable parallel algorithm that can works well on multi-core computers using Pthread. Experiments show that our algorithm delivers good, scalable performance.

关键词： High-throughput sequencing Error correction suffix array Parallel

来源：评论

学校读者我要写书评

暂无评论

Safeness: suffix arrays Driven Materialized View Selection Framework for Large-Scale Workloads 1

引用

24th International Conference on Big Data Analytics and Knowledge Discovery (DaWaK)

作者： Kechar, Mohamed Bellatreche, Ladjel Univ Oran1 Ahmed Ben Bella Ecole Super Informat LITIO Sidi Bel Abbes Algeria LIAS ISAE ENSMA Poitiers France

ISBN: (数字)9783031126703

ISBN: (纸本)9783031126703;9783031126697

Materialized views (MVs) are an elegant redundant optimization technique for analytical workloads. Numerous frameworks and algorithms for selecting MVs have been propounded, and some are deployed in commercial DBMSs. The central role of MVs in optimizing workloads has recently prodded researchers to revisit the problems associated with them (selection, maintenance, adaptation) by proposing AI techniques to tackle those issues. When deeply analyzing both traditional and AI-driven solutions for the MV Selection Problem (VSP), we identify two main limitations: (1) the workloads used in experiments comprise dozens of queries, which is at odds with modern analytical projects involving large-scale workloads, and (2) Query Join Ordering (QJO) is not integrated into the VSP solving process. In this paper, we propose a framework named Safeness that tackles the VSP for large-scale workloads with the incorporation of QJO, thanks to suffix arrays initially introduced for string processing, enabling efficient algorithms for data compression, repeat finding, etc. Firstly, we show the flexibility of suffix arrays in coding analytical queries, capturing shareable subexpressions, and incorporating QJO. Secondly, an enumeration process of different MV candidates is specified. Thirdly, a cost-driven algorithm for selecting MVs under a storage budget is put forward. Finally, experiments are conducted to evaluate the effectiveness and scalability of our proposal.

关键词： Materialized view suffix array OLAP Join order

来源：评论

学校读者我要写书评

暂无评论

A suffix arrays based approach to semantic search in P2P systems

A suffix arrays based approach to semantic search in P2P sys...

引用

Conference on Next-Generation Communication and Sensor Networks 2007

作者： Shi, Qingwei Zhao, Zheng Bao, Hu Tianjin Univ Sch Comp Sci & Technol Tianjin 300072 Peoples R China Liaoning Tech Univ Sch Comp Software Huludao 125105 Peoples R China Nav Aeronaut Engn Inst Dept Elect Engn Yantai 264001 Peoples R China

ISBN: (纸本)9780819469335

Building a semantic search system on top of peer-to-peer (P2P) networks is becoming an attractive and promising alternative scheme for the reason of scalability, Data freshness and search cost. In this paper, we present a suffix arrays based algorithm for Semantic Search (SASS) in P2P systems, which generates a distributed Semantic Overlay Network (SONs) construction for full-text search in P2P networks. For each node through the P2P network, SASS distributes document indices based on a set of suffix arrays, by which clusters are created depending on words or phrases shared between documents, therefore, the search cost for a given query is decreased by only scanning semantically related documents. In contrast to recently announced SONs scheme designed by using metadata or predefined-class, SASS is an unsupervised approach for decentralized generation of SONs. SASS is also an incremental, linear time algorithm, which efficiently handle the problem of nodes update in P2P networks. Our simulation results demonstrate that SASS yields high search efficiency in dynamic environments.

关键词： semantic overlay networks (SONs) P2P networks suffix array distributed information retrieval

来源：评论

学校读者我要写书评

暂无评论

Dynamic Generalized suffix arrays

Dynamic Generalized Suffix Arrays

引用

International Conference on Information Technology and Management Innovation (ICITMI2012)

作者： Lu, Songfeng Zhao, Hua Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

ISBN: (纸本)9783037855744

Document retrieval is the basic task of search engines, and seize amount of attention by the pattern matching community. In this paper, we focused on the dynamic version of this problem, in which the text insertion and deletion is allowable. By using the generalized suffix array and other data structure, we proposed a new index structure. Our scheme achieved better time complexity than the existing ones, and a bit more space overhead is needed as return.

关键词： Algorithms Document Retrieval suffix array Generalized suffix array

来源：评论

学校读者我要写书评

暂无评论

Reducing squares in suffix arrays 18

Reducing squares in suffix arrays

引用

18th Prague Stringology Conference, PSC 2014

作者： Leupold, Peter Institut Für Informatik Universität Leipzig Leipzig Germany

ISBN: (纸本)9788001055472

In contrast to other mutations, duplication leaves an easily detectable trace: a repetition. Therefore it is a convenient starting point for computing a phylogenetic network. Basically, all squares must be detected to compute all possible direct predecessors. To find all the possible, not necessarily direct predecessors, this process must be iterated for all the resulting strings. We show how to reuse the work for one string in this process for the detection of squares in all the strings that are derived from it. For the detection of squares we propose suffix arrays as data structure and show how they can be updated after the reduction of a square. © Czech Technical University in Prague, Czech Republic.

关键词： Duplication suffix array

来源：评论

学校读者我要写书评

暂无评论

suffix arrayS WITH A TWIST

引用

COMPUTING AND INFORMATICS 2019年第3期38卷 555-574页

作者： Kowalski, Tomasz M. Grabowski, Szymon Fredriksson, Kimmo Lodz Univ Technol Inst Appl Comp Sci Al Politech 11 PL-90924 Lodz Poland Univ Eastern Finland Sch Comp POB 1627 FI-70211 Kuopio Finland

The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that i) the way how we search for the right interval boundary impacts significantly the overall search speed, ii) a B-tree data layout easily wins over the standard one, iii) the well-known idea of a lookup table for the prefixes of the suffixes can be refined with using compression, iv) caching prefixes of the suffixes in a helper array can pose another practical space-time tradeoff.

关键词： suffix array data structures text indexes hashing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：