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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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 条记录，以下是151-160 订阅

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

详细简洁

排序：

Near Optimal Linear Algebra in the Online and Sliding Window Models 61

Near Optimal Linear Algebra in the Online and Sliding Window...

引用

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

作者： Braverman, Vladimir Drineas, Petros Musco, Cameron Musco, Christopher Upadhyay, Jalaj Woodruff, David P. Zhou, Samson Johns Hopkins Univ Baltimore MD 21218 USA Purdue Univ W Lafayette IN 47907 USA Univ Massachusetts Amherst Amherst MA USA NYU New York NY 10003 USA Apple Cupertino CA USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781728196213

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent W updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow elements from the smooth histogram framework (Braverman and Ostrovsky, FOCS 2007), we show that many interesting linear-algebraic problems, including spectral and vector induced matrix norms, generalized regression, and low-rank approximation, are not amenable to this approach in the row-arrival model. To overcome this challenge, we first introduce a unified row-sampling based framework that gives randomized algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and l(1)-subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime. Our algorithms are based on "reverse online" versions of offline sampling distributions such as (ridge) leverage scores, l(1) sensitivities, and Lewis weights to quantify both the importance and the recency of a row;our structural results on these distributions may be of independent interest for future algorithmic design. Although our techniques initially address numerical linear algebra in the sliding window model, our row-sampling framework rather surprisingly implies connections to the well-studied online model;our structural results also give the first sample optimal (up to lower order terms) online algorithm for low-rank approximation/projection-cost preservation. Using this powerful primitive, we give online algorithms for column/row subset selection and principal component analysis that resolves the main open question of Bhaskara et al. (FOCS 2019). We also give the first online algorithm for l(1)-subspace embeddings. We further formalize the connection between the online model and the sliding window model by introducing an additional unified framework for deterministic algorithms using a merge and r

关键词： streaming algorithms online algorithms sliding window model numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization 64

Derandomization vs Refutation: A Unified Framework for Chara...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Chen, Lijie Tell, Roei Williams, Ryan Univ Calif Berkeley Miller Inst Bas Res Sci Berkeley CA 94720 USA Univ Toronto Dept Comp Sci Toronto ON Canada MIT EECS Cambridge MA 02139 USA

ISBN: (纸本)9798350318944

We establish an equivalence between two algorithmic tasks: derandomization, the deterministic simulation of probabilistic algorithms;and refutation, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function. We prove that refuting low-space probabilistic streaming algorithms which attempt to compute functions f is an element of FP is equivalent to proving that prBPP = prP, even in cases where a lower bound for f against such streaming algorithms (without a refuter) is already unconditionally known. We also demonstrate the generality of our connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i.e., T C-0). Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, the refuter framework allows to directly compare several recent works to each other and to our work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to T C-0.

关键词： Refuters derandomization streaming algorithms threshold circuits

来源：评论

学校读者我要写书评

暂无评论

Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams 1

引用

3rd International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Braverman, Vladimir Lang, Harry Levin, Keith Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Johns Hopkins Univ Dept Math Baltimore MD 21218 USA

ISBN: (数字)9783319530079

ISBN: (纸本)9783319530062;9783319530079

We present a low-constant approximation for metric k median on an insertion-only stream of n points using 0O(epsilon(-3)k log n) space. In particular, we present a streaming (0(epsilon(-3)k log n), 2 + 6)-bicriterion solution that reports cluster weights. It is well-known that running an offline algorithm on this bicriterion solution yields a (17.66 + epsilon)-approximation. Previously, there have been two lines of research that trade off between space and accuracy in the streaming k-median problem. To date, the best-known (k, 6)-coreset construction requires O (epsilon(-2) k log(4) n) space [8], while the best-known 0 (k log n)-space algorithm provides only a (0 (k log n), 1063)-bicriterion [3]. Our work narrows this gap significantly, matching the best-known space while significantly improving the accuracy from 1063 to 2 + epsilon. We also provide a matching lower bound, showing that any polylog(n)-space streaming algorithm that maintains an (alpha, beta)-bicriterion must have beta >= 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By a storing an accurate summary of recent segments and a lower-space summary of older segments, our algorithm maintains a (0(epsilon(-3) k log n), 2 + epsilon)-bicriterion solution for the entire input.

关键词： streaming algorithms k-median Clustering

来源：评论

学校读者我要写书评

暂无评论

Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes 2019

Weak Lower Bounds on Resource-Bounded Compression Imply Stro...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： McKay, Dylan M. Murray, Cody D. Williams, R. Ryan MIT CSAIL Cambridge MA 02139 USA MIT EECS Cambridge MA 02139 USA

ISBN: (纸本)9781450367059

