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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

62 篇 会议
49 篇 期刊文献
5 篇 学位论文

馆藏范围

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

日期分布

学科分类号

105 篇 工学
- 98 篇 计算机科学与技术...
- 27 篇 软件工程
- 6 篇 电气工程
- 5 篇 控制科学与工程
- 1 篇 光学工程
- 1 篇 电子科学与技术（可...
- 1 篇 信息与通信工程
- 1 篇 生物工程
76 篇 理学
- 75 篇 数学
- 2 篇 统计学（可授理学、...
- 1 篇 物理学
- 1 篇 生物学
7 篇 管理学
- 7 篇 管理科学与工程(可...
2 篇 医学
- 2 篇 临床医学

主题

116 篇 sublinear algori...
33 篇 property testing
11 篇 approximation al...
9 篇 random walks
7 篇 graph algorithms
5 篇 local computatio...
5 篇 voting
5 篇 randomized algor...
4 篇 monotonicity
4 篇 embedding
4 篇 approximation
4 篇 distributed algo...
4 篇 pagerank
4 篇 sparse approxima...
4 篇 sketching
4 篇 edit distance
3 篇 local algorithms
3 篇 distribution tes...
3 篇 clustering
3 篇 computational co...

机构

6 篇 weizmann inst sc...
5 篇 mit csail cambri...
4 篇 ecole polytech f...
4 篇 tel aviv univ te...
3 篇 sandia natl labs...
3 篇 princeton univ p...
3 篇 univ michigan de...
3 篇 microsoft res re...
3 篇 mit cambridge ma...
3 篇 columbia univ de...
3 篇 carnegie mellon ...
3 篇 univ calif santa...
3 篇 columbia univ ny...
3 篇 univ penn philad...
3 篇 tel aviv univ il...
3 篇 natl univ singap...
3 篇 stanford univ st...
3 篇 pennstate univer...
3 篇 univ michigan de...
2 篇 weizmann institu...

作者

12 篇 seshadhri c.
7 篇 bressan marco
7 篇 ron dana
5 篇 woodruff david p...
5 篇 peserico enoch
5 篇 pretto luca
5 篇 raskhodnikova so...
4 篇 rubinfeld ronitt
4 篇 gilbert anna c.
3 篇 strauss martin j...
3 篇 rubinstein aviad
3 篇 kapralov michael
3 篇 andoni alexandr
3 篇 eden talya
3 篇 czumaj artur
3 篇 jahja irvan
3 篇 vardi shai
3 篇 talmon nimrod
3 篇 yu haifeng
3 篇 servedio rocco a...

语言

116 篇 英文

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

共 116 条记录，以下是81-90 订阅

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

详细简洁

排序：

Efficient and Near-Optimal algorithms for Sampling Connected Subgraphs 2021

Efficient and Near-Optimal Algorithms for Sampling Connected...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bressan, Marco Univ Statale Milano Dipartimento Informat Milan Italy

ISBN: (纸本)9781450380539

We study the graphlet sampling problem: given an integer k >= 3 and a graph G = (V, E), sample a connected induced k-node subgraph of G (also called k-graphlet) uniformly at random. This is a fundamental graph mining primitive, with applications in social network analysis and bioinformatics. The two state-of-the-art techniques are random walks and color coding. The random walk is elegant, but the current upper bounds and lower bounds on its mixing time suffer a gap of Delta(k-1) where A is the maximum degree of G. Color coding is better understood, but requires a 2(O)((k))m-time preprocessing over the entire graph. Moreover, no efficient algorithm is known for sampling graphlets uniformly - random walks and color coding yield only e-uniform samples. In this work, we provide the following results: (i) A near-optimal mixing time bound for the classic k-graphlet random walk, as a function of the mixing time of G. In particular, ignoring k(O(k)) factors, we show that the k-graphlet random walk mixes in (Theta) over tilde (t(G) . rho(G)(k-1)) steps, where t(G) is the mixing time of G and rho(G) is the ratio between its maximum and minimum degree, and on some graphs this is tight up to poly lg n factors. (ii) The first efficient algorithm for uniform graphlet sampling. The algorithm has a preprocessing phase that uses time O(nk(2) lg k + m) and space O(n), and a sampling phase that takes k(O(k)) lg Delta time per sample. It is based on ordering G in a simple way, so to virtually partition the graphlets into buckets, and then sampling from those buckets using rejection sampling. The algorithm can be used also for counting, with additive guarantees. (iii) A near-optimal algorithm for epsilon-uniform graphlet sampling, with a preprocessing phase that runs in time O(k(6)epsilon(-1)n( )lg n) and space O(n), and a sampling phase that takes k(O(k)) (1/3)(10) lg 1/epsilon expected time per sample. The algorithm is based on a nontrivial sketching of the ordering of G, followed by

关键词： subgraph sampling random walks sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Vision with Smart Pixels

Distributed Vision with Smart Pixels

引用

25th Annual Symposium on Computational Geometry

作者： Fekete, Sandor P. Fey, Dietmar Komann, Marcus Kroeller, Alexander Reichenbach, Marc Schmidt, Christiane Braunschweig Inst Technol Algorithms Grp Braunschweig Germany

ISBN: (纸本)9781605585017

We study a problem related to computer vision: flow can a field of sensors compute higher-level properties of observed objects deterministically in sublinear time, without accessing a central authority? This issue is not only important for real-time processing of images, but lies at the very heart of understanding how a brain may be able to function. In particular, we consider a quadratic field of n "smart pixels" on a video chip that observe a B/W image. Each pixel can exchange low-level information with its immediate neighbors. We show that it is possible to compute the centers of gravity along with a principal component analysis of all connected components of the black grid graph in time O(root n), by developing appropriate distributed protocols that are modeled after sweepline methods. Our method is not only interesting from a philosophical and theoretical point of view, it is also useful for actual applications for controling a robot arm that has to seize objects on a moving belt. We describe details of an implementation on an FPGA;the code has also been turned into a hardware design for an application-specific integrated circuit (ASIC).

关键词： distributed vision distributed algorithms sublinear algorithms principal component analysis sweepline algorithms

来源：评论

学校读者我要写书评

暂无评论

Property Testing for Bounded Degree Databases 35

Property Testing for Bounded Degree Databases

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Adler, Isolde Harwath, Frederik Univ Leeds Sch Comp Leeds W Yorkshire England Goethe Univ Inst Informat D-60054 Frankfurt Germany

ISBN: (纸本)9783959770620

Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.

关键词： Logic and Databases Property Testing Logical Meta-theorems Bounded Degree Model sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Separations and Equivalences between Turnstile Streaming and Linear Sketching 2020

Separations and Equivalences between Turnstile Streaming and...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Kallaugher, John Price, Eric Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781450369794

A longstanding observation, which was partially proven by Li, Nguyen, and Woodruff in 2014, and extended by Ai, Hu, Li, and Woodruff in 2016, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivially true). We study the relationship between turnstile streaming and linear sketching algorithms in more detail, giving both new separations and new equivalences between the two models. It was shown by Li, Nguyen, and Woodruff in 2014 that, if a turnstile algorithm works for arbitrarily long streams with arbitrarily large coordinates at intermediate stages of the stream, then the turnstile algorithm is equivalent to a linear sketch. We show separations of the opposite form: if either the stream length or the maximum value of the stream are substantially restricted, there exist problems where linear sketching is exponentially harder than turnstile streaming. A further limitation of the Li, Nguyen, and Woodruff equivalence is that the turnstile sketching algorithm is neither explicit nor uniform, but requires an exponentially long advice string. We show how to remove this limitation for deterministic streaming algorithms: we give an explicit small-space algorithm that takes the streaming algorithm and computes an equivalent module.

