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

31st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Lewenstein, Moshe Nekrich, Yakov Vitter, Jeffrey Scott Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Univ Kansas Dept Elect Engn & Comp Sci Lawrence KS 66045 USA

ISBN: (纸本)9783939897651

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses O(n log(epsilon)n) bits for any epsilon > 0 and reports all occ occurrences of a wildcard string in O(m + sigma(g).mu(n) + occ) time, where mu(n) = o(log log log n), sigma is the alphabet size, m is the number of alphabet symbols and g is the number of wildcard symbols in the query string. We also present an O(n)-bit index with O((m + sigma(g) + occ) log(epsilon)n) query time and an O(n(log log n)(2))-bit index with O((m +sigma(g) + occ) log log n) query time. These are the first non-trivial data structures for this problem that need o(n log n) bits of space.

关键词： compressed data structures compressed indexes pattern matching

来源：评论

学校读者我要写书评

暂无评论

Compressing Huffman Models on Large Alphabets

Compressing Huffman Models on Large Alphabets

引用

data Compression Conference (DCC)

作者： Navarro, Gonzalo Ordonez, Alberto Univ Chile Dept Comp Sci Santiago Chile Univ A Coruna Database Lab La Coruna Spain

ISBN: (纸本)9781467360371

A naive storage of a Huffman model on a text of length n over an alphabet of size s requires O(sigma log n) bits. This can be reduced to sigma log sigma + O(sigma) bits using canonical codes. This overhead over the entropy can be significant when sigma is comparable to n, and it also dictates the amount of main memory required to compress or decompress. We design an encoding scheme that requires sigma log log n + O(sigma + log(2) n) bits in the worst case, and typically less, while supporting encoding and decoding of symbols in O(log log n) time. We show that our technique reduces the storage size of the model of state-of-the-art techniques to around 15% in various real-life sequences over large alphabets, while still offering reasonable compression/decompression times.

关键词： Huffman compression compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Practical compressed Suffix Trees

引用

ALGORITHMS 2013年第2期6卷 319-351页

作者： Abeliuk, Andres Canovas, Rodrigo Navarro, Gonzalo Univ Chile Dept Comp Sci Santiago 8320000 Chile Univ Melbourne Dept Comp & Informat Syst NICTA Victoria Res Lab Melbourne Vic 3010 Australia

The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of range min-max trees yields novel representations achieving practical space/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.

关键词： suffix trees compressed data structures repetitive sequence collections bioinformatics

来源：评论

学校读者我要写书评

暂无评论

LRM-Trees: compressed indices, adaptive sorting, and compressed permutations

引用

THEORETICAL COMPUTER SCIENCE 2012年 459卷 26-41页

作者： Barbay, Jeremy Fischer, Johannes Navarro, Gonzalo Univ Chile Dept Comp Sci Santiago Chile Univ Karlsruhe Dept Comp Sci Karlsruhe Germany

LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks. They have been used to encode ordinal trees and to index integer arrays in order to support range minimum queries on them. We describe how they yield many other convenient results in a variety of areas: compressed indices for range minimum queries on partially sorted arrays, a new adaptive sorting algorithm, and a compressed data structure for permutations supporting direct and inverse application in time inversely proportional to the compressibility of the permutation. (C) 2012 Elsevier B.V. All rights reserved.

关键词： compressed data structures Range minimum queries Adaptive sorting algorithms data structures for permutations

来源：评论

学校读者我要写书评

暂无评论

Stronger Lempel-Ziv Based compressed Text Indexing

引用

ALGORITHMICA 2012年第1-2期62卷 54-101页

作者： Arroyuelo, Diego Navarro, Gonzalo Sadakane, Kunihiko Yahoo Res Latin Amer Santiago Chile Univ Chile Dept Comp Sci Santiago Chile Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

