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

Space-efficient data-analysis queries on grids

THEORETICAL COMPUTER SCIENCE 2013年 482卷 60-72页

作者： Navarro, Gonzalo Nekrich, Yakov Russo, Luis M. S. Univ Chile Dept Comp Sci Santiago Chile Univ Tecn Lisboa Inst Super Tecn P-1096 Lisbon Portugal

We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on geometric queries such as dominance and rectangle visibility, and on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries less frequently considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor, mode, and various top-k queries, considering static and dynamic scenarios. (C) 2012 Elsevier S.V. All rights reserved.

关键词： Range queries databases succinct data structures Dynamic data structures Statistical database queries Orthogonal range queries Point dominance Rectangle visibility Wavelet tree Range minimum queries Alpha majority Quantile Top-k Mode

来源：评论

学校读者我要写书评

暂无评论

Optimizing RPQs over a compact graph representation

引用

VLDB JOURNAL 2024年第2期33卷 349-374页

作者： Arroyuelo, Diego Gomez-Brandon, Adrian Hogan, Aidan Navarro, Gonzalo Rojas-Ledesma, Javiel Pontificia Univ Catolica Chile Escuela Ingn IMFD Santiago Chile Pontificia Univ Catolica Chile Escuela Ingn DCC Santiago Chile Univ A Coruna IMFD La Coruna Spain Univ A Coruna CITIC La Coruna Spain Univ Chile IMFD Santiago Chile Univ Chile DCC Santiago Chile

We propose techniques to evaluate regular path queries (RPQs) over labeled graphs (e.g., RDF). We apply a bit-parallel simulation of a Glushkov automaton representing the query over a ring: a compact wavelet-tree-based index of the graph. To the best of our knowledge, our approach is the first to evaluate RPQs over a compact representation of such graphs, where we show the key advantages of using Glushkov automata in this setting. Our scheme obtains optimal time, in terms of alternation complexity, for traversing the product graph. We further introduce various optimizations, such as the ability to process several automaton states and graph nodes/labels simultaneously, and to estimate relevant selectivities. Experiments show that our approach uses 3-5x\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} less space, and is over 5x\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} faster, on average, than the next best state-of-the-art system for evaluating RPQs.

关键词： Regular path queries Ring index succinct data structures Graph databases

来源：评论

学校读者我要写书评

暂无评论

Minimal indices for predecessor search

引用

INFORMATION AND COMPUTATION 2015年 240卷 12-30页

作者： Cohen, Sarel Fiat, Amos Hershcovitch, Moshik Kaplan, Haim Tel Aviv Univ IL-69978 Tel Aviv Israel

