NSTL国家科技图书文献中心

1. Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number EI 工程索引 NSTL国家科技图书文献中心

Chakraborty, Sankard... | Jo, Seungbum - 《Theoretical computer science》 - 2023,941 - 156～166 - 共11页 - 被引量：2

摘要：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 sho...

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

2. Succinct navigational oracles for families of intersection graphs on a circle EI 工程索引 SCIE Web of Science核心 NSTL国家科技图书文献中心

Acan, Huseyin | Chakraborty, Sankard...... - 《Theoretical computer science》 - 2022,928 - 151～166 - 共16页 - 被引量：3

摘要：We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency and neighbor-hood efficiently for int...

关键词： Intersection graph | Succinct data structure | Navigational query | INTERVAL-GRAPHS | RECOGNITION

3. Encoding Two-Dimensional Range Top-k Queries EI 工程索引 SCIE Web of Science核心 SCOPUS Scopus数据库 NSTL国家科技图书文献中心

Jo, Seungbum | Lingala, Rahul ... - 《Algorithmica》 - 2021,83(11) - 3379～3402 - 共24页 - 被引量：1

摘要：We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-...

关键词： Encoding model | Top-k query | Range minimum query

4. Approximate query processing over static sets and sliding windows EI 工程索引 SCOPUS Scopus数据库 SCIE Web of Science核心 NSTL国家科技图书文献中心

Ben Basat, Ran | Jo, Seungbum ... - 《Theoretical computer science》 - 2021,885 - 1～14 - 共14页 - 被引量：1

摘要：Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem...

关键词： Streaming | Algorithms | Sliding window | Lower bounds

5. Succinct Encodings for Families of Interval Graphs EI 工程索引 SCIE Web of Science核心 SCOPUS Scopus数据库 NSTL国家科技图书文献中心

Acan, Huseyin | Chakraborty, Sankard...... - 《Algorithmica》 - 2021,83(3) - 776～794 - 共19页 - 被引量：6

摘要：We consider the problem of designing succinct data structures for interval graphs with n vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time. Towards sh...

关键词： Space efficient data structures | Succinct encoding | Interval graphs | Proper interval graphs | Unit interval graphs

6. Compressed range minimum queries SCOPUS Scopus数据库 EI 工程索引 SCIE Web of Science核心 NSTL国家科技图书文献中心

Gawrychowski, Pawel | Jo, Seungbum ... - 《Theoretical computer science》 - 2020,812 - 39～48 - 共10页 - 被引量：2

摘要：Given a string S of nintegers in [0, sigma), a range minimum query RMQ(i, j) asks for the index of the smallest integer in S[i... j]. It is well known that the problem can be solved with a succinct da...

关键词： RMQ | Grammar compression | SLP | Tree compression | Cartesian tree

7. Combined compression of multiple correlated data streams for online-diagnosis systems EI 工程索引 SCIE Web of Science核心 SCOPUS Scopus数据库 NSTL国家科技图书文献中心

Meckel, Simon | Lohrey, Markus ... - 《Microprocessors and microsystems》 - 2020,77(Sep.) - 103184.1～103184.13 - 共13页 - 被引量：1

摘要：Online fault-diagnosis is applied to various systems to enable an automatic monitoring and, if applicable, the recovery from faults to prevent the system from failing. For a sound decision on occurred...

关键词： Online-diagnosis | Real-time | Data compression | Scheduling

8. An architecture for online-diagnosis systems supporting compressed communication SCIE Web of Science核心 SCOPUS Scopus数据库 NSTL国家科技图书文献中心

Jo, Seungbum | Lohrey, Markus ... - 《Microprocessors and microsystems》 - 2018,61(Sep.) - 242～256 - 共15页 - 被引量：2

摘要：With its ability to detect, identify and, if applicable, recover from occurred faults, online-diagnosis can help achieving fault-tolerant systems. A sound decision on an occurred fault is the foundati...

关键词： Online-diagnosis | Real-time | Fault-tolerance | Data compression | Scheduling

9. Compressed Bit vectors Based on Variable-to-Fixed Encodings SCOPUS Scopus数据库 SCIE Web of Science核心 NSTL国家科技图书文献中心

Jo, Seungbum | Joannou, Stelios ... - 《The Computer journal》 - 2017,60(5) - 761～775 - 共15页

摘要：We consider practical implementations of compressed bitvectors, which support rank and select operations on a given bit-string, while storing the bit-string in compressed form. Our approach relies on ...

关键词： bitvector | rank and select | variable-to-fixed encoding | entropy

10. Simultaneous encodings for range and next/previous larger/smaller value queries SCOPUS Scopus数据库 SCIE Web of Science核心 NSTL国家科技图书文献中心

Jo, Seungbum | Satti, Srinivasa Rao - 《Theoretical computer science》 - 2016,654 - 80～91 - 共12页 - 被引量：1

摘要：Given an array of n elements from a total order, we propose encodings that support various range queries (range minimum, range maximum and their variants), and previous and next smaller/larger value q...