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

Algorithms to compute the Burrows-Wheeler Similarity Distribution

THEORETICAL COMPUTER SCIENCE 2019年 782卷 145-156页

作者： Louza, Felipe A. Telles, Guilherme P. Gog, Simon Zhao, Liang Univ Sao Paulo Dept Comp & Math Ribeirao Preto Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil eBay Inc San Jose CA USA

The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler Similarity Distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Burrows-Wheeler transform String similarity String collections compressed data structures Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Lempel-Ziv compressed structures for document retrieval

引用

INFORMATION AND COMPUTATION 2019年 265卷 1-25页

作者： Ferrada, Hector Navarro, Gonzalo Univ Austral Chile Fac Ciencias Ingn Informat Inst Valdivia Chile Univ Chile Dept Comp Sci CeBiB Ctr Biotechnol & Bioengn Santiago Chile

Document retrieval structures index a collection of string documents, to retrieve those that are relevant to query strings p: document listing retrieves all documents where p appears;top k retrieval retrieves the k most relevant of those. Classical structures use too much space in practice. Most current research uses compressed suffix arrays, but fast indices still use 17-21 bpc (bits per character), whereas small ones take milliseconds per returned answer. We present the first document retrieval structures based on Lempel-Ziv compression, precisely LZ78. Our structures use 7-10 bpc and dominate a large part of the space/time tradeoffs. They also enable more efficient partial or approximate answers: our document listing outputs the first 75%-80% of the answers at a rate of one per microsecond;for top-k retrieval we return a result of 90% quality at the same rate and using just 4-6 bpc. This outperforms current indices by a wide margin. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Document retrieval Document listing Top-k queries String databases compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Zuckerli: A New compressed Representation for Graphs

引用

IEEE ACCESS 2020年 8卷 219233-219243页

作者： Versari, Luca Comsa, Iulia-Maria Conte, Alessio Grossi, Roberto Univ Pisa Dipartimento Informat I-56127 Pisa Italy Google Res CH-8002 Zurich Switzerland

Zuckerli is a scalable compression system meant for large real-world graphs. Graphs are notoriously challenging structures to store efficiently due to their linked nature, which makes it hard to separate them into smaller, compact components. Therefore, effective compression is crucial when dealing with large graphs, which can have billions of nodes and edges. Furthermore, a good compression system should give the user fast and reasonably flexible access to parts of the compressed data without requiring full decompression, which may be unfeasible on their system. Compared to WebGraph, the de-facto standard in compressing real-world graphs, Zuckerli improves multiple aspects by using advanced compression techniques and novel heuristic graph algorithms. Zuckerli can produce both a compressed representation for storage and one which allows fast direct access to the adjacency lists of the compressed graph without decompressing the entire graph. We validate its effectiveness on real-world graphs with up to a billion nodes and 90 billion edges, conducting an extensive experimental evaluation of both compression density and decompression performance. We show that Zuckerli-compressed graphs are 10% to 29% smaller, and more than 20% in most cases, with a resource usage for decompression comparable to that of WebGraph.

关键词： Decoding Channel coding Standards Huffman coding Time-frequency analysis Two dimensional displays Transform coding Graphs compression compressed data structures

来源：评论

学校读者我要写书评

暂无评论

A Compact Rank/Select data Structure for the Streaming Model 38

A Compact Rank/Select Data Structure for the Streaming Model

引用

38th International Conference of the Chilean-Computer-Science-Society (SCCC)

作者： Gonzalez, Natalia Arroyuelo, Diego Univ Tecn Federico Santa Maria Dept Informat Santiago Chile Univ Tecn Federico Santa Maria Dept Informat Millennium Inst Fdn Res Data IMFD Santiago Chile

ISBN: (纸本)9781728156132

