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

44th ACM SIGMOD International Conference on Management of data

作者： Zhang, Huanchen Lim, Hyeontaek Leis, Viktor Andersen, David G. Kaminsky, Michael Keeton, Kimberly Pavlo, Andrew Carnegie Mellon Univ Pittsburgh PA 15213 USA Tech Univ Munich Munich Germany Intel Labs Pittsburgh PA USA Hewlett Packard Enterprise Palo Alto CA USA

ISBN: (纸本)9781450317436

We present the succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries: open-range queries, closed-range queries, and range counts. SuRF is based on a new data structure called the Fast succinct Trie (FST) that matches the point and range query performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node. The false positive rates in SuRF for both point and range queries are tunable to satisfy different application needs. We evaluate SuRF in RocksDB as a replacement for its Bloom filters to reduce I/O by filtering requests before they access on-disk data structures. Our experiments on a 100 GB dataset show that replacing RocksDB's Bloom filters with SuRFs speeds up open-seek (without upper-bound) and closed-seek (with upper-bound) queries by up to 1.5x and 5x with a modest cost on the worst-case (all-missing) point query throughput due to slightly higher false positive rate.

关键词： range filter lsm-trees surf fast succinct tries succinct data structures

来源：评论

学校读者我要写书评

暂无评论

On the succinct Representation of Equivalence Classes

引用

ALGORITHMICA 2017年第3期78卷 1020-1040页

作者： El-Zein, Hicham Lewenstein, Moshe Munro, J. Ian Raman, Venkatesh Chan, Timothy M. Univ Waterloo David Cheriton Sch Comp Sci Waterloo ON Canada Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Inst Math Sci Madras Tamil Nadu India

Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of is necessary and sufficient. In other words, bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of for the label length, if each vertex need not get a unique label. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set , we first show that bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses bits to support equivalence queries and unions in worst case time or expected amortized time where is the inverse Ackermann function. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set for any constant , we show that bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model.

关键词： Equivalence classes Labeling schemes succinct data structures

来源：评论

学校读者我要写书评

暂无评论

succinct Indices for Path Minimum, with Applications

引用

ALGORITHMICA 2017年第2期78卷 453-491页

作者： Chan, Timothy M. He, Meng Munro, J. Ian Zhou, Gelin Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Dalhousie Univ Fac Comp Sci Halifax NS Canada

In the path minimum problem, we preprocess a tree on n weighted nodes, such that given an arbitrary path, the node with the smallest weight along this path can be located. We design novel succinct indices for this problem under the indexing model, for which weights of nodes are read-only and can be accessed with ranks of nodes in the preorder traversal sequence of the input tree. We presentan index within O(m) bits of additional space that supports queries in time and accesses to the weights of nodes, for any integer;and an index within bits of additional space that supports queries in time and accesses to the weights of nodes. Here a(m, n) is the inverse-Ackermann function, and a(n) = a(n, n). These indices give us the first succinct data structures for the path minimum problem. Following the same approach, we also develop succinct data structures for semigroup path sum queries, for which a query asks for the sum of weights along a given query path. One of our data structures requires n lg sigma + 2n + o(n lg sigma) bits of space and O(alpha(n)) query time, where sigma is the size of the semigroup. In the path reporting problem, queries ask for the nodes along a query path whose weights are within a two-sided query range. Using the succinct indices for path minimum queries, we achieve three different time/space tradeoffs for path reporting by designing an O(n)-word data structure with O(lg(epsilon) n + occ . lg(epsilon) n) query time;an O(n lg lg n)-word data structure with O(lg lg n + occ lg lg n) query time;and an O(n lg . n)-word data structure with O(lg lg n + occ) query time. Here occ is the number of nodes reported and is an arbitrary constant between 0 and 1. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries (Chan et al. 2011), which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than n, we further improve both the query time and the space cost of

关键词： Path minimum Semigroup path sum Path reporting succinct data structures succinct encoding of directed topology trees

来源：评论

学校读者我要写书评

暂无评论

I/O-Efficient Path Traversal in succinct Planar Graphs

引用

ALGORITHMICA 2017年第3期77卷 714-755页

作者： Dillabaugh, Craig He, Meng Maheshwari, Anil Zeh, Norbert Carleton Univ Sch Comp Sci 5302 HP1125 Colonel By Dr Ottawa ON K1S 5B6 Canada Dalhousie Univ Fac Comp Sci 6050 Univ AvePOB 15000 Halifax NS B3H 4R2 Canada Dalhousie Univ Fac Comp Sci 6050 Univ Ave Halifax NS B3H 1W5 Canada

We present a technique for representing bounded-degree planar graphs in a succinct fashion while permitting I/O-efficient traversal of paths. Using our representation, a graph with N vertices, (In this paper denotes ) each with an associated key of bits, can be stored in bits and traversing a path of length K takes I/Os, where B denotes the disk block size. By applying our construction to the dual of a terrain represented as a triangular irregular network, we can represent the terrain in the above space bounds and support path traversals on the terrain using I/Os, where K is the number of triangles visited by the path. This is useful for answering a number of queries on the terrain, such as reporting terrain profiles, trickle paths, and connected components.

关键词： External memory algorithms Path traversal Planar graphs succinct 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

来源：评论

学校读者我要写书评

暂无评论

m-Bonsai: A Practical Compact Dynamic Trie

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2018年第8期29卷 1257-1278页

作者： Poyias, Andreas Puglisi, Simon J. Raman, Rajeev Univ Leicester Dept Informat Univ Rd Leicester LE1 7RH Leics England Univ Helsinki Dept Comp Sci Helsinki Inst Informat Technol POB 68 FI-00014 Helsinki Finland

