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

Set operations over compressed binary relations

INFORMATION SYSTEMS 2019年第Feb.期80卷 76-90页

作者： Quijada-Fuentes, Carlos Penabad, Miguel R. Ladra, Susana Gutierrez, Gilberto Univ Bio Bio Fac Ciencias Empresariales Chillan Chile Univ A Coruna Fac Informat La Coruna Spain

Binary relations are commonly used to represent relationships between real-world objects. Classical representations for binary relations can be very space-consuming when the set of elements is large. In these cases, compressed representations, such as the k(2)-tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover, k(2)-trees can successfully represent both sparse and dense binary relations, using different variants of the technique. In this paper, we propose and evaluate algorithms to efficiently perform set operations over binary relations represented using k(2)-trees. More specifically, we present algorithms for computing the union, intersection, difference, symmetric difference, and complement of binary relations. Thus, this work extends the functionality of the different variants of the k(2)-tree representation for binary relations. Our algorithms are computed directly over the compressed representation, without requiring previous decompression, and generate the result in compressed form. The experimental evaluation shows that they are efficient in terms of space and time, compared with different baselines where the binary relations are represented in plain form or require a previous decompression to perform the set operation. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： compact data structures Compressed binary relations Set operations k(2)-trees

来源：评论

学校读者我要写书评

暂无评论

compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number

引用

THEORETICAL COMPUTER SCIENCE 2023年 941卷 156-166页

作者： Chakraborty, Sankardeep Jo, Seungbum Univ Tokyo Tokyo Japan Chungnam Natl Univ Daejeon South Korea

In this paper we initiate the study of designing parameterized compact data structures for an interval graph G with n vertices. First, we show that when the maximum degree of G is bounded by A, we show that the space requirement of our data structure is at least (16 n log2 A - O(n))-bit, which is one of the main contributions of this work. Next, by straightforward modifications of the result of Acan et al. (2021) [5], we obtain an (n log2 A + O(n))-bit data structure supporting the standard navigational queries i.e., degree, adjacency, and neighborhood optimally. Hence, we provide a compact representation of interval graphs with bounded degree for the first time in literature. Note that this upper bound result takes less space than their (n log2 n + O (n)) -bit upper bound when A = O (nE), for any 0 < c < 1. Next, we consider the interval graphs with bounded chromatic number x, and design a ((x - 1)n + o(xn))-bit data structure with efficient query times. Unlike the previous upper bound, this data structure is completely new and doesn't follow from the result of Acan et al. (2021) [5]. Moreover, this takes less space than their data structure when x = o(logn). Finally, we provide parameterized compact data structures for circular-arc graphs as well with bounded degree or bounded chromatic number condition. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Interval graphs Circular -arc graphs compact data structures Navigational queries

来源：评论

学校读者我要写书评

暂无评论

Space/time-efficient RDF stores based on circular suffix sorting

引用

JOURNAL OF SUPERCOMPUTING 2023年第5期79卷 5643-5683页

作者： Brisaboa, Nieves R. Cerdeira-Pena, Ana de Bernardo, Guillermo Farina, Antonio Navarro, Gonzalo Univ A Coruna Dept Comp Sci & Informat Technol La Coruna Spain CITIC Res Ctr La Coruna Spain Univ Chile Dept Comp Sci IMFD Santiago Chile

The resource description framework (RDF) has gained popularity as a format for the standardized publication and exchange of information in the Web of data. In this paper, we introduce RDFCSA, a compressed representation of RDF datasets that in addition supports efficient querying. RDFCSA regards the triples of the RDF store as short circular strings and applies suffix sorting on those strings, so that triple-pattern queries reduce to prefix searching on the string set. The RDF store is then represented compactly using a compressed suffix array (CSA), a proved technology in text indexing that efficiently supports prefix searches. Our experiments show that RDFCSA is competitive with state-of-the-art alternatives. It compresses the raw data to 60% of its size, close to the most compact alternatives. While most alternatives perform better in some kinds of triple-patterns than in others, RDFCSA features fast and consistent query times, a few microseconds per result in all cases. This enables efficiently supporting join queries by using either merge- or chaining-join strategies over the triple patterns coupled with some specific optimizations such as variable filling. Our experiments on binary joins show that RDFCSA is faster than the alternatives in most cases.

关键词： compact data structures RDF CSA Web of data

来源：评论

学校读者我要写书评

暂无评论

Faster compressed quadtrees

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年 131卷 86-104页