For a sorted set S from a universe [1..u] received under the streaming model (i.e., elements are received one at a time, in sorted order), such that at a given time it contains n elements {x(1),..., x(n)}, and whose characteristic bit vector is C-S = 0(sigma 1)11 center dot center dot center dot 10(sigma 2)11 center dot center dot center dot 1 center dot center dot center dot 0(sigma g)11 center dot center dot center dot 1 (i.e., the set elements are actually arranged in g <= n intervals of size >= 1), we propose a compact data structure that answers operations select and rank in Theta(lg(g/lg g)) worst-case time, and append in O(1) amortized time, using 2g lg u - n/g + g lg n/g + O(g lg lg g) bits of space. The structure is suitable in cases where g <= n/2.

关键词： Succinct and compact data structures compressed data structures append-only rank/select data structures

来源：评论

学校读者我要写书评

暂无评论

Rank and select: Another lesson learned

引用

INFORMATION SYSTEMS 2018年 73卷 25-34页

作者： Grabowski, Szymon Raniszewski, Marcin Lodz Univ Technol Inst Appl Comp Sci Al Politech 11 PL-90924 Lodz Poland

Rank and select queries on bitmaps are essential building bricks of many compressed data structures, including text indexes, membership and range supporting spatial data structures, compressed graphs, and more. Theoretically considered yet in 1980s, these primitives have also been a subject of vivid research concerning their practical incarnations in the last decade. We present a few novel rank/select variants, focusing mostly on speed, obtaining competitive space-time results in the compressed setting. Our findings can be summarized as follows: (i) no single rank/select solution works best on any kind of data (ours are optimized for bit arrays obtained from wavelet trees for real text datasets, but also work well for LOUDS-encoded XML tree layouts), (ii) it pays to efficiently handle blocks consisting of all 0 or all 1 bits, (iii) compressed select does not have to be significantly slower than compressed rank at a comparable memory use. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Binary sequences Rank Select compressed data structures

来源：评论

学校读者我要写书评

暂无评论

At the Roots of Dictionary Compression: String Attractors 2018

At the Roots of Dictionary Compression: String Attractors

引用

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

作者： Kempa, Dominik Prezza, Nicola Univ Helsinki Dept Comp Sci Helsinki Finland Tech Univ Denmark DTU Compute Lyngby Denmark Univ Pisa Dept Comp Sci Pisa Italy

ISBN: (纸本)9781450355599

A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this fact, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text's size by exploiting its repetitiveness. Lempel-Ziv 77 is one of the most successful and well-known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, macro schemes, collage systems, and the compact directed acyclic word graph. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all distinct text's substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives the approximation ratios of dictionary compressors with respect to the smallest string attractor and allows us to uncover new asymptotic relations between the output sizes of different dictionary compressors. We then show that the k-attractor problem deciding whether a text has a size-t set of positions capturing all substrings of length at most k is NP-complete for k >= 3. This, in particular, includes the full string attractor problem. We provide several approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower and upper bounds for the random access problem on string attractors. The upper bound is proved by showing a data structure supporting queries in optimal time. Our data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, it matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access pr

关键词： Dictionary compression compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Top-k Term-Proximity in Succinct Space

引用

ALGORITHMICA 2017年第2期78卷 379-393页

作者： Munro, J. Ian Navarro, Gonzalo Nielsen, Jesper Sindahl Shah, Rahul Thankachan, Sharma V. Univ Waterloo Cheriton Sch CS Waterloo ON Canada Univ Chile Dept CS Santiago Chile Aarhus Univ MADALGO Aarhus Denmark Louisiana State Univ Sch EECS Baton Rouge LA 70803 USA Georgia Inst Technol Sch CSE Atlanta GA 30332 USA

Let be a collection of D string documents of n characters in total, that are drawn from an alphabet set . The top-k document retrieval problem is to preprocess into a data structure that, given a query , can return the k documents of most relevant to the pattern P. The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in . For example, it can be the term frequency (i.e., the number of occurrences of P in ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in ), or a pattern-independent importance score of such as PageRank. Linear space and optimal query time solutions already exist for the general top-k document retrieval problem. compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o(n) bits on top of any compressed suffix array of and solves queries in time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection.

关键词： Document indexing Top-k document retrieval Ranked document retrieval Succinct data structures compressed data structures Compact data structures Proximity search