Wegive a new predecessor data structure which improves upon the index size of the Patrascu-Thorup data structures, reducing the index size from O(nw(4/5)) bits to O(n log w) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra O(log w) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of O(n log w) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree w/logw(compared to w(1/5) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Successor search Predecessor search succinct data structures Cell probe model Fusion trees Tries Word RAM model

来源：评论

学校读者我要写书评

暂无评论

Rank and select revisited and extended

引用

THEORETICAL COMPUTER SCIENCE 2007年第3期387卷 332-347页

作者： Makinen, Veli Navarro, Gonzalo Univ Chile Dept Comp Sci Ctr Web Res Santiago Chile Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

The deep connection between the Burrows-Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes. This paper is devoted to alternative implementations and extensions of rank and select data structures. First, we show that one can use gap encoding techniques to obtain constant time rank and select queries in essentially the same space as what is achieved by the best current direct solution (and sometimes less). Second, we extend symbol rank and select to substring rank and select, giving several space/time trade-offs for the problem. An application of these queries is in position-restricted substring searching, where one can specify the range in the text where the search is restricted to, and only occurrences residing in that range are to be reported. In addition, arbitrary occurrences are reported in text position order. Several byproducts of our results display connections with searchable partial sums, Chazelle's two-dimensional data structures, and Grossi et al.'s wavelet trees. (c) 2007 Elsevier B.V. All rights reserved.

关键词： succinct data structures compressed data structures gap encoding range searching position-restricted substring searching wavelet trees substring rank and select

来源：评论

学校读者我要写书评

暂无评论

A framework for designing space-efficient dictionaries for parameterized and order-preserving matching

引用

THEORETICAL COMPUTER SCIENCE 2021年 854卷 52-62页

作者： Ganguly, Arnab Hon, Wing-Kai Sadakane, Kunihiko Shah, Rahul Thankachan, Sharma V. Yang, Yilin Univ Wisconsin Dept Comp Sci Whitewater WI 53190 USA Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Univ Tokyo Dept Math Informat Tokyo Japan Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Univ Cent Florida Dept Comp Sci Orlando FL 32816 USA

Let P be a collection of d patterns {P1, P2, ... , Pd} of total length n characters, which are chosen from an alphabet Sigma of size sigma. Given a text T (over Sigma), the dictionary indexing problem is to create a data structure using which we can report all positions j (called occurrences) where at least one of the patterns P-i is an element of P is a match with the same-length substring of T that starts at j. We consider this problem under the following definitions of matching Parameterized Matching: The characters of Sigma are partitioned into static characters and parameterized characters. Two equal length strings S and S' are a parameterized match iff the static characters match exactly, and there exists a one-to-one function which renames the parameterized characters in S to those in S'. Order-Preserving Matching: The alphabet Sigma is ordered. Two equal length strings S and S' are an order-preserving match iff for any two integers i, j is an element of [1, vertical bar S vertical bar], S[i] < S[j] double left right arrow S'[i] < S'[j], where denotes the precedence order in Sigma. Let epsilon 0 be an arbitrarily small constant. For parameterized matching, we first present a compact O (n log sigma + d log n)-bit index that reports all occ occurrences in O (vertical bar T vertical bar(log sigma + log sigma n) + occ) time, and then a succinct n log(sigma) + o(n log sigma) + O (d log n)-bit index that reports all occ occurrences in O (vertical bar T vertical bar(log sigma + log(epsilon) n log(sigma) n) + occ) time. For order-preserving matching, we present indexes of the same sizes, but with slightly increased query time. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Sparsification Trie AC automaton succinct data structures

来源：评论

学校读者我要写书评

暂无评论

succinct Permutation Graphs

引用

ALGORITHMICA 2023年第2期85卷 509-543页

作者： Tsakalidis, Konstantinos Wild, Sebastian Zamaraev, Viktor Univ Liverpool Dept Comp Sci Ashton BldgAshton St Liverpool L69 3BX Merseyside England

We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. in Theor Comput Sci, https://***/10.1016/***.2022.06.022, 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an O(log n/ log log n)-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: CLIQUE, COLORING, INDEPENDENT SET, HAMILTONIAN CYCLE, ALL- PAIR SHORTEST PATHS, and others. Finally, we initiate the study of semi-distributed graph representations;a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only O(n) bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.

关键词： succinct data structures Distance oracles Permutation graphs Bipartite permutations graphs Circular permutation graphs Graph compression Graph encoding

来源：评论

学校读者我要写书评

暂无评论

Optimal Indexes for Sparse Bit Vectors

引用

ALGORITHMICA 2014年第4期69卷 906-924页

作者： Golynski, Alexander Orlandi, Alessio Raman, Rajeev Rao, S. Srinivasa Google Inc New York NY USA Google Switzerland GmbH Zurich Switzerland Univ Leicester Dept Comp Sci Leicester Leics England Seoul Natl Univ Sch Comp Sci & Engn Seoul South Korea

We consider the problem of supporting rank and select operations on a bit vector of length m with n 1-bits. The problem is considered in the succinct index model, where the bit vector is stored in "read-only" memory and an additional data structure, called the index is created during pre-processing to help answer the above queries. We give asymptotically optimal density-sensitive trade-offs, involving both m and n, that relate the size of the index to the number of accesses to the bit vector (and processing time) needed to answer the above queries. The results are particularly interesting for the case where n=o(m).

关键词： succinct data structures Bit-vectors Rank and select Systematic encoding Information-theoretic lower bound Redundancy

来源：评论

学校读者我要写书评

暂无评论

Fast Compressed Self-indexes with Deterministic Linear-Time Construction

引用

ALGORITHMICA 2020年第2期82卷 316-337页

作者： Munro, J. Ian Navarro, Gonzalo Nekrich, Yakov Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada Univ Chile Dept Comp Sci CeBiB Ctr Biotechnol & Bioengn Santiago Chile Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

We introduce a compressed suffix array representation that, on a text T of length n over an alphabet of size sigma, can be built in O(n) deterministic time, within O(nlog sigma) bits of working space, and counts the number of occurrences of any pattern P in T in time O(|P|+loglogw sigma) on a RAM machine of w=Omega(logn)-bit words. This time is almost optimal for large alphabets (log sigma=Theta(logn)), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require Theta(nlogn) bits. For smaller alphabets, where log sigma=o(logn), we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time O(|P|/log sigma n+log sigma En) for any constant E>0. This is almost RAM-optimal in the typical case where w=Theta(logn).

关键词： succinct data structures Self-indexes Suffix arrays Deterministic construction

来源：评论

学校读者我要写书评

暂无评论

Path queries on functions

引用

THEORETICAL COMPUTER SCIENCE 2019年 770卷 34-50页

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

Let f : [1..n] -> [1..n] be a function, and l : [1..n] -> [1..sigma] indicate a label assigned to each element of the domain. We design several compact data structures that answer various kinds of summary queries on the labels of paths in f. For example, we can find either the minimum label in f(k)(i) for a given i and any k >= 0 in a given range [k(1)..k(2)], or the minimum label in f f(-k)(i) for a given i and k > 0, using n lgn + n lg sigma + o(n lgn) bits and time O(alpha(n)), the inverse Ackermann function. Within similar space we can count, in time O(lgn/ lglgn), the number of labels within a range, and report each element with such labels in O(lgn/lglgn) additional time. Several other tradeoffs and possible queries are considered, such as selection, top-r queries and tau-majorities. Finally, we consider queries that allow us navigate on the graph of the function, such as the nearest common successor of two elements, or the nearest successor or predecessor of an element within a range of labels. (C) 2018 Elsevier B.V. All rights reserved.

关键词： succinct data structures Integer functions Range queries Trees and permutations

来源：评论

学校读者我要写书评

暂无评论

Representing trees of higher degree

引用

ALGORITHMICA 2005年第4期43卷 275-292页

作者： Benoit, D Demaine, ED Munro, JI Raman, R Raman, V Rao, SS Invio Bioinformat Inc Halifax NS B4A 1E6 Canada MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England Inst Math Sci Madras 600113 Tamil Nadu India

This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled {1,..., k}, each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child, and subtree size. For cardinal trees the structure also supports finding the child labelled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers (1,..., n), giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.

关键词： data structures analysis of algorithms succinct data structures data compression information theory cardinal trees ordinal trees tries digital search trees dictionary hashing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：