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

succinct data structures for bounded clique-width graphs

DISCRETE APPLIED MATHEMATICS 2024年 352卷 55-68页

作者： Chakraborty, Sankardeep Jo, Seungbum Sadakane, Kunihiko Satti, Srinivasa Rao Univ Tokyo Tokyo Japan Chungnam Natl Univ Daejeon South Korea Norwegian Univ Sci & Technol Trondheim Norway

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic traceability, and in this paper, we study the class of bounded clique-width graphs through the lens of succinct data structures. A data structure is said to be succinct if the amount of space used by the data structure is information-theoretically optimal up to lower-order additive terms. More specifically, we design a succinct data structure for graphs on n vertices whose clique-width is at most k <= & varepsilon;root logn for some constant 0 < & varepsilon;< 1/6, that supports degree, adjacency, and neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018). As an application of our main technique, we also propose succinct data structures for distance-hereditary and Ptolemaic graphs, which are subclasses of the class of graphs with clique-width at most 3. (c) 2024 Elsevier B.V. All rights reserved.

关键词： succinct data structures Bounded clique-width graphs Cographs Distance hereditary graphs

来源：评论

学校读者我要写书评

暂无评论

succinct data structures for nearest colored node in a tree

引用

INFORMATION PROCESSING LETTERS 2018年 132卷 6-10页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

We give succinct data structures that store a tree with colors on the nodes. Given a node x and a color alpha, the structures find the nearest node to x with color alpha. Our results improve the O(n log n)-bits struct... 详细信息

关键词： succinct data structures Labeled trees Colored trees

来源：评论

学校读者我要写书评

暂无评论

succinct data structures for flexible text retrieval systems

引用

JOURNAL OF DISCRETE ALGORITHMS 2007年第1期5卷 12-22页

作者： Sadakane, Kunihiko Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka Japan

We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf *idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf * idf scores there has been no efficient data structures for arbitrary patterns. Our new data structures support these queries using small space. The space is only 2/epsilon times the size of compressed documents plus 10n bits for a document collection of length n, for any 0 < epsilon <= 1. This is much smaller than the previous O(n logn) bit data structures. Query time is O( m+q log(epsilon) n) for listing and computing tf *idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Information retrieval Tf* idf succinct data structures Suffix trees Inverted files

来源：评论

学校读者我要写书评

暂无评论

succinct data structures in Information Retrieval: Theory and Practice 16

Succinct Data Structures in Information Retrieval: Theory an...

引用

39th International ACM SIGIR conference on Research and Development in Information Retrieval

作者： Gog, Simon Venturini, Rossano Karlsruhe Inst Technol Inst Theoret Informat Fasanengarten 5 D-76131 Karlsruhe Germany Univ Pisa Dept Comp Sci Largo Bruno Pontecorvo 3 I-56127 Pisa Italy

ISBN: (纸本)9781450340694

succinct data structures are used today in many information retrieval applications, e.g., posting lists representation, language model representation, indexing (social) graphs, query auto-completion, document retrieval and indexing dictionary of strings, just to mention the most recent ones. These new kind of data structures mimic the operations of their classical counterparts within a comparable time complexity but require much less space. With the availability of several libraries for basic succinct structures - like SDSL, succinct, Facebook's Folly, and Sux - it is relatively easy to directly profit from advances in this field. In this tutorial we will introduce this field of research by presenting the most important succinct data structures to represent set of integers, set of points, trees, graphs and strings together with their most important applications to Information Retrieval problems. The introduction of the succinct data structures will be sustained with a practical session with programming handouts to solve. This will allow the attendees to directly experiment with implementations of these solutions on real datasets and understand the potential benefits they can bring on their own projects.

关键词： data compression succinct data structures indexing

来源：评论

学校读者我要写书评

暂无评论

succinct data structures ... Potential for Symbolic Computation? 16

Succinct Data Structures ... Potential for Symbolic Computat...

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Munro, J. Ian Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

We focus on succinct data structures, that is on time and space efficient representations of trees and other combinatorial objects that dominate the memory requirements of most sophisticated programs and systems.

ISBN: (纸本)9781450343800

关键词： data structures space efficiency information theory succinct data structures

来源：评论

学校读者我要写书评

暂无评论

The cell probe complexity of succinct data structures

引用

THEORETICAL COMPUTER SCIENCE 2007年第3期379卷 405-417页

