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

8th Annual International Conference on Computational Biology (RECOMB)

作者： Bailey-Kellogg, C Chainraj, S Pandurangan, G Dartmouth Coll Dept Comp Sci Sudikoff Lab 6211 Hanover NH 03755 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)9781581137552

Nuclear magnetic resonance (NMR) spectroscopy allows scientists to study protein structure, dynamics and interactions in solution. A necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. Automated resonance assignment algorithms rely on information regarding connectivity ( e. g., through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. Significant ambiguity exists in both connectivity and amino acid type information. This paper focuses on the information content available in connectivity alone and develops a novel random-graph theoretic framework and algorithm for connectivity-driven NMR sequential assignment. Our random graph model captures the structure of chemical shift degeneracy, a key source of connectivity ambiguity. We then give a simple and natural randomized algorithm for finding optimal assignments as sets of connected fragments in NMR graphs. The algorithm naturally and efficiently reuses substrings while exploring connectivity choices;it overcomes local ambiguity by enforcing global consistency of all choices. By analyzing our algorithm under our random graph model, we show that it can provably tolerate relatively large ambiguity while still giving expected optimal performance in polynomial time. We present results from practical applications of the algorithm to experimental datasets from a variety of proteins and experimental set-ups. We demonstrate that our approach is able to overcome significant noise and local ambiguity in identifying significant fragments of sequential assignments.

关键词： nuclear magnetic resonance (NMR) spectroscopy automated sequential resonance assignment random graph model randomized algorithm Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

A Fill Estimation algorithm for Sparse Matrices and Tensors in Blocked Formats 32

A Fill Estimation Algorithm for Sparse Matrices and Tensors ...

引用

27th International Heterogeneity in Computing Workshop in conjunction with 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Ahrens, Willow Xu, Helen Schiefer, Nicholas MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781538643686

Many sparse matrices and tensors from a variety of applications, such as finite element methods and computational chemistry, have a natural aligned rectangular nonzero block structure. Researchers have designed high-performance blocked sparse operations which can take advantage of this sparsity structure to reduce the complexity of storing the locations of nonzeros. The performance of a blocked sparse operation depends on how well the block size reflects the structure of nonzeros in the tensor. Sparse tensor structure is generally unknown until runtime, so block size selection must be efficient. The fill is a quantity which, for some block size, relates the number of nonzero blocks to the number of nonzeros. Many performance models use the fill to help choose a block size. However, the fill is expensive to compute exactly. We present a sampling-based algorithm called PHIL to estimate the fill of sparse matrices and tensors in any format. We provide theoretical guarantees for sparse matrices and tensors, and experimental results for matrices. The existing state-of-the-art fill estimation algorithm, which we will call OSKI, runs in time linear in the number of elements in the tensor. The number of samples PHIL needs to compute a fill estimate is unrelated to the number of nonzeros and depends only on the order (number of dimensions) of the tensor, desired accuracy of the estimate, desired probability of achieving this accuracy, and number of considered block sizes. We compare PHIL and OSKI on a suite of 42 matrices. On most inputs, PHIL estimates the fill at least 2 times faster and often more than 20 times faster than OSKI. PHIL consistently produced accurate estimates-in all cases that we tested PHIL was faster and/or more accurate than OSKI. Finally, we find that PHIL and OSKI produce comparable speedups in multicore blocked sparse matrix-vector multiplication (SpMV) when the block size was chosen using fill estimates in a model due to Vuduc et al.

关键词： Fill Estimation Sparse Matrix Sparse Tensor Block Sparse Block Size Selection randomized algorithm Sampling algorithm Autotuning Performance Engineering Performance Model Numerical Linear Algebra Phil

来源：评论

学校读者我要写书评

暂无评论

Computation of probabilistic output admissible set for time-varying uncertain constrained system

Computation of probabilistic output admissible set for time-...

引用

SICE-ICASE International Joint Conference

作者： Hatanaka, Takeshi Takaba, Kiyotsugu Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan JSPS Tokyo Japan

ISBN: (纸本)9788995003848

This paper considers time-varying uncertain constrained systems, and develops a method for computing a probabilistic output admissible (POA) set which consists of initial states probabilistically assured to satisfy the infinitetime constraint. The algorithm for the time-invariant case has already been presented in Hatanaka and Takaba (2006). This paper shows how this algorithm is extended to the time-varying case when an upper bound of a number called future output admissibility (FOA) index is available. We moreover present two methods for computing an upper bound of the FOA index;probabilistic and deterministic methods.

关键词： constrained system uncertainty maximal output admissible set randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time 59

Approximating Edit Distance Within Constant Factor in Truly ...

引用

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

作者： Chakraborty, Diptarka Das, Debarati Goldenberg, Elazar Koucky, Michal Saks, Michael Charles Univ Prague Inst Comp Sci Malostranske Namesti 25 CR-11800 Prague 1 Czech Republic Acad Coll Tel Aviv Yaffo Sch Comp Sci Tel Aviv Israel Rutgers State Univ Dept Math Piscataway NJ USA

ISBN: (纸本)9781538642306

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running time (O) over tilde (n(2-2/7)) that approximates the edit distance within a constant factor.

关键词： Edit distance Approximation algorithm Sub-quadratic time algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

PHED: Pre-Handshaking Neighbor Discovery Protocols in Full Duplex Wireless Ad Hoc Networks

PHED: Pre-Handshaking Neighbor Discovery Protocols in Full D...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Sun, Guobao Wu, Fan Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Dept Comp Sci & Engn Shanghai 200030 Peoples R China

ISBN: (纸本)9781467309219;9781467309202

Neighbor Discovery (ND) is a basic and crucial step for initializing wireless ad hoc networks. A fast, precise, and energy-efficient ND protocol has significant importance to subsequent operations in wireless networks. However, many existing protocols have high probabilities to generate idle slots in their neighbor discovering processes, which extends the executing duration, and thus compromises their performance. In this paper, we propose a novel randomized protocol PHED, Pre-Handshaking Neighbor Discovery Protocol, to initialize synchronous full duplex wireless ad hoc networks. By introducing a pre-communication strategy to help each node be aware of activities of its neighborhood, we significantly reduce the probabilities of generating idle slots and collisions. Moreover, with the development of single channel full duplex communication technology [1, 2], we further decrease the processing time needed in PHED, and construct the first full duplex neighbor discovery protocol. Our theoretical analysis proves that PHED can increase the speed of ND by approximately 98% in comparison with the classical ALOHA-like protocols [3, 4]. In addition, we prove the effectiveness of PHED by simulations.

关键词： Wireless Ad Hoc Networks Neighbor Discovery Full Duplex Technology randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Enabling information confidentiality in publish/subscribe overlay services

Enabling information confidentiality in publish/subscribe ov...

引用

IEEE International Conference on Communications (ICC 2008)

作者： Zhang, Hui Sharma, Abhishek Chen, Haifeng Jiang, Guofei Meng, Xiaoqiao Yoshihira, Kenji NEC Labs Amer Princeton NJ USA Univ Southern Calif Los Angeles CA USA NEC Lab Amer Princeton NJ USA

ISBN: (纸本)9781424420742

"Alice has a piece of valuable information which she is willing to sell to anyone who is interested in;she is too busy and wants to ask Bob, a professional broker, to sell that information for her;but Alice is in a dilemma where she cannot trust Bob with that information but Bob cannot help her find her customers without knowing that information." In this paper, we propose a security mechanism called information foiling to address new confidentiality problems arising in pub/sub overlay services [1]. Information foiling extends Rivest's "Chaffing and Winnowing" [2], and its basic idea is to carefully generate a set of fake messages to hide an authentic message. Information foiling requires no modification inside the broker network so that the routing/filtering capabilities of broker nodes remains intact. We formally present the information foiling mechanism in the context of publish/subscribe overlay services, and discuss its applicability in other Internet applications. For publish/subscribe applications, we propose a suite of optimal schemes for fake message generation in different scenarios. Real-world data are used in our evaluation to demonstrate the effectiveness of the proposed schemes.

关键词： security confidentiality publish/subscribe randomized algorithm data privacy

来源：评论

学校读者我要写书评

暂无评论

randomized estimation of functional covariance operator via subsampling

引用

STAT 2020年第1期9卷

作者： He, Shiyuan Yan, Xiaomeng Renmin Univ China Inst Stat & Big Data 59 Zhongguancun St Beijing 100872 Peoples R China Texas A&M Univ Dept Stat College Stn TX 77843 USA

Covariance operators are fundamental concepts and modelling tools for many functional data analysis methods, such as functional principal component analysis. However, the empirical (or estimated) covariance operator becomes too costly to compute when the functional dataset gets big. This paper studies a randomized algorithm for covariance operator estimation. The algorithm works by sampling and rescaling observations from the large functional data collection to form a sketch of much smaller size and performs computation on the sketch to obtain the subsampled empirical covariance operator. The proposed algorithm is theoretically justified via nonasymptotic bounds between the subsampled and the full-sample empirical covariance operator in terms of the Hilbert-Schmidt norm and the operator norm. It is shown that the optimal sampling probability that minimizes the expected squared Hilbert-Schmidt norm of the subsampling error is determined by the norm of each function. Simulated and real data examples are used to illustrate the effectiveness of the proposed algorithm.

关键词： covariance operator functional data analysis randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Faster k-SAT algorithms using Biased-PPSZ 2019

Faster k-SAT Algorithms using Biased-PPSZ

引用

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

作者： Hansen, Thomas Dueholm Kaplan, Haim Zamir, Or Zwick, Uri Univ Copenhagen Copenhagen Denmark Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450367059

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k > 3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k >= 3. For k = 3 we also improve on Herli's result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308(n) to 1.307(n).

关键词： satisfiability randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

NearlyWork-Efficient Parallel algorithm for Digraph Reachability 2018

NearlyWork-Efficient Parallel Algorithm for Digraph Reachabi...

引用

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

作者： Fineman, Jeremy T. Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450355599

One of the simplest problems on directed graphs is that of identifying the set of vertices reachable from a designated source vertex. This problem can be solved easily sequentially by performing a graph search, but efficient parallel algorithms have eluded researchers for decades. For sparse high-diameter graphs in particular, there is no known work-efficient parallel algorithm with nontrivial parallelism. This amounts to one of the most fundamental open questions in parallel graph algorithms: Is there a parallel algorithm for digraph reachability with nearly linear work? This paper shows that the answer is yes. This paper presents a randomized parallel algorithm for digraph reachability and related problems with expected work (O) over tilde (m) and span (Omega) over tilde (n(2/3)), and hence parallelism (Omega) over tilde (m/n(2/3)) = (Omega) over tilde (n(1/3)), on any graph with n vertices and m arcs. This is the first parallel algorithm having both nearly linear work and strongly sublinear span, i.e., span (Omega) over tilde (n(1-epsilon)) for any constant epsilon > 0. The algorithm can be extended to produce a directed spanning tree, determine whether the graph is acyclic, topologically sort the strongly connected components of the graph, or produce a directed ear decomposition, all with work (O) over tilde (m) and span (O) over tilde (n(2/3)). The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of (O) over tilde (n) shortcuts, reduces the diameter of the graph to (Omega) over tilde (n(2/3)) with high probability. While both sequential and parallel algorithms are known with those combinatorial properties, even the sequential algorithms are not efficient, having sequential runtime (Omega) over tilde (m (1)). This paper presents a surprisingly simple sequential algorithm that achieves the stated diameter reduction and runs in O(m) time. Parallelizing that algorithm yields the main result, but doing so involves overcomi

关键词： Parallel algorithm randomized algorithm graph search reachability shortcuts

来源：评论

学校读者我要写书评

暂无评论

Maximization of k-Submodular Function with a Matroid Constraint 17th

Maximization of k-Submodular Function with a Matroid Constra...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Sun, Yunjing Liu, Yuezhu Li, Min Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

ISBN: (纸本)9783031203497;9783031203503

A k-submodular function is a promotion of a submodular function, whose domain is composed of k disjoint subsets rather than a single subset. In this paper, we give a deterministic algorithm for the non-monotone k-submodular function maximization problem subject to a matroid constraint with approximation factor 1/3. Based on this result, we give a randomized 1/3-approximation algorithm for the problem with faster running time, but the probability of success is (1- e). And we obtain that the complexity of deterministic algorithm and random algorithm is O(N vertical bar D vertical bar(p+ kq)) and O(vertical bar D vertical bar(p log N/epsilon(1) + kq log N/epsilon(2)) logN) respectively, where D is the ground set of the matroid constraint with rank N, p is times of oracle to calculate whether a set is an independent set in this matroid, q is the times of oracle to calculate a value of the k-submodular function, and epsilon, epsilon(1), epsilon(2) are positive parameters with e = max{epsilon(1), epsilon(2)}.

关键词： k-submodular function Matroid constraint Deterministic algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：