We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with n nodes with an alphabet of size sigma, the information-theoretic space lower bound is n log sigma + O(n) bits. The Bonsai data structure is a compact trie proposed by Darragh et al. (Softw. Pract. Exper. 23(3) (1993) 277-291). Its disadvantages include the user having to specify an upper bound M on the trie size in advance (which cannot be changed easily after initalization), a space usage of M log sigma + O(M log log M) (which is asymptotically non-optimal for smaller sigma or if n << M) and a lack of support for deletions. It supports traversal and update operations in O(1/epsilon) expected time (based on assumptions about the behaviour of hash functions), where epsilon = (M - n)/M and has excellent speed performance in practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining a trie that uses (1+beta)n(log sigma+O(1)) bits in expectation, and supports traversal and update operations in O(1/beta) expected time and O(1/beta(2)) amortized expected time, for any user-specified parameter beta > 0 (again based on assumptions about the behaviour of hash functions). We give an implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.

关键词： Trie succinct data structures dynamic trie cardinal tree digital search tree compact hashing

来源：评论

学校读者我要写书评

暂无评论

Fast compressed self-indexes with deterministic linear-Time construction 28

Fast compressed self-indexes with deterministic linear-Time ...

引用

28th International Symposium on Algorithms and Computation, ISAAC 2017

作者： Munro, J.Ian Navarro, Gonzalo Nekrich, Yakov Cheriton School of Computer Science University of Waterloo Canada Department of Computer Science Center of Biotechnology and Bioengineering University of Chile Chile

ISBN: (纸本)9783959770545

We introduce a compressed suffix array representation that, on a text T of length n over an alphabet of size can be built in O(n) deterministic time, within O(n log ) bits of working space, and counts the number of occurrences of any pattern P in T in time O(|P|+log logw -) on a RAM machine of w = (log n)-bit words. This new index outperforms all the other compressed indexes that can be built in linear deterministic time, and some others. The only faster indexes can be built in linear time only in expectation, or require -(n log n) bits.

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

来源：评论

学校读者我要写书评

暂无评论

Document listing on repetitive collections with guaranteed performance 28

Document listing on repetitive collections with guaranteed p...

引用

28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017

作者： Navarro, Gonzalo Center for Biotechnology and Bioengineering Department of Computer Science University of Chile Santiago Chile

ISBN: (纸本)9783959770392

We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1, σ] is composed of D copies of a string of size n, and s single-character edits are applied on the copies. We introduce the first document listing index with size Õ(n+s), precisely O((n lg σ+s lg2 N) lg D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc strings where it appears in time O(m2 + m lg N(lgD + lgϵ N) · ndoc), for any constant ϵ > 0. © Gonzalo Navarro.

关键词： Document listing Grammar compression Range minimum queries Repetitive string collections succinct data structures

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Optimal Encodings of Range data structures for Selection and Top-k Queries

引用

ACM TRANSACTIONS ON ALGORITHMS 2017年第2期13卷 28-28页

作者： Grossi, Roberto Iacono, John Navarro, Gonzalo Raman, Rajeev Satti, S. Rao Univ Pisa Dept Informat Largo Bruno Pontecorvo 3 I-56127 Pisa Italy NYU Polytech Inst Dept Comp Sci & Engn New York NY 10003 USA Univ Chile Dept Comp Sci Beauchef 851 Santiago Chile Univ Leicester Dept Comp Sci Leicester Leics England Seoul Natl Univ Sch Comp Sci & Engn Seoul South Korea Polytech Inst New York Dept Comp Sci & Engn 2 MetroTech Ctr Brooklyn NY 11201 USA Univ Leicester Dept Informat Univ Rd Leicester LE1 7RH Leics England Seoul Natl Univ Dept Comp Sci & Engn 1 Gwanak Ro Seoul 08826 South Korea

Given an array A[1, n] of elements with a total order, we consider the problem of building a data structure that solves two queries: (a) selection queries receive a range [i, j] and an integer k and return the position of the kth largest element in A[i, j];(b) top-k queries receive [i, j] and k and return the positions of the k largest elements in A[i, j]. These problems can be solved in optimal time, O(1 + lgk/lg lg n) and O(k), respectively, using linear-space data structures. We provide the first study of the encoding data structures for the above problems, where A cannot be accessed at query time. Several applications are interested in the relative order of the entries of A, and their positions, rather their actual values, and thus we do not need to keep A at query time. In those cases, encodings save storage space: we first show that any encoding answering such queries requires nlg k - O(n + klg k) bits of space;then, we design encodings using O(nlg k) bits, that is, asymptotically optimal up to constant factors, while preserving optimal query time.

关键词： succinct data structures encoding data structures range search data structures range minimum queries

来源：评论

学校读者我要写书评

暂无评论

Simple and efficient fully-functional succinct trees

引用

THEORETICAL COMPUTER SCIENCE 2016年第PartB期656卷 135-145页

作者： Cordova, Joshimar Navarro, Gonzalo Univ Chile Dept Comp Sci Ctr Biotechnol & Bioengn Santiago Region Metropol Chile

The fully-functional succinct tree representation of Navarro and Sadakane (2014) [10] supports a large number of operations in constant time using 2n + o(n) bits. However, the full idea is hard to implement. Only a simplified version with O(lgn) operation time has been implemented and shown to be practical and competitive. We describe a new variant of the original idea that is much simpler to implement and has worst-case time O(lglgn) for the operations. An implementation based on this version is experimentally shown to be superior to existing implementations. (C) 2016 Elsevier B.V. All rights reserved.

关键词： succinct data structures Ordinal trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：