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

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

109 篇 会议
106 篇 期刊文献
2 篇 学位论文

馆藏范围

217 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

201 篇 工学
- 191 篇 计算机科学与技术...
- 39 篇 软件工程
- 35 篇 电气工程
- 7 篇 信息与通信工程
- 6 篇 控制科学与工程
- 1 篇 仪器科学与技术
- 1 篇 动力工程及工程热...
- 1 篇 电子科学与技术（可...
- 1 篇 石油与天然气工程
- 1 篇 环境科学与工程（可...
- 1 篇 生物医学工程（可授...
88 篇 理学
- 86 篇 数学
- 3 篇 物理学
- 3 篇 统计学（可授理学、...
- 2 篇 系统科学
- 1 篇 生物学
9 篇 管理学
- 9 篇 管理科学与工程(可...
1 篇 医学
- 1 篇 临床医学

主题

217 篇 streaming algori...
14 篇 approximation al...
12 篇 communication co...
11 篇 algorithms
9 篇 submodular maxim...
9 篇 heavy hitters
8 篇 clustering
8 篇 theory
8 篇 online algorithm...
8 篇 lower bounds
8 篇 randomized algor...
6 篇 graph partitioni...
6 篇 graph algorithms
6 篇 sketches
6 篇 data streams
6 篇 sampling
5 篇 distinct element...
5 篇 triangle countin...
5 篇 set cover
5 篇 quantiles

机构

10 篇 carnegie mellon ...
5 篇 charles univ pra...
4 篇 mit cambridge ma...
4 篇 harvard univ sch...
4 篇 johns hopkins un...
4 篇 univ warwick cov...
3 篇 indian stat inst...
3 篇 univ nebraska li...
3 篇 univ penn philad...
3 篇 univ waterloo sc...
3 篇 xi an jiao tong ...
3 篇 tel aviv univ te...
3 篇 natl univ singap...
3 篇 univ penn dept c...
2 篇 weizmann inst sc...
2 篇 alan turing inst...
2 篇 georgetown univ ...
2 篇 peking univ peop...
2 篇 univ michigan an...
2 篇 sandia natl labs...

作者

12 篇 woodruff david p...
9 篇 braverman vladim...
9 篇 cormode graham
7 篇 vesely pavel
7 篇 zhou samson
6 篇 assadi sepehr
6 篇 khanna sanjeev
6 篇 velusamy santhos...
5 篇 sudan madhu
5 篇 wang pinghui
5 篇 chou chi-ning
4 篇 golovnev alexand...
4 篇 meel kuldeep s.
4 篇 czumaj artur
4 篇 bender michael a...
4 篇 farach-colton ma...
4 篇 vinodchandran n....
4 篇 indyk piotr
4 篇 guan xiaohong
4 篇 hernandez cecili...

语言

214 篇 英文
2 篇 其他
1 篇 中文

检索条件"主题词=Streaming algorithms"

共 217 条记录，以下是61-70 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

Estimating the Size of Union of Sets in streaming Models 21

Estimating the Size of Union of Sets in Streaming Models

引用

40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Meel, Kuldeep S. Vinodchandran, N. V. Chakraborty, Sourav Natl Univ Singapore Singapore Singapore Univ Nebraska Lincoln NE USA Indian Stat Inst Kolkata India

ISBN: (纸本)9781450383813

In this paper we study the problem of estimating the size of the union of sets S-1, ..., S-M where each set S-i subset of Omega (for some discrete universe Omega) is implicitly presented and comes in a streaming fashion. We define the notion of Delphic sets to capture class of streaming problems where membership, sampling, and counting calls to the sets are efficient. In particular, we show our notion of Delphic sets capture three well known problems: Klee's measure problem (discrete version), test coverage estimation, and model counting of DNF formulas. The Klee's measure problem corresponds to computation of volume of multi-dimension axis aligned rectangles, i.e., every d-dimension axis-aligned rectangle can be defined as [a(1), b(1)]x[a(2), b(2)]x ... x [a(d), b(d)]. The problem of test coverage estimation focuses on the computation of coverage measure for a given testing array in the context of combinatorial testing, which is a fundamental technique in the context of hardware and software testing. Finally, given a DNF formula phi = T-1 boolean OR T-2 boolean OR ... boolean OR T-M, the problem of model counting seeks to compute the number of satisfying assignments of phi. The primary contribution of our work is a simple and efficient sampling-based algorithm, called APS-Estimator, for estimating the of union of sets in streaming setting. Our algorithm has the space complexity of O(R log vertical bar Omega vertical bar) and update time is O(R log R . log(M/delta) . log vertical bar Omega vertical bar) where, R = O log(M/delta) . epsilon(2)). Consequently, our algorithm provides the first algorithm with linear dependence on d for Klee's measure problem in streaming setting for d > 1, thereby settling the open problem of Tirthpura and Woodruff (PODS-12). Furthermore, a straightforward application of our algorithm lends to an efficient algorithm for coverage estimation problem in streaming setting. We then investigate whether the space complexity for coverage estimat

关键词： streaming algorithms DNF counting Klee's Measure Problem

来源：评论

学校读者我要写书评

暂无评论

Optimal streaming Approximations for all Boolean Max-2CSPs and Max-kSAT 61

