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

compact data structures to Represent and Query data Warehouses into Main Memory

IEEE LATIN AMERICA TRANSACTIONS 2018年第9期16卷 2328-2335页

作者： Vallejos, C. Caniupan, M. Gutierrez, G. Univ Los Lagos Puerto Montt Chile Univ Bio Bio Dept Sistemas Informac Concepcion Chile Univ Bio Bio Dept Ciencias Comp & Tecnol Informac Chillan Chile

In this paper we propose the use of compact data structures to represent and process data Warehouses (DWs) into main memory. compact data structures are data structures that allow compacting the data without losing the capacity of querying the data in their compact form. A DW is a data repository to store historical data for decision support, and consists of dimensions and facts. The dimensions are abstract concepts that groups data with a similar meaning, usually, they are modelled as hierarchies of levels, which contain elements. The facts are quantitative data associated to dimensions. A data cube is a way to retrieve facts at different levels of granularity, which is achieved by navigation on dimensions hierarchies. Since a DW can store terabytes of data, the efficient processing of data cubes is key in OLAP (On-line Analytical Processing). We show that by using a compact representation of DWs we can improve the use of space in main memory, and achieve better performance for query processing. In this paper we extend a previous work to process aggregate queries with aggregate functions MAX, MIN, COUNT and AVG.

关键词： databases data warehousing compact data structures

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of spatial queries over points stored in k²-tree compact data structures

引用

THEORETICAL COMPUTER SCIENCE 2021年 892卷 108-131页

作者： Santolaya, Fernando Caniupan, Monica Gajardo, Luis Romero, Miguel Torres-Aviles, Rodrigo Univ Bio Bio Concepcion Chile

We present efficient algorithms to compute two spatial queries over points stored in compact data structures. The former is the K-Nearest Neighbors Query (KNN) which given a point q gets the K-nearest points to q. The latter query is the K-Closest Pair Query (KCPQ), which obtains the K-pairs of closest neighbors between two set of points R and S on the same spatial plane. There are several efficient implementations of these queries, which work mainly with data stored in secondary memory. However, these implementations do not scale well over large datasets. Our algorithms compute the queries over large datasets of points stored in compact data structures, in main memory. compact data structures are structures that allow efficiently storage data in main memory and query them in their compressed form. We use the k(2)-tree compact structure to represent points of interest. Through experimentation over synthetic and real datasets, we show that by using the k(2)-tree we can work with large datasets in main memory, and that the KNN and KCPQ spatial data queries can be efficiently computed over the compact data structures. We also implement a JAVA library that is available for the academic and industrial community. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Algorithms compact data structures Spatial databases Computational geometry Spatial queries

来源：评论

学校读者我要写书评

暂无评论

Building Efficient and compact data structures for Simplicial Complexes

引用

ALGORITHMICA 2017年第2期79卷 530-567页

作者： Boissonnat, Jean-Daniel Karthik, C. S. Tavenas, Sebastien INRIA Sophia Antipolis Mediterranee Geometr 2004 Route LuciolesBP 93 F-06902 Sophia Antipolis France Weizmann Inst Sci Dept Comp Sci & Appl Math Rehovot Israel Microsoft Res India Bangalore Karnataka India

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

关键词： Simplicial complex compact data structures Automaton NP-hard

来源：评论

学校读者我要写书评

暂无评论

CmpctArch: A Generic Low Power Architecture for compact data structures in Energy Harvesting Devices

CmpctArch: A Generic Low Power Architecture for Compact Data...

引用

IEEE-Computer-Society Annual Symposium on VLSI (ISVLSI)

作者： Singla, Priyanka Sarangi, Smruti R. Indian Inst Technol New Delhi Sch Informat Technol New Delhi India Indian Inst Technol New Delhi Comp Sci & Engn New Delhi India

ISBN: (数字)9781665466059

ISBN: (纸本)9781665466059

Small sub-mW sensor devices that rely on energy harvesting often have limited computation capability to locally process, query, and update data. Such energy harvesting devices (EHDs) need to operate under a strict power constraint and are also extremely cost-sensitive. Based on current costs and estimated near-term trends, we observe that the price of the nonvolatile memory component dominates (in approximate to 20 USD devices). Hence, there is a pressing need to reduce the overall memory footprint in a data-intensive setting. This paper is the first to propose a generic hardware architecture, CmpctArch, for implementing compact data structures (CDSs) on such devices. They reduce the memory footprint by up to 3.5x without significantly increasing the overall energy consumption or time taken (max. additional energy 1.04x and time 1.18x). The hardware implementations are 160-1200x more energy-efficient and 280-620x faster than the corresponding software implementations of CDSs. Our generic template can be used to instantiate a wide variety of data structures commonly used in EHD applications.