The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem whose NP-hardness remains open. Recently, Oliveira and Santhanam [FOCS 2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a "hardness magnification" phenomenon for MCSP in restricted settings. Letting MCSP[s(n)] be the problem of deciding if a truth table of length 2(n) has circuit complexity at most s(n), they proved that small (fixed-polynomial) average case circuit/formula lower bounds for MCSP[2(root n)], or lower bounds for approximating MCSP[2(o(n))], would imply major separations such as NP not subset of BPP and NP not subset of P/poly. We strengthen these results in several directions, obtaining magnification results from worst-case lower bounds on exactly computing the search version of generalizations of MCSP[s(n)], which also extend to time -bounded Kolmogorov complexity. In particular, we show that search-MCSP[s(n)] (where we must output a s(n)-size circuit when it exists) admits extremely efficient AC(0) circuits and streaming algorithms using Sigma(3)SAT oracle gates of small fan-in (related to the size s(n) we want to test). For A : {0, 1}* -> {0,1}, let search-MCSPA[s(n)] be the problem: Given a truth table T of size N = 2(n), output a Boolean circuit for T of size at most s(n) with AND, OR, NOT, and A-oracle gates (or report that no such circuit exists). Some consequences of our results are: (1) For reasonable s(n) >= n and A is an element of PH, if search-MCSPA[s(n)] does not have a 1 -pass deterministic poly(s(n))-space streaming algorithm with poly(s(n)) update time, then P # NP. For example, proving that it is impossible to synthesize SAT-oracle circuits of size 2(n/log n) with a streaming algorithm on truth tables of length N = 2(n) using N-epsilon update time and N-epsilon space on length-N inputs (for some epsilon > 0) would already separate P and NP. Not

关键词： hardness magnification minimum circuit size problem Kolmogorov complexity streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Quancurrent: A Concurrent Quantiles Sketch 23

Quancurrent: A Concurrent Quantiles Sketch

引用

35th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Zada, Shaked Elias Rinberg, Arik Keidar, Idit Technion Haifa Israel

ISBN: (纸本)9781450395458

Sketches are a family of streaming algorithms widely used in the world of big data to perform fast, real-time analytics. A popular sketch type is Quantiles, which estimates the data distribution of a large input stream. We present Quancurrent, a highly scalable concurrent Quantiles sketch. Quancurrent's throughput increases linearly with the number of available threads, and with 32 threads, it reaches an update speedup of 12x and a query speedup of 30x over a sequential sketch. Quancurrent allows queries to occur concurrently with updates and achieves an order of magnitude better query freshness than existing scalable solutions.

关键词： big data streaming algorithms sketches quantiles real-time analysis concurrency

来源：评论

学校读者我要写书评

暂无评论

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

引用

24th Annual Symposium on Theoretical Aspects of Computer Science

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Applicat Coventry CV4 7AL W Midlands England TU Dortmund Dept Comp Sci D-44221 Dortmund Germany

ISBN: (纸本)9783540709176

The min-sum k-clustering problem is to partition a metric space ( P, d) into k clusters C-1,..., C-k subset of P such that Sigma(k)(i=1) Sigma(p,q is an element of Ci) d(p, q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results. The first result is a sublinear-time ( 4 + epsilon)-approximation algorithm for the minsum k-clustering problem in metric spaces. The running time of this algorithm is O( n) for any constant k and epsilon, and it is o( n2) for all k = o( log n/ log log n). Since the full description size of the input is Theta(n(2)), this is sublinear in the input size. The fastest previously known o( log n)-factor approximation algorithm for k > 2 achieved a running time of Omega(nk), and no non-trivial o(n(2))-time algorithm was known before. Our second result is the first pass-efficient data streaming algorithm for min-sum k-clustering in the distance oracle model, i.e., an algorithm that uses poly( log n, k) space and makes 2 passes over the input point set, which arrives in form of a data stream in arbitrary order. It computes an implicit representation of a clustering of ( P, d) with cost at most a constant factor larger than that of an optimal partition. Using one further pass, we can assign each point to its corresponding cluster. To develop the coresets, we introduce the concept of alpha-preserving metric embeddings. Such an embedding satisfies properties that the distance between any pair of points does not decrease and the cost of an optimal solution for the considered problem on input ( P, d')is within a constant factor of the optimal solution on input ( P, d). In other words, the goal is to find a metric embedding into a ( structurally simpler) metric space that approximates the original metric up to a factor of a with respect to a given problem. We believe that this con

关键词： Sublinear-time algorithms Sublinear-space algorithms Clustering Min-sum k-clustering Balanced k-median streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance 11

K-Median Clustering, Model-Based Compressive Sensing, and Sp...

引用

43rd ACM Symposium on Theory of Computing

作者： Indyk, Piotr Price, Eric MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450306911

We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m = O(k log(n/k)) and a 1 + epsilon approximation factor, which matches the best achievable bound for other error measures, such as the l(1) norm. Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems.

关键词： Compressive sensing Earth Mover Distance streaming algorithms Clustering

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Clustering in Graph Streams: Single-Pass algorithms and Space Lower Bounds 35

Hierarchical Clustering in Graph Streams: Single-Pass Algori...

引用

35th Conference on Learning Theory (COLT)

作者： Assadi, Sepehr Chatziafratis, Vaggos Lacki, Jakub Mirrokni, Vahab Wang, Chen Rutgers State Univ Piscataway NJ 08854 USA Univ Calif Santa Cruz Santa Cruz CA 95064 USA Google Res New York NY USA

The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the problem in the streaming model, in which the memory is heavily limited and only a single or very few passes over the input are allowed. Specifically, we investigate whether a good hierarchical clustering can be obtained, or at least whether we can approximately estimate the value of the optimal hierarchy. To measure the quality of a hierarchy, we use the HC minimization objective introduced by Dasgupta Dasgupta (2016). Assuming that the input is an n-vertex weighted graph whose edges arrive in a stream, we derive the following results on space-vs-accuracy tradeoffs: . With O(n center dot polylog n) space, we develop a single-pass algorithm, whose approximation ratio matches the currently best offline algorithm Charikar and Chatziafratis (2017). . When the space is more limited, namely, n(1-o(1)), we prove that no algorithm can even estimate the value of the optimum hierarchical tree to within an o(log n/log log n) factor, even when allowed polylog n passes over the input and exponential time. . In the most stringent setting of polylog n space, studied extensively in the literature, we rule out algorithms that can even distinguish between "highly"-vs-"poorly" clusterable graphs, namely, graphs that have an n(1/2-o(1)) factor gap between their HC objective value. . Finally, we prove that any single-pass streaming algorithm that computes an optimal HC clustering requires storing almost the entire input even if allowed exponential time. Our algorithmic results establish a general structural result that proves that cut sparsifiers of input graphs can preserve the cost of "balanced" hierarchical trees to within a constant factor, and thus can be used in place of the original (dense) graphs when solving HC. Our lower bound results include a new streaming lower bound for a novel problem "One-vs-Man

关键词： Hierarchical Clustering streaming algorithms Sublinear Memory Dasgupta's Objective Lower Bounds Communication Complexity

来源：评论

学校读者我要写书评

暂无评论

Finding Favourite Tuples on Data Streams with Provably Few Comparisons 23

Finding Favourite Tuples on Data Streams with Provably Few C...

引用

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

作者： Zhang, Guangyi Tatti, Nikolaj Gionis, Aristides Shenzhen Inst Comp Sci Shenzhen Peoples R China Univ Helsinki HIIT Helsinki Finland KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9798400701030

One of the most fundamental tasks in data science is to assist a user with unknown preferences in finding high-utility tuples within a large database. To accurately elicit the unknown user preferences, a widely-adopted way is by asking the user to compare pairs of tuples. In this paper, we study the problem of identifying one or more high-utility tuples by adaptively receiving user input on a minimum number of pairwise comparisons. We devise a single-pass streaming algorithm, which processes each tuple in the stream at most once, while ensuring that the memory size and the number of requested comparisons are in the worst case logarithmic in n, where n is the number of all tuples. An important variant of the problem, which can help to reduce human error in comparisons, is to allow users to declare ties when confronted with pairs of tuples of nearly equal utility. We show that the theoretical guarantees of our method can be maintained for this important problem variant. In addition, we show how to enhance existing pruning techniques in the literature by leveraging powerful tools from mathematical programming. Finally, we systematically evaluate all proposed algorithms over both synthetic and real-life datasets, examine their scalability, and demonstrate their superior performance over existing methods.

关键词： preference learning user interaction streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Volume and Irregularity Effects on Massively Multicore Packet Processors 18

Volume and Irregularity Effects on Massively Multicore Packe...

引用

18th Asia-Pacific Network Operations and Management Symposium (APNOMS)

作者： Zhanikeev, Marat Tokyo Univ Sci Sch Management Chiyoda Ku Fujimi 1-11-2 Tokyo 1020071 Japan

ISBN: (纸本)9784885523045

Irregularity is a recognized problem on many-and multi-core platforms but its effect remains to be studied. This paper focuses on multicore processors and assumes that packet traffic is processed by a large number of parallel jobs in realtime, while each job is implemented as a streaming algorithm. Analysis is performed using a real-life measurement dataset collected especially for this study while irregular traffic is modeled using a hotspot distribution. Results show that massively multicore processors are affected by both the total input volume and the irregularity.

关键词： massively multicore irregularity heterogeneity streaming data streaming algorithms packet traffic

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共22页 << < 12 13 14 15 16 17 18 19 20 21 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：