作者： de Bernardo, Guillermo Gagie, Travis Ladra, Susana Navarro, Gonzalo Seco, Diego Univ A Coruna Database Lab CITIC Coruna Spain Dalhousie Univ Fac Comp Sci Halifax NS Canada IMFD Millennium Inst Fdn Res Data Santiago Chile Univ Chile Dept Comp Sci Santiago Chile

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O (1) bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy -path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice.(c) 2022 Elsevier Inc. All rights reserved.

关键词： compact data structures Quadtrees Heavy-path decomposition Range queries Clustered points

来源：评论

学校读者我要写书评

暂无评论

Linear-time String Indexing and Analysis in Small Space

引用

ACM TRANSACTIONS ON ALGORITHMS 2020年第2期16卷 17-17页

作者： Belazzougui, Djamal Cunial, Fabio Karkkainen, Juha Makinen, Veli Univ Helsinki Dept Comp Sci POB 68Pietari Kalmin Katu 5 FIN-00014 Helsinki Finland Ctr Rech Informat Sci & Tech Algiers Algeria Max Planck Inst Mol Cell Biol & Genet Dresden Germany

The field of succinct data structures has flourished over the past 16 years. Starting from the compressed suffix array by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. For example, one can compare two genomes by building a common index for their concatenation and by detecting common substructures by querying the index. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis: We show that the BWT of a string T is an element of {1, . . . , sigma}(n) can be built in deterministic O(n) time using just O(n log sigma) bits of space, where sigma <= n. Deterministic linear time is achieved by exploiting a new partial rank data structure that supports queries in constant time and that might have independent interest. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of T. Many fundamental string analysis problems, such as maximal repeats, maximal unique matches, and string kernels, can be mapped to such enumeration and can thus be solved in deterministic O(n) time and in O(n log sigma) bits of space from the input string by tailoring the enumeration algorithm to some problem-specific computations. We also show how to build many of the existing indexes based on the BWT, such as the compressed suffix array, the compressed suffix tree, and the bidirectional BWT index, in randomized O(n) time and in O(n log sigma) bits of space. The previously fastest

关键词： compact data structures compressed indexes Burrows-Wheeler transform suffix array suffix tree suffix-link tree compressed suffix array compressed suffix tree bidirectional BWT index partial rank query monotone minimal perfect hash function matching statistics maximal repeat maximal unique match maximal exact match minimal absent word string kernel

来源：评论

学校读者我要写书评

暂无评论

Space-efficient representations of raster time series

引用

INFORMATION SCIENCES 2021年 566卷 300-325页

作者： Silva-Coira, Fernando Parama, Jose R. de Bernardo, Guillermo Seco, Diego Univ A Coruna Fac Informat Ctr Invest CITIC Campus Elvina S-N La Coruna 15071 Spain Univ Concepcion Concepcion Chile IMFD Concepcion Chile

Raster time series, a.k.a. temporal rasters, are collections of rasters covering the same region at consecutive timestamps. These data have been used in many different applications ranging from weather forecast systems to monitoring of forest degradation or soil contamination. Many different sensors are generating this type of data, which makes such analyses possible, but also challenges the technological capacity to store and retrieve the data. In this work, we propose a space-efficient representation of raster time series that is based on compact data structures (CDS). Our method uses a strategy of snapshots and logs to represent the data, in which both components are represented using CDS. We study two variants of this strategy, one with regular sampling and another one based on a heuristic that determines at which timestamps should the snapshots be created to reduce the space redundancy. We perform a comprehensive experimental evaluation using real datasets. The results show that the proposed strategy is competitive in space with alternatives based on pure data compression, while providing much more efficient query times for different types of queries. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Geographic information systems Raster datasets data compression Indexing Query processing compact data structures

来源：评论

学校读者我要写书评

暂无评论

Parallel computation of the Burrows Wheeler Transform in compact space

引用

THEORETICAL COMPUTER SCIENCE 2020年 812卷 123-136页

作者： Fuentes-Sepulveda, Jose Navarro, Gonzalo Nekrich, Yakov Univ Chile Ctr Biotechnol & Bioengn Dept Comp Sci Santiago Chile Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

The Burrows-Wheeler Transform (BWT) has become since its introduction a key tool for representing large text collections in compressed space while supporting indexed searching: on a text of length n over an alphabet of size sigma, it requires O (n lg sigma) bits of space, instead of the O (n lg n) bits required by classical indexes. A challenge for its adoption is to build it within O (n lg sigma) bits as well. There are some sequential algorithms building it within this space, but no such a parallel algorithm. In this paper we present a PRAM CREW algorithm to build the BWT using O (n root lgn) work, O(lg(3)n/lg sigma) depth, and O (n lg sigma) bits. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Burrows-Wheeler Transform Suffix arrays Parallel construction compact data structures

