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

Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams

THEORY OF COMPUTING SYSTEMS 2023年第6期67卷 1241-1267页

作者： Bishnu, Arijit Ghosh, Arijit Kolay, Sudeshna Mishra, Gopinath Saurabh, Saket Indian Stat Inst Kolkata India Indian Inst Technol Kharagpur Kharagpur India Univ Warwick Coventry England HBNI Inst Math Sci Chennai India

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O(f (k) log(O(1)) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Omega (n) bits of storage for any streaming algorithm;e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F-Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F-Subgraph Deletion and F-Minor Deletion.

关键词： FPT streaming algorithms Vertex cover Subgraph deletion problems Minor deletion problems

来源：评论

学校读者我要写书评

暂无评论

Turnstile streaming algorithms Might as Well Be Linear Sketches 14

Turnstile Streaming Algorithms Might as Well Be Linear Sketc...

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Li, Yi Nguyen, Huy L. Woodruff, David P. Max Planck Inst Informat Saarbrucken Germany Princeton Univ Princeton NJ 08544 USA IBM Res Almaden San Jose CA USA

ISBN: (纸本)9781450327107

In the turnstile model of data streams, an underlying vector x E {m, m +1,..., m 1, m} is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f (x) with constant probability while only making a single pass over this sequence of updates and using a small amount of space. All known algorithms in this model are linear sketches: they sample a matrix A from a distribution on integer matrices in the preprocessing phase, and maintain the linear sketch A " x while processing the stream. At the end of the stream, they output an arbitrary function of A " x. One cannot help but ask: are linear sketches universal? In this work we answer this question by showing that any 1 pass constant probability streaming algorithm for approximating an arbitrary function f of x in the turnstile model can also be implemented by sampling a matrix A from the uniform distribution on 0 (n log m) integer matrices, with entries of magnitude poly (n), and maintaining the linear sketch Ax. Furthermore, the logarithm of the number of possible states of Ax, as x ranges over {m 1,, m}n, plus the amount of randomness needed to store A, is at most a logarithmic factor larger than the space required of the space-optimal algorithm. Our result shows that to prove space lower bounds for 1-pass streaming algorithms, it suffices to prove lower bounds in the simultaneous model of communication complexity, rather than the stronger 1-way model. Moreover, the fact that we can assume we have a linear sketch with polynomially-bounded entries further simplifies existing lower bounds, e.g., for frequency moments we present a simpler proof of the Q(711-2/k) bit complexity lower bound without using communication complexity.

关键词： streaming algorithms linear sketches lower bounds communication complexity

来源：评论

学校读者我要写书评

暂无评论

JACC-FPGA: A hardware accelerator for Jaccard similarity estimation using FPGAs in the cloud

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2023年 138卷 26-42页

作者： Soto, Javier E. Hernandez, Cecilia Figueroa, Miguel Univ Concepcion Elect Engn Dept Concepcion Chile Univ Concepcion Comp Sci Dept Concepcion Chile Ctr Biotechnol & Bioengn CeBiB Santiago Chile

Genomic similarity is a key metric in genomics, used in important tasks such as genome clustering and metagenomic profiling. One commonly-used approach is to treat each genome as a set of k-mers and to compute the Jaccard coefficient between each genome pair. However, computing the Jaccard coefficient between genomes in a large dataset is a computationally-challenging task. In this paper, we present an algorithm and accelerator architecture that uses an FPGA-as-a-service paradigm to compute the Jaccard similarity between pairs of genomes in large datasets using sketches and hardware acceleration in the cloud. The algorithm can compute the similarity between all genome pairs in the dataset, or it can use a selection criterion to reduce the amount of computation when only genome pairs with a Jaccard coefficient above a user-supplied threshold are of interest. After building the sketches, our heterogeneous accelerator can compute more than 96 million Jaccard coefficients per second running on an AWS EC2 f1.2xlarge instance with a Xilinx XCVU9P FPGA, which is 58 times faster than a state-of-the art software implementation that exploits SIMD instructions and thread-level parallelism on a compute-optimized EC2 c5.9xlarge instance with 36 hardware threads. The accelerator also computes similarities 27 times faster than a straightforward GPU-accelerated implementation of the Jaccard coefficient using sketches, and 4 times faster than an optimized GPU implementation of our algorithm, both running on an EC2 g5.4xlarge instance tailored with an NVIDIA A10G GPU. Furthermore, using a Jaccard coefficient threshold of 0.8 reduces the execution time of similarity computation to approximately one third in the hardware-accelerated and parallel software implementations, compared to computing the complete similarity matrix.(C) 2022 Elsevier B.V. All rights reserved.

关键词： Hardware acceleration Cloud computing Field-programmable gate arrays streaming algorithms Sketches Genomics

来源：评论

学校读者我要写书评

暂无评论

Identifying Taxonomic Units in Metagenomic DNA Streams on Mobile Devices

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第2期20卷 1092-1103页

作者： Zheng, Vicky Sariyuce, Ahmet Erdem Zola, Jaroslaw Univ Buffalo Dept Comp Sci Buffalo NY 14260 USA

With the emergence of portable DNA sequencers, such as Oxford Nanopore Technology MinION, metagenomic DNA sequencing can be performed in real-time and directly in the field. However, because metagenomic DNA analysis tasks, e.g., classification, taxonomic units assignment, etc., are compute and memory intensive, and the available methods are designed for batch processing, the current metagenomic tools are not well suited for mobile devices. In this work, we propose a new memory-efficient approach to identify Operational Taxonomic Units (OTUs) in metagenomic DNA streams on mobile devices. Our method is based on finding connected components in overlap graphs constructed over a real-time stream of long DNA reads as produced by the MinION platform. We propose an efficient algorithm to maintain connected components when an overlap graph is streamed and show how redundant information can be removed from the stream by transitive closures. We also propose how our algorithms can be integrated into a larger DNA analysis pipeline tailored for mobile computing. Through experiments on simulated and real-world metagenomic data, executed on the actual mobile device, we demonstrate that our resulting solution is able to recover OTUs with high precision. Our experiments also demonstrate the compounding benefits of introducing feedback loops in the DNA analysis pipeline.

关键词： Connected components metagenomics nanopore sequencing streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Cloud Computing’s Effect on Video Games streaming 2

Cloud Computing’s Effect on Video Games Streaming

引用

2nd International Conference on Automation, Computing and Renewable Systems, ICACRS 2023

作者： Komathi, A. Lenin, J. Asha, S. Suresh, A. Suguna, M. Srinivasan, C. Department of Computer Science Nadar Saraswathi College of Arts and Science College Tamilnadu Theni India Department of ComputerScience and Engineering Alliance College of Engineering and Design Alliance University Karnataka Bengaluru India Department of Information Technology S.A. Engineering College Tamil Nadu Chennai India Department of Computer Science and Engineering Siddharth Institute of Engineering & Technology Andhra Pradesh Puttur India Tamil Nadu Salem India Department of Computer Science and Engineering Saveetha School of Engineering Saveetha Institute of Medical and Technical Sciences Saveetha University Tamil Nadu Chennai India

ISBN: (纸本)9798350340235

The disruptive power of cloud computing is altering the gaming industry. Real-time gaming is now feasible because to advancements in streaming algorithms, further blurring the lines between the digital and physical worlds. Understanding the potential of Cloud computing to change the gaming industry is the emphasis which investigates the complicated relationship between numerous technologies. By using cutting-edge streaming protocols and techniques like Adaptive Bitrate streaming (ABS), buffering, caching, and compression, users may have uninterrupted, high-quality gaming experiences. The study's findings herald a new era of interactive entertainment and shed light on the transformative possibilities of these technologies. Asynchronous Bit-Rate (ABR) encoding, buffering, caching algorithms, video compression standards, and streaming protocols are just few of the numerous digital components that work together to provide uninterrupted data transmission. The rapid progress of ABR algorithms has made it possible to dynamically alter video quality to maximize the user experience across a broad variety of network scenarios. Buffering and caching algorithms play crucial roles by proactively managing data flow and storage to avoid disruptions in the streaming experience. © 2023 IEEE.

关键词： Autism buffering algorithms caching methods Cloud Computing Impact Interactive Entertainment Standards for video compression streaming algorithms streaming protocols Video Games

来源：评论

学校读者我要写书评

暂无评论

Least-Mean-Squares Coresets for Infinite Streams

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第9期35卷 8699-8712页

作者： Braverman, Vladimir Feldman, Dan Lang, Harry Rus, Daniela Statman, Adiel Johns Hopkins Univ Comp Sci Deprtment Baltimore MD 21218 USA Univ Haifa Comp Sci Dept Robot & Big Data Lab IL-349883 Haifa Israel MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Consider a stream of d-dimensional rows (points in R-d) arriving sequentially. An epsilon-coreset is a positively weighted subset that approximates their sum of squared distances to any linear subspace of R-d, up to a 1 +/- epsilon factor. Unlike other data summarizations, such a coreset: (1) can be used to minimize faster any optimization function that uses this sum, such as regularized or constrained regression, (2) preserves input sparsity;(3) easily interpretable;(4) avoids numerical errors;(5) applies to problems with constraints on the input, such as subspaces that are spanned by few input points. Our main result is the first algorithm that returns such an epsilon-coreset using finite and constant memory during the streaming, i.e., independent of n, the number of rows seen so far. The coreset consists of O(d log(2) d/epsilon(2)) weighted rows, which is nearly optimal according to existing lower bounds of Omega(d/epsilon(2)). We support our findings with experiments on theWikipedia dataset benchmarked against state-of-the-art algorithms.

关键词： Big data coresets optimization streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

QSketch: An Efficient Sketch for Weighted Cardinality Estimation in Streams 24

QSketch: An Efficient Sketch for Weighted Cardinality Estima...

引用

30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

作者： Qi, Yiyan Li, Rundong Wang, Pinghui Sun, Yufang Xing, Rui Int Digital Econ Acad IDEA Shenzhen Guangdong Peoples R China Xi An Jiao Tong Univ MOE KLINNS Lab Xian Peoples R China

ISBN: (纸本)9798400704901

Estimating cardinality, i.e., the number of distinct elements, of a data stream is a fundamental problem in areas like databases, computer networks, and information retrieval. This study delves into a broader scenario where each element carries a positive weight. Unlike traditional cardinality estimation, limited research exists on weighted cardinality, with current methods requiring substantial memory and computational resources, challenging for devices with limited capabilities and real-time applications like anomaly detection. To address these issues, we propose QSketch, a memory-efficient sketch method for estimating weighted cardinality in streams. QSketch uses a quantization technique to condense continuous variables into a compact set of integer variables, with each variable requiring only 8 bits, making it 8 times smaller than previous methods. Furthermore, we leverage dynamic properties during QSketch generation to significantly enhance estimation accuracy and achieve a lower time complexity of O(1) for updating estimations upon encountering a new element. Experimental results on synthetic and real-world datasets show that QSketch is approximately 30% more accurate and two orders of magnitude faster than the state-of-the-art, using only 1/8 of the memory.

关键词： streaming algorithms Sketch Weighted Cardinality Estimation

来源：评论

学校读者我要写书评

暂无评论

The Quantum and Classical streaming Complexity of Quantum and Classical Max-Cut 63

The Quantum and Classical Streaming Complexity of Quantum an...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Kallaugher, John Parekh, Ojas Sandia Natl Labs POB 5800 Albuquerque NM 87185 USA

ISBN: (纸本)9781665455190

We investigate the space complexity of two graph streaming problems: MAX-CUT and its quantum analogue, QUANTUM MAX-CUT. Previous work by Kapralov and Krachun [STOC '19] resolved the classical complexity of the classical problem, showing that any (2 - epsilon)-approximation requires Omega(n) space (a 2-approximation is trivial with O(log n) space). We generalize both of these qualifiers, demonstrating Omega(n) space lower bounds for (2-epsilon)-approximatingMAX-CUT and QUANTUM MAX-CUT, even if the algorithm is allowed to maintain a quantum state. As the trivial approximation algorithm for QUANTUM MAX-CUT only gives a 4-approximation, we show tightness with an algorithm that returns a (2 + epsilon)-approximation to the QUANTUM MAX-CUT value of a graph in O(log n) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using o(n) space. We prove our lower bounds through the techniques of Boolean Fourier analysis. We give the first application of these methods to sequential one-way quantum communication, in which each player receives a quantum message from the previous player, and can then perform arbitrary quantum operations on it before sending it to the next. To this end, we show how Fourier-analytic techniques may be used to understand the application of a quantum channel.

关键词： quantum algorithms graph algorithms streaming algorithms fourier analysis

来源：评论

学校读者我要写书评

暂无评论

streaming Facility Location in High Dimension via Geometric Hashing 63

Streaming Facility Location in High Dimension via Geometric ...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Czumaj, Artur Jiang, Shaofeng H-C Krauthgamer, Robert Vesely, Pavel Yang, Mingwei Univ Warwick Coventry W Midlands England Peking Univ Beijing Peoples R China Weizmann Inst Sci Rehovot Israel Charles Univ Prague Prague Czech Republic

ISBN: (纸本)9781665455190

In Euclidean Uniform Facility Location, the input is a set of clients in R-d and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid {1,...,Delta}(d), and we focus on the high-dimensional regime, where the algorithm's space complexity must be polynomial (and certainly not exponential) in d center dot log Delta. We present a new algorithmic framework, based on importance sampling from the stream, for O(1)-approximation of the optimal cost using only poly(d center dot log Delta) space. This framework is easy to implement in two passes, one for sampling points and the other for estimating their contribution. Over random-order streams, we can extend this to a one-pass algorithm by using the two halves of the stream separately. Our main result, for arbitrary-order streams, computes O(d(1.5))-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee O(d center dot log(2) Delta)-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the O(log Delta)-factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by employing a geometric hashing scheme that maps points in R-d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly(d) distinct buckets. Finally, we complement our results with a proof that every streaming 1.085-approximation algorithm requires space exponential in poly(d center dot log Delta), even for insertion-only streams.

关键词： sublinear algorithms facility location streaming algorithms hash functions high dimension

来源：评论

学校读者我要写书评

暂无评论

Brooks' Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for Δ-Coloring 2022

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streami...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Assadi, Sepehr Kumar, Pankaj Mittal, Parth Rutgers State Univ Piscataway NJ 08854 USA Charles Univ Prague Prague Czech Republic

ISBN: (纸本)9781450392648

Every graph with maximum degree. can be colored with (Delta + 1) colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model: there exists a randomized algorithm that with high probability finds a (Delta + 1)-coloring of the input graph in only O (n center dot polylog n) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs (Delta + 1) colors to properly color a graph. Indeed, the celebrated Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with Delta colors. Can we find a.-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not.-colorable or outputs a Delta-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for Delta-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in o (n(2)) time we prove that neither of these tasks is possible for Delta-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to Delta-coloring. We then build on these insights to design a semi-streaming algorithm that uses (i) a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input-the ones that form the basis of our impossibility results-and (ii) a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of in

关键词： streaming algorithms graph coloring brooks' theorem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：