Given a text T[1..u] over an alphabet of size sigma, the full-text search problem consists in finding the occ occurrences of a given pattern P[1..m] in T. In indexed text searching we build an index on T to improve the search time, yet increasing the space requirement. The current trend in indexed text searching is that of compressed full-text self-indices, which replace the text with a more space-efficient representation of it, at the same time providing indexed access to the text. Thus, we can provide efficient access within compressed space. The Lempel-Ziv index (LZ-index) of Navarro is a compressed full-text self-index able to represent T using 4uH (k) (T)+o(ulog sigma) bits of space, where H (k) (T) denotes the k-th order empirical entropy of T, for any k=o(log (sigma) u). This space is about four times the compressed text size. The index can locate all the occ occurrences of a pattern P in T in O(m (3)log sigma+(m+occ)log u) worst-case time. Although this index has proven very competitive in practice, the O(m (3)log sigma) term can be excessive for long patterns. Also, the factor 4 in its space complexity makes it larger than other state-of-the-art alternatives. In this paper we present stronger Lempel-Ziv based indices (LZ-indices), improving the overall performance of the original LZ-index. We achieve indices requiring (2+epsilon)uH (k) (T)+o(ulog sigma) bits of space, for any constant epsilon > 0, which makes them the smallest existing LZ-indices. We simultaneously improve the search time to O(m (2)+(m+occ)log u), which makes our indices very competitive with state-of-the-art alternatives. Our indices support displaying any text substring of length a"" in optimal O(a""/log (sigma) u) time. In addition, we show how the space can be squeezed to (1+epsilon)uH (k) (T)+o(ulog sigma) to obtain a structure with O(m (2)) average search time for ma parts per thousand yen2log (sigma) u. Alternatively, the search time of LZ-indices can be improved to O((m+occ)log u) w

关键词： Text compression compressed data structures compressed full-text indices Lempel-Ziv compression

来源：评论

学校读者我要写书评

暂无评论

compressed Representation of Web and Social Networks via Dense Subgraphs

Compressed Representation of Web and Social Networks via Den...

引用

19th International Symposium on String Processing and Information Retrieval (SPIRE) / 8th Latin American Web Congress (LA-WEB)

作者： Hernandez, Cecilia Navarro, Gonzalo Univ Concepcion Dept Comp Sci Concepcion Chile Univ Chile Dept Comp Sci Santiago Chile

ISBN: (纸本)9783642341083;9783642341090

Mining and analyzing large web and social networks are challenging tasks in terms of storage and information access. In order to address this problem, several works have proposed compressing large graphs allowing neighbor access over their compressed representations. In this paper, we propose a novel compressed structure aiming to reduce storage and support efficient navigation over web and social graph compressed representations. Our approach uses clustering and mining for finding dense subgraphs and represents them using compact data structures. We perform experiments using a wide range of web and social networks and compare our results with the best known techniques. Our results show that we improve the state of the art space/time tradeoffs for supporting neighbor queries. Our compressed structure also enables mining queries based on dense subgraphs, such as cliques and bicliques.

关键词： Web graphs Social networks compressed data structures

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT PATH KERNELS FOR REACTION FUNCTION PREDICTION

EFFICIENT PATH KERNELS FOR REACTION FUNCTION PREDICTION

引用

International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS)

作者： Heinonen, Markus Valimaki, Niko Makinen, Veli Rousu, Juho Univ Helsinki Dept Comp Sci SF-00510 Helsinki Finland

ISBN: (纸本)9789898425904

Kernels for structured data are rapidly becoming an essential part of the machine learning toolbox. Graph kernels provide similarity measures for complex relational objects, such as molecules and enzymes. Graph kernels based on walks are popular due their fast computation but their predictive performance is often not satisfactory, while kernels based on subgraphs suffer from high computational cost and are limited to small substructures. Kernels based on paths offer a promising middle ground between these two extremes. However, the computation of path kernels has so far been assumed computationally too challenging. In this paper we introduce an effective method for computing path based kernels;we employ a Burrows-Wheeler transform based compressed path index for fast and space-efficient enumeration of paths. Unlike many kernel algorithms the index representation retains fast access to individual features. In our experiments with chemical reaction graphs, path based kernels surpass state-of-the-art graph kernels in prediction accuracy.

关键词： Graph kernels compressed data structures XBW transform Reaction graph Hierarchical classification

来源：评论

学校读者我要写书评

暂无评论

Parallel implementation of the finite element method using compressed data structures

引用

COMPUTATIONAL MECHANICS 2007年第1期41卷 31-48页

作者： Ribeiro, F. L. B. Ferreira, I. A. Univ Fed Rio de Janeiro COPPE Programa Engn Civil BR-21945970 Rio De Janeiro Brazil