来源：评论

学校读者我要写书评

暂无评论

Wheeler graphs: A framework for BWT-based data structures

引用

THEORETICAL COMPUTER SCIENCE 2017年 698卷 67-78页

作者： Gagie, Travis Manzini, Giovanni Siren, Jouni Diego Portales Univ Santiago Chile CEBIB Santiago Chile Univ Piemonte Orientale Alessandria Italy IIT CNR Pisa Italy Wellcome Trust Sanger Inst Cambridge England

The famous Burrows-Wheeler Transform (BWT) was originally defined for a single string but variations have been developed for sets of strings, labeled trees, de Bruijn graphs, etc. In this paper we propose a framework that includes many of these variations and that we hope will simplify the search for more. We first define Wheeler graphs and show they have a property we call path coherence. We show that if the state diagram of a finite-state automaton is a Wheeler graph then, by its path coherence, we can order the nodes such that, for any string, the nodes reachable from the initial state or states by processing that string are consecutive. This means that even if the automaton is non-deterministic, we can still store it compactly and process strings with it quickly. We then rederive several variations of the BWT by designing straightforward finite-state automata for the relevant problems and showing that their state diagrams are Wheeler graphs. (C) 2017 The Authors. Published by Elsevier B.V.

关键词： compressed data structures Burrows-Wheeler transform Pattern matching

来源：评论

学校读者我要写书评

暂无评论

A succinct data structure for self-indexing ternary relations

引用

JOURNAL OF DISCRETE ALGORITHMS 2017年 43卷 38-53页

作者： Alvarez-Garcia, Sandra de Bernardo, Guillermo Brisaboa, Nieves R. Navarro, Gonzalo Databases Lab Campus Elvina La Coruna Spain Enxenio SL Banos De Arteixo A Coruna Spain Univ A Coruna Campus Elvina La Coruna Spain Univ Chile DCC Beauchef 851 Santiago Chile

The representation of binary relations has been intensively studied and many different theoretical and practical representations have been proposed to answer the usual queries in multiple domains. However, ternary relations have not received as much attention, even though many real-world applications require the processing of ternary relations. In this paper we present a new compressed and self-indexed data structure that we call Interleaved K-2-tree (IK2-tree), designed to compactly represent and efficiently query general ternary relations. The IK2-tree is an evolution of an existing data structure, the K-2-tree [6], initially designed to represent Web graphs and later applied to other domains. The IK2-tree is able to extend the K-2-tree to represent a ternary relation, based on the idea of decomposing it into a collection of binary relations but providing indexing capabilities in all the three dimensions. We present different ways to use IK2-tree to model different types of ternary relations using as reference two typical domains: RDF and Temporal Graphs. We also experimentally evaluate our representations comparing them in space usage and performance with other solutions of the state of the art. (C) 2016 Elsevier B.V. All rights reserved.

关键词： compressed data structures Ternary relations RDF Temporal graphs K-2-tree

来源：评论

学校读者我要写书评

暂无评论

compressed Spaced Suffix Arrays

引用

MATHEMATICS IN COMPUTER SCIENCE 2017年第2期11卷 151-157页

作者： Gagie, Travis Manzini, Giovanni Valenzuela, Daniel Diego Portales Univ Santiago Chile CEBIB Santiago Chile Univ Piemonte Orientale Alessandiia Italy CNR IIT Pisa Italy Univ Helsinki Helsinki Finland

As a first step in designing relatively-compressed data structures-i.e., such that storing an instance for one dataset helps us store instances for similar datasets-we consider how to compress spaced suffix arrays relative to normal suffix arrays and still support fast access to them. This problem is of practical interest when performing similarity search with spaced seeds because using several seeds in parallel significantly improves their performance, but with existing approaches we keep a separate linear-space hash table or spaced suffix array for each seed. We first prove a theoretical upper bound on the space needed to store a spaced suffix array when we already have the suffix array. We then present experiments indicating that our approach works even better in practice.

关键词： compressed data structures Similarity search Spaced seeds Spaced suffix arrays Relative compression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：