关键词： compact data structures Hardware accelerators Memory footprint Resource-constrained System on chip

来源：评论

学校读者我要写书评

暂无评论

data structures for temporal graphs based on compact sequence representations

引用

INFORMATION SYSTEMS 2015年 51卷 1-26页

作者： Caro, Diego Andrea Rodriguez, M. Brisaboa, Nieves R. Univ Concepcion Concepcion Chile Univ A Coruna La Coruna Spain

Temporal graphs represent vertices and binary relations that change along time. In this paper, a temporal graph is conceptualized as the sequences of changes on its edges during its lifetime, also known as temporal adjacency logs. The paper explores the use of compression techniques, and compact and self-indexed data structures, to represent large temporal graphs. More specifically, we present four strategies to represent temporal graphs. The first two strategies, Time-interval Log per Edge (EdgeLog) and the Adjacency Log of Events (EveLog), use compression techniques over the inverted indexes that represent the adjacency logs. Then, we introduce two new strategies to represent temporal graphs using compact and self-indexed data structures. compact Adjacency Sequence (CAS) represents changes on adjacent vertices as a sequence stored in a Wavelet Tree, and the compact Events ordered by Time (CET) represents the edges that change in each time instant using Interleaved Wavelet Tree, a new compact and self-indexed data structure specifically designed in this work that is able to represent a sequence of multidimensional symbols (that is, tuples of symbols encoded together). We experimentally evaluate the four strategies and compare them with previous alternatives in the state-of-the-art showing that the four alternatives can represent large temporal graphs making efficient use of space, while keeping good time performance for a wide range of useful queries. We conclude that the use of compression techniques or the use of compact and self-indexed data structures open the possibility for the design of interesting representations of temporal graphs that fit the heeds of different application domains. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Temporal graphs compact data structures Wavelet tree

来源：评论

学校读者我要写书评

暂无评论

Rescore in a Flash: compact, Cache Efficient Hashing data structures for N-gram Language Models 21

Rescore in a Flash: Compact, Cache Efficient Hashing Data St...

引用

Interspeech Conference

作者： Strimel, Grant P. Rastrow, Ariya Tiwari, Gautam Pierard, Adrien Webb, Jon Amazon Com Seattle WA 98109 USA

ISBN: (纸本)9781713820697

We introduce DashHashLM, an efficient data structure that stores an n-gram language model compactly while making minimal trade-offs on runtime lookup latency. The data structure implements a finite state transducer with a lossless structural compression and outperforms comparable implementations when considering lookup speed in the small-footprint setting. DashHashLM introduces several optimizations to language model compression which are designed to minimize expected memory accesses. We also present variations of DashHashLM appropriate for scenarios with different memory and latency constraints. We detail the algorithm and justify our design choices with comparative experiments on a speech recognition task. Specifically, we show that with roughly a 10% increase in memory size, compared to a highly optimized, compressed baseline n-gram representation, our proposed data structure can achieve up to a 6x query speedup.

关键词： n-gram language models compact data structures LM compression

来源：评论

学校读者我要写书评

暂无评论

Repetitiveness measures based on string morphisms

引用

THEORETICAL COMPUTER SCIENCE 2025年 1043卷

作者： Navarro, Gonzalo Urbina, Cristian Univ Chile Dept Comp Sci Santiago Chile Ctr Biotechnol & Bioengn CeBiB Santiago Chile

We study deterministic Lindenmayer systems, and more generally string morphisms, as mechanisms to capture the repetitiveness of string collections. In particular, we define L-systems, which extend CPD0L-systems with two parameters, d and n, to unambiguously determine a single string w = i(pd(s ))[1 .. n], where p is the morphism of the system, i is a coding, and s is its starting symbol. We define 8(w) as the size of the shortest description of an L-system generating w, and show that 8, which builds on the self-similarities that arise in the sequence, is a relevant measure of repetitiveness. We study the relation between 8 and a better-established measure called S, which builds on sub-string complexity. Our results show that 8 and S are largely orthogonal, in the sense that either root can be larger than the other, depending on the string family. In particular, 8 can be Theta( n) times smaller than S, whereas 8 is upper-bounded by the smallest context-free grammar that generates the string, and thus can be only polylogarithmically larger than S. This suggests that both mechanisms capture different kinds of regularities related to repetitiveness. We then combine the mechanisms of L-systems and of bidirectional macro schemes, the smallest known representation scheme that captures substring copies. We call the combination NU-systems, and show that they can be asymptotically strictly smaller than both mechanisms for the same fixed string family. The size v of the smallest NU-system is a new minimal reachable repetitiveness measure, and it is also shown to be uncomparable with S. This shows that combining morphism substitution with copy-paste mechanisms yields a stronger approach to capture string repetitiveness. We also study algorithmic problems on L-systems and NU-systems, such as the cost of decompression and of accessing substrings of the encoded string without fully decompressing it, and explore various simplifications of L-systems that trade compression effectiven