This paper presents a parallel implementation of the finite element method designed for coarse-grain distributed memory architectures. The MPI standard is used for message passing and tests are run on a PC cluster and on an SGI Altix 350. compressed data structures are employed to store the coefficient matrix and obtain iterative solutions, based on Krylov methods, in a subdomain-by-subdomain approach. Two mesh partitioning schemes are compared: non-overlapping and overlapping. The pros and cons of these partitioning methods are discussed. Numerical examples of symmetric and non-symmetric problems in two and three dimensions are presented.

关键词： parallel computing message passing interface compressed data structures finite element method

来源：评论

学校读者我要写书评

暂无评论

Word-Based Self-Indexes for Natural Language Text

引用

ACM TRANSACTIONS ON INFORMATION SYSTEMS 2012年第1期30卷 1-1页

作者： Farina, Antonio Brisaboa, Nieves R. Navarro, Gonzalo Claude, Francisco Places, Angeles S. Rodriguez, Eduardo Univ A Coruna Fac Informat Dept Comp Sci La Coruna 15071 Spain Univ Chile Dept Comp Sci Santiago 2120 Chile Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

The inverted index supports efficient full-text searches on natural language text collections. It requires some extra space over the compressed text that can be traded for search speed. It is usually fast for single-word searches, yet phrase searches require more expensive intersections. In this article we introduce a different kind of index. It replaces the text using essentially the same space required by the compressed text alone (compression ratio around 35%). Within this space it supports not only decompression of arbitrary passages, but efficient word and phrase searches. Searches are orders of magnitude faster than those over inverted indexes when looking for phrases, and still faster on single-word searches when little space is available. Our new indexes are particularly fast at counting the occurrences of words or phrases. This is useful for computing relevance of words or phrases. We adapt self-indexes that succeeded in indexing arbitrary strings within compressed space to deal with large alphabets. Natural language texts are then regarded as sequences of words, not characters, to achieve word-based self-indexes. We design an architecture that separates the searchable sequence from its presentation aspects. This permits applying case folding, stemming, removing stopwords, etc. as is usual on inverted indexes.

关键词： Algorithms Performance Self-indexes compressed data structures inverted indexes

来源：评论

学校读者我要写书评

暂无评论

Space-efficient construction of Lempel-Ziv compressed text indexes

引用

INFORMATION AND COMPUTATION 2011年第7期209卷 1070-1102页

作者： Arroyuelo, Diego Navarro, Gonzalo Univ Chile Dept Comp Sci Santiago Chile Yahoo Res Latin Amer Santiago Chile

A compressed full-text self-index is a data structure that replaces a text and in addition gives indexed access to it, while taking space proportional to the compressed text size. This is very important nowadays, since one can accommodate the index of very large texts entirely in main memory, avoiding the slower access to secondary storage. In particular, the LZ-index [G. Navarro, Indexing text using the Ziv-Lempel trie, Journal of Discrete Algorithms (JDA) 2 (1) (2004) 87-114] stands out for its good performance at extracting text passages and locating pattern occurrences. Given a text T[1..u] over an alphabet of size a. the Li-index requires 4 vertical bar LZ vertical bar(1 + 0(1)) bits of space, where vertical bar LZ vertical bar is the size of the LZ78-compression of T. This can be bounded by vertical bar LZ vertical bar = uH(k)(T)+o(u log sigma), where H-k(T) is the k-th order empirical entropy of T, for any k = o(log sigma u). The LZ-index is built in O(u loga) time, yet requiring 0(u log u) bits of main memory in the worst case. In practice, the LZ-index occupies 1.0-1.5 times the text size (and replaces the text), but its construction requires around 5 times the text size. This limits its applicability to medium-sized texts. In this paper we present a space-efficient algorithm to construct the 12-index in O(u(log sigma + log log u)) time and requiring 4 vertical bar LZ vertical bar(1 + o(1)) bits of main memory, that is, asymptotically the same space of the final index. We also adapt our algorithm to construct more recent reduced versions of the 12-index, which occupy from 1 to 3 times vertical bar LZ vertical bar(1 + 0(1)) bits, and show that these can also be built using asymptotically the same space of the final index. Finally, we study an alternative model in which we are given only a limited amount of main memory to carry out the indexing process (less than that required by the final index), and must use the disk for the rest. We show how to build all t

关键词： Full-text indexing compressed data structures Text databases Lempel-Ziv compression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：