关键词： graph algorithms linear algebra streaming sketching big data sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

On Approximating the Stationary Distribution of Time-reversible Markov Chains 35

On Approximating the Stationary Distribution of Time-reversi...

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Sapienza Univ Roma Dipartimento Informat Rome Italy Univ Padua Dipartimento Ingn Informaz Padua Italy

ISBN: (纸本)9783959770620

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require (O) over tilde(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time T, and even the best available techniques still have complexity (O) over tilde (tau(1.5)/pi(v)(0.5));and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".

关键词： Markov Chains MCMC Sampling Large Graph algorithms Randomized algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust and Sample Optimal algorithms for PSD Low Rank Approximation 61

Robust and Sample Optimal Algorithms for PSD Low Rank Approx...

引用

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

作者： Bakshi, Ainesh Chepurko, Nadiia Woodruff, David P. CMU Pittsburgh PA 15213 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781728196213

Recently, Musco and Woodruff (FOCS, 2017) showed that given an nxn positive semidefinite (PSD) matrix A, it is possible to compute a (1 + epsilon)-approximate relative-error low-rank approximation to A by querying (O) over tilde (nk/epsilon(2.5)) entries of A in time (O) over tilde (nk/epsilon(2.5) + nk(omega-1)/epsilon(2(omega-1))). They also showed that any relative-error low-rank approximation algorithm must query Omega(nk/epsilon) entries of A, this gap has since remained open. Our main result is to resolve this question by obtaining an optimal algorithm that queries (O) over tilde (nk/epsilon) entries of A and outputs a relative-error low-rank approximation in (O) over tilde (n . (k/epsilon)(omega- 1)) time. Note, our running time improves that of Musco and Woodruff, and matches the information-theoretic lower bound if the matrix-multiplication exponent omega is 2. We then extend our techniques to negative-type distance matrices. Here, our input is a pair-wise distance matrix A corresponding to a point set P = {x(1), x(2), ..., x(n)} such that A(i, j) = parallel to x(i) - x(j)parallel to(2)(2). Bakshi and Woodruff (NeurIPS, 2018) showed a bi-criteria, relative-error low-rank approximation for negative-type metrics. Their algorithm queries (O) over tilde (nk/epsilon(2.5)) entries and outputs a rank-(k + 4) matrix. We show that the bi-criteria guarantee is not necessary and obtain an (O) over tilde (nk/epsilon) query algorithm, which is optimal. Our algorithm applies to all distance matrices that arise from metrics satisfying negative-type inequalities, including l(1), l(2), spherical metrics, hypermetrics and effective resistances on a graph. We also obtain faster algorithms for ridge regression. Next, we introduce a new robust low-rank approximation model which captures PSD matrices that have been corrupted with noise. We assume that the Frobenius norm of the corruption is bounded. Here, we relax the notion of approximation to additive-error, since it is inform

关键词： low rank approximation psd matrices regression sublinear algorithms randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Polylogarithmic Approximation for Edit Distance and the Asym...

引用

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

作者： Andoni, Alexandr Krauthgamer, Robert Onak, Krzysztof Princeton Univ CCI Princeton NJ 08544 USA

ISBN: (纸本)9780769542447

We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed epsilon > 0, the algorithm computes a (log n)(O(1/epsilon)) approximation in n(1+epsilon) time. This is an exponential improvement over the previously known approximation factor, 2((O) over tilde(root log n)), with a comparable running time [Ostrovsky and Rabani, J. ACM 2007;Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being "repetitive", which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance.

关键词： edit distance sampling query complexity linear-time algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating the Spectrum of a Graph 18

Approximating the Spectrum of a Graph

引用

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

作者： Cohen-Steiner, David Kong, Weihao Sohler, Christian Valiant, Gregory INRIA Sophia Antipolis Valbonne France Stanford Univ Dept Comp Sci Stanford CA 94305 USA TU Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9781450355520

The spectrum of a network or graph G = (V, E) with adjacency matrix A, consists of the eigenvalues of the normalized Laplacian L = I - D(-1/2)AD(-1/2). This set of eigenvalues encapsulates many aspects of the structure of the graph, including the extent to which the graph posses community structures at multiple scales. We study the problem of approximating the spectrum, lambda = (lambda(1), ... , lambda(vertical bar V vertical bar)), of G in the regime where the graph is too large to explicitly calculate the spectrum. We present a sublinear time algorithm that, given the ability to query a random node in the graph and select a random neighbor of a given node, computes a succinct representation of an approximation (lambda) over tilde = ((lambda) over tilde (1), ... , (lambda) over tilde (vertical bar V vertical bar)), such that parallel to(lambda) over tilde - lambda parallel to(1) <= epsilon vertical bar V vertical bar. Our algorithm has query complexity and running time exp(O(1/epsilon)), which is independent of the size of the graph, vertical bar V vertical bar. We demonstrate the practical viability of our algorithm on synthetically generated graphs, and on 15 different real-world graphs from the Stanford Large Network Dataset Collection, including social networks, academic collaboration graphs, and road networks. For the smallest of these graphs, we are able to validate the accuracy of our algorithm by explicitly calculating the true spectrum;for the larger graphs, such a calculation is computationally prohibitive. The spectra of these real-world networks reveal insights into the structural similarities and differences between them, illustrating the potential value of our algorithm for efficiently approximating the spectrum of large large networks.

关键词： Spectral graph theory sublinear algorithms random walks method of moments

来源：评论

学校读者我要写书评

暂无评论

Extrapolating the profile of a finite population 33

Extrapolating the profile of a finite population

引用

33rd Conference on Learning Theory (COLT)

作者： Jana, Soham Polyanskiy, Yury Wu, Yihong Yale Univ Dept Stat & Data Sci New Haven CT 06520 USA MIT Dept EECS 77 Massachusetts Ave Cambridge MA 02139 USA

We study a prototypical problem in empirical Bayes. Namely, consider a population consisting of k individuals each belonging to one of k types (some types can be empty). Without any structural restrictions, it is impossible to learn the composition of the full population having observed only a small (random) subsample of size m = o(k). Nevertheless, we show that in the sublinear regime of m = omega(k= log k), it is possible to consistently estimate in total variation the profile of the population, defined as the empirical distribution of the sizes of each type, which determines many symmetric properties of the population. We also prove that in the linear regime of m = ck for any constant c the optimal rate is Theta(1/log k). Our estimator is based on Wolfowitz's minimum distance method, which entails solving a linear program (LP) of size k. We show that there is a single infinite-dimensional LP whose value simultaneously characterizes the risk of the minimum distance estimator and certifies its minimax optimality. The sharp convergence rate is obtained by evaluating this LP using complex-analytic techniques.

关键词： High-dimensional statistics empirical Bayes sublinear algorithms minimax rate H-infinity-relaxation Laguerre polynomials

来源：评论

学校读者我要写书评

暂无评论

Estimating the longest increasing sequence in polylogarithmic time

Estimating the longest increasing sequence in polylogarithmi...

引用

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

作者： Saks, Michael Seshadhri, C. Rutgers State Univ Dept Math Piscataway NJ 08855 USA IBM Res Corp San Jose CA USA

ISBN: (纸本)9780769542447

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) time algorithms are known that determine the LIS exactly. In this paper, we develop a randomized approximation algorithm, that for any constant delta > 0, runs in time polylogarithmic in n and estimates the length of the LIS of an array up to an additive error of delta n. The algorithm presented in this extended abstract runs in time (log n)(O(1/delta)). In the full paper, we will give an improved version of the algorithm with running time (log n)(c)(1/delta)(O(1/delta)) where the exponent c is independent of delta. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2-approximation. Our techniques also yield a fast algorithm for estimating the distance to monotonicity to within a small multiplicative factor. The distance of f to monotonicity, epsilon(f), is equal to 1 - vertical bar LIS vertical bar/n (the fractional length of the complement of the LIS). For any delta > 0, we give an algorithm with running time O((epsilon(-1)(f) log n)(O(1/delta))) that outputs a (1 + delta)-multiplicative approximation to epsilon(f). This can be improved so that the exponent is a fixed constant. The previously known polylogarithmic algorithms gave only a 2-approximation.

关键词： sublinear algorithms Monotonicity Longest Increasing Subsequence Dynamic Programming

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：