关键词： Repetitiveness measures Text compression compact data structures Combinatorics on

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm to Count the Relations in a Range of Binary Relations Represented by a k²-Tree

引用

IEEE ACCESS 2021年 9卷 20808-20818页

作者： Candia, Martita Munoz Retamal, Gilberto Gutierrez Torres-Aviles, Rodrigo Univ Bio Bio Dept Ciencias Comp & Tecnol Informac Chillan 3780000 Chile Univ Bio Bio Dept Sistemas Informac Concepcion 4030000 Chile

Two sets A and B, whose elements fulfill a total order on operator <=, can have a binary relation R subset of A x B represented by the k(2)-tree compact data structure, which greatly improves storage space. Currently, Count query is managed by either using Range query or to modify the structure to have aggregate information, implying additional time or space in order to perform the query. This article presents compact Count, which exploits the k(2)-tree properties to reduce the paths to be scanned to count the numbers in a range r, thus ensuring an expected runtime of O(log(k) r log(k) n) and storage of O(log(k) r) with the k(2)-tree parameters n and k. Our algorithm was compared through a series of experiments that consider both synthetic data with different distributions and real data, with a solution based on the Range algorithm. Experimental results show that compact Count is 250 to 1,000 times faster than Range on synthetic and real data, respectively, with a small additional storage cost, as expected by the theoretical analysis.

关键词： data structures Aggregates Web pages Licenses Ink Central Processing Unit Urban areas Algorithm compact data structures counting query

来源：评论

学校读者我要写书评

暂无评论

IBHM: index-based data structures for 2D and 3D hybrid meshes

引用

ENGINEERING WITH COMPUTERS 2017年第4期33卷 727-744页

作者： Lage, Marcos Martha, Luiz Fernando Moitinho de Almeida, J. P. Lopes, Helio Univ Fed Fluminense Niteroi RJ Brazil Pontificia Univ Catolica Rio de Janeiro Rio De Janeiro Brazil Univ Lisbon Inst Super Tecn Lisbon Portugal

We propose new topological data structures for the representation of 2D and 3D hybrid meshes, i.e., meshes composed of elements of different types. Hybrid meshes are playing an increasingly important role in all fields of modeling, because elements of different types are frequently considered either because such meshes are easier to construct or because they produce better numerical results. The proposed data structures are designed to achieve a balance between their memory requirements and the time complexity necessary to answer topological queries while accepting cells (elements) of different types. Additionally these data structures are easy to implement and to operate, because they are based on integer arrays and on basic arithmetic rules. A comparison with other existing data structures regarding their memory requirements and of the time complexities for the algorithms to answer general topological queries is also presented. The comparison shows that the overhead required to accept arbitrary cell types is small.

关键词： Topological data structures Hybrid meshes compact data structures Index-based data structures Local adjacencies

来源：评论

学校读者我要写书评

暂无评论

Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2020年第10期62卷 4091-4111页

作者： Felipe Castro, Juan Romero, Miguel Gutierrez, Gilberto Caniupan, Monica Quijada-Fuentes, Carlos Univ Bio Bio Bio Bio Chile

In this paper, we present two algorithms to obtain the convex hull of a set of points that are stored in the compact data structure called k(2)-tree. This problem consists in given a set of points P in the Euclidean space obtaining the smallest convex region (polygon) containing P. Traditional algorithms to compute the convex hull do not scale well for large databases, such as spatial databases, since the data does not reside in main memory. We use the k(2)-tree compact data structure to represent, in main memory, efficiently a binary adjacency matrix representing points over a 2D space. This structure allows an efficient navigation in a compressed form. The experimentations performed over synthetical and real data show that our proposed algorithms are more efficient. In fact they perform over four order of magnitude compared with algorithms with time complexity of O(n log n).

关键词： Algorithms data structures Spatial databases Computational geometry compact data structures Convex hull

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：