作者： Gal, Anna Miltersen, Peter Bro Univ Aarhus Dept Comp Sci Aarhus Denmark Univ Texas Dept Comp Sci Austin TX 78712 USA

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size I (the bit probe model). In this model, the goal is to represent n -bit data with s = n + r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. In this paper, we consider the case of succinct representations, where s = n + r for some redundancy r << n. For a Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy-query time tradeoff of the form (r + 1)t >= Omega(n/ log n). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (r + 1)t >= Omega(n) for certain problems. Previously, no omega(m) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies. By restricting our attention to systematic or index structures phi satisfying phi (x) = x . phi* (x) for some map phi* (where - denotes concatenation), we show similar lower bounds on the redundancy-query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search. (c) 2007 Elsevier B.V All rights reserved.

关键词： succinct data structures cell probe complexity polynomial evaluation with preprocessing

来源：评论

学校读者我要写书评

暂无评论

Optimized succinct data structures for massive data

引用

SOFTWARE-PRACTICE & EXPERIENCE 2014年第11期44卷 1287-1314页

作者： Gog, Simon Petri, Matthias Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic 3001 Australia

succinct data structures provide the same functionality as their corresponding traditional data structure in compact space. We improve on functions rank and select, which are the basic building blocks of FM-indexes and other succinct data structures. First, we present a cache-optimal, uncompressed bitvector representation that outperforms all existing approaches. Next, we improve, in both space and time, on a recent result by Navarro and Providel on compressed bitvectors. Last, we show techniques to perform rank and select on 64-bit words that are up to three times faster than existing methods. In our experimental evaluation, we first show how our improvements affect cache and runtime performance of both operations on data sets larger than commonly used in the evaluation of succinct data structures. Our experiments show that our improvements to these basic operations significantly improve the runtime performance and compression effectiveness of FM-indexes on small and large data sets. To our knowledge, our improvements result in FM-indexes that are either smaller or faster than all current state of the art implementations. Copyright (C) 2013 John Wiley & Sons, Ltd.

关键词： succinct data structures binary sequences FM-index algorithm engineering massive data sets rank select SSE hugepages

来源：评论

学校读者我要写书评

暂无评论

Rank and Select for succinct data structures

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2009年第C期236卷 131-145页

作者： Farina, Antonio Ladra, Susana Pedreira, Oscar Places, Angeles S. Univ A Coruna Database Lab La Coruna 15071 Spain

In this paper, we study different approaches for rank and select on sequences of bytes and propose new implementation strategies. Extensive experimental evaluation comparing the efficiency of the different alternatives are provided. Given a sequence of bits, a rank query counts the number of occurrences of the bit 1 up to a given position, and a select query returns the position of the ith occurrence of the bit 1. These operations are widely used in information retrieval and management, being the base of several data structures and algorithms for text collections, graphs, etc. There exist solutions for computing these operations on sequences of bits in constant time using additional information. However, new applications require rank and select to be computed on sequences of bytes instead of bits. The solutions for the binary case are not directly applicable to sequences of bytes. The existing solutions for the byte case vary in their space-time trade-off which can still be improved.

关键词： information retrieval algorithms succinct data structures rank select

来源：评论

学校读者我要写书评

暂无评论

The cell probe complexity of succinct data structures

The cell probe complexity of succinct data structures

引用

30th International Colloquium on Automata, Languages and Programming (ICALP 2003)

作者： Gal, Anna Miltersen, Peter Bro Univ Aarhus Dept Comp Sci Aarhus Denmark Univ Texas Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)3540404937

关键词： succinct data structures cell probe complexity polynomial evaluation with preprocessing

来源：评论

学校读者我要写书评

暂无评论

Application-Oriented succinct data structures for Big data

引用

REVIEW OF SOCIONETWORK STRATEGIES 2019年第2期13卷 227-236页

作者： Shibuya, Tetsuo Tokyo Japan

A data structure is called succinct if its asymptotical space requirement matches the original data size. The development of succinct data structures is an important factor to deal with the explosively increasing big data. Moreover, wider variations of big data have been produced in various fields recently and there is a substantial need for the development of more application-specific succinct data structures. In this study, we review the recently proposed application-oriented succinct data structures motivated by big data applications in three different fields: privacy-preserving computation in cryptography, genome assembly in bioinformatics, and work space reduction for compressed communications.

关键词： Sublinear paradigm succinct data structures Survey Oblivious RAM de Bruijn graph Compressed communication Work space reduction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：