来源：评论

学校读者我要写书评

暂无评论

Compressed data structures for Binary Relations in Practice

引用

IEEE ACCESS 2020年 8卷 25949-25963页

作者： Quijada Fuentes, Carlos Penabad, Miguel R. Ladra, Susana Gutierrez Retamal, Gilberto Univ Bio Bio Fac Ciencias Empresariales Chillan 3800708 Chile Univ A Coruna Fac Informat Ctr Invest CITIC La Coruna 15071 Spain

Binary relations are commonly used in Computer Science for modeling data. In addition to classical representations using matrices or lists, some compressed data structures have recently been proposed to represent binary relations in compact space, such as the k(2)-tree and the Binary Relation Wavelet Tree (BRWT). Knowing their storage needs, supported operations and time performance is key for enabling an appropriate choice of data representation given a domain or application, its data distribution and typical operations that are computed over the data. In this work, we present an empirical comparison among several compressed representations for binary relations. We analyze their space usage and the speed of their operations using different (synthetic and real) data distributions. We include both neighborhood and set operations, also proposing algorithms for set operations for the BRWT, which were not presented before in the literature. We conclude that there is not a clear choice that outperforms the rest, but we give some recommendations of usage of each compact representation depending on the data distribution and types of operations performed over the data. We also include a scalability study of the data representations.

关键词： Binary relations compact data structures compressed binary relations k(2)-trees BRWT set operations neighborhood queries

来源：评论

学校读者我要写书评

暂无评论

Compressed Dynamic Range Majority and Minority data structures

引用

ALGORITHMICA 2020年第7期82卷 2063-2086页

作者： Gagie, Travis He, Meng Navarro, Gonzalo CeBiB Ctr Biotechnol & Bioengn Santiago Chile Dalhousie Univ Fac Comp Sci Halifax NS Canada Millennium Inst Foundat Res Data Santiago Chile Univ Chile Dept Comp Sci Santiago Chile

In the range alpha-majority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ellipsis j], we can efficiently report the symbols that occur more than alpha(j-i+1) times in S[i horizontal ellipsis j], which are called the range alpha-majorities. In this article we describe the first compressed dynamic data structure for range alpha-majority queries. It represents S in compressed space-nHk+o(nlg sigma) bits for any k=o(lg sigma n), where sigma is the alphabet size and Hk <= H0 <= lg sigma is the kth order empirical entropy of S-and answers queries in amortized time. We then show how to modify our data structure to receive some beta >=alpha at query time and report the range beta-majorities in time, without increasing the asymptotic space or update-time bounds. The best previous dynamic solution has the same query and update times as ours, but it occupies O(n) words and cannot take advantage of being given a larger threshold beta at query time. We also design the first dynamic data structure for range alpha-minority-i.e., find a non-alpha-majority that occurs in a range-and obtain space and time bounds similar to those for alpha-majorities. We extend the structure to find Theta(1/alpha)-minorities at the same space and time cost. By giving up updates, we obtain static data structures with query time O((1/alpha)lglgw sigma) for both problems, on a RAM with word size w=omega(lgn) bits, without increasing our space bound. Static alternatives reach time O(1/alpha), but they compress S only to zeroth order entropy (H0) or they only handle small values of alpha, that is, lg(1/alpha)=o(lg sigma).

关键词： Range majority and minority Dynamic data structures compact data structures

来源：评论

学校读者我要写书评

暂无评论

compact Fenwick trees for dynamic ranking and selection

引用

SOFTWARE-PRACTICE & EXPERIENCE 2020年第7期50卷 1184-1202页

作者： Marchini, Stefano Vigna, Sebastiano Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan MI Italy

The Fenwick tree is a classical implicit data structure that stores an array in such a way that modifying an element, accessing an element, computing a prefix sum and performing a predecessor search on prefix sums all take logarithmic time. We introduce a number of variants which improve the classical implementation of the tree: in particular, we can reduce its size when an upper bound on the array element is known, and we can perform much faster predecessor searches. Our aim is to use our variants to implement an efficient dynamic bit vector: our structure is able to perform updates, ranking and selection in logarithmic time, with a space overhead in the order of a few percents, outperforming existing data structures with the same purpose. Along the way, we highlight the pernicious interplay between the arithmetic behind the Fenwick tree and the structure of current CPU caches, suggesting simple solutions that improve performance significantly.

关键词： compact data structures dynamic bit vectors prefix sums

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：