Optimal Streaming Approximations for all Boolean Max-2CSPs a...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chou, Chi-Ning Golovnev, Alexander Velusamy, Santhoshini Harvard Univ John A Paulson Sch Engn & Appl Sci Cambridge MA 02138 USA

ISBN: (纸本)9781728196213

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant alpha, s.t. for any epsilon > 0 (i) there is an (alpha - epsilon)-streaming approximation using space O(log n);and (ii) any (alpha + epsilon)-streaming approximation requires space Omega(root n). This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015;Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was 1/2. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DICUT problem, there was a gap between an upper bound of 1/2 and a lower bound of 2/5 [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DICUT is 4/9. We also establish that the tight approximation for Max-2SAT is root 2/2, and for Exact Max-2SAT it is 3/4. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for Max-kSAT is root 2/2 for every k >= 2.

关键词： streaming algorithms Approximation algorithms Constraint Satisfaction

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Single-Pass streaming Complexity of the Set Cover Problem 16

Tight Bounds for Single-Pass Streaming Complexity of the Set...

引用

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

作者： Assadi, Sepehr Khanna, Sanjeev Li, Yang Univ Penn Dept Comp & Informat Sci 200 S 33Rd St Philadelphia PA 19104 USA

ISBN: (纸本)9781450341325

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an alpha-approximate set cover (for alpha = o(root n)) via a single-pass streaming algorithm, we show that Theta(mn/alpha) space is both sufficient and necessary (up to an O(log n) factor);here m denotes number of the sets and n denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk et al. (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of alpha saving in the space is achievable in this case and that this is the best possible. In other words, we show that Theta(mn/alpha(2)) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of alpha. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.

关键词： streaming algorithms communication complexity set cover covering integer programs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Space Efficient streaming Algorithm for Triangle Counting using the Birthday Paradox 13

A Space Efficient Streaming Algorithm for Triangle Counting ...

引用

19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Jha, Madhav Seshadhri, C. Pinar, Ali Penn State Univ State Coll PA 16801 USA Sandia Natl Labs Livermore CA USA

ISBN: (纸本)9781450321747

We design a space efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (coilmion properties for social networks), we can prove that our algorithm requires 0(0-i) space (n is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges] our algorithm stores just 60.000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity/number of triangles of a graph, by storing a miniscule fraction of edges.

关键词： streaming algorithms Triangle counting

来源：评论

学校读者我要写书评

暂无评论

streaming Submodular Maximization Under Differential Privacy Noise 15th

Streaming Submodular Maximization Under Differential Privacy...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Xiao, Di Guo, Longkun Liao, Kewen Yao, Pei Fuzhou Univ Fuzhou Peoples R China Australian Catholic Univ Sydney NSW Australia

ISBN: (纸本)9783030926816;9783030926809

The era of big data has brought the need of fast data stream analysis. Recently the problem of streaming submodular optimization has attracted much attention due to the importance of both submodular functions and streaming analytics. However, in real practical setting, streaming data often comes with noise which causes difficulties in analysing and optimizing submodular functions. In this paper, we study the problem of submodular maximization with cardinality constraint under a noisy streaming model, where the impact of noise is assumed to be small as inspired by the framework of differential privacy (so we also call it DP noise). For this problem, we eventually give a worst-case approximation ratio of 1/(2+(1+1/k)(2))(1+1/k) - delta in one pass. To complement the theoretical analysis, we also conduct experiments across real datasets to show our algorithm outperforms the baseline streaming methods.

关键词： Submodular maximization streaming algorithms Differential privacy noise

来源：评论

学校读者我要写书评

暂无评论

streaming Tetrahedral Mesh Optimization 08

Streaming Tetrahedral Mesh Optimization

引用

ACM Solid and Physical Modeling Symposium (ACM SPM 2008)

作者： Xia, Tian Shaffer, Eric Univ Illinois Chicago IL 60680 USA

ISBN: (纸本)9781605581064

Improving the quality of tetrahedral meshes is an important operation in many scientific computing applications. Meshes with badly shaped elements impact both the accuracy and convergence of scientific applications. State-of-the-art mesh improvement techniques rely on sophisticated numerical optimization methods such as feasible Newton or conjugate gradient. Unfortunately, these methods cannot be practically applied to very large meshes due to their global nature. Our contribution in this paper is to describe a streaming framework for tetrahedral mesh optimization. This framework enables the optimization of meshes an order of magnitude larger than previously feasible, effectively optimizing meshes too large to fit in memory. Our results show that streaming is typically faster than global optimization and results in comparable mesh quality. This leads us to conclude that streaming extends mesh optimization to a new class of mesh sizes without compromising the quality of the optimized mesh.

关键词： Computational geometry and object modeling out-of-core algorithms streaming algorithms mesh smoothing large meshes tetrahedral meshes

来源：评论

学校读者我要写书评

暂无评论

Barcodes of Towers and a streaming Algorithm for Persistent Homology 33

Barcodes of Towers and a Streaming Algorithm for Persistent ...

引用

33rd International Symposium on Computational Geometry (SoCG) held as Part of Computational Geometry Week (CG Week)

作者： Kerber, Michael Schreiber, Hannah Graz Univ Technol Kopernikusgasse 24 A-8010 Graz Austria

ISBN: (纸本)9783959770385

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG, 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.

关键词： Persistent homology Topological data analysis Matrix reduction streaming algorithms Simplicial approximation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共22页 << < 3 4 5 6 7 8 9 10 11 12 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：