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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Almost Chor-Goldreich Sources and Adversarial Random Walks 2023

Almost Chor-Goldreich Sources and Adversarial Random Walks

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Doron, Dean Moshkovitz, Dana Oh, Justin Zuckerman, David Ben Gurion Univ Negev Beer Sheva Israel Univ Texas Austin Austin TX USA

ISBN: (纸本)9781450399135

A Chor-Goldreich (CG) source is a sequence of random variables Chi = Chi(1) ..... -Chi(t), where each Chi(i) similar to {0, 1}(d) and Chi(i) has delta d min-entropy conditioned on any fixing of Chi = Chi(1) ..... -Chi(i-1). The parameter 0 < delta <= 1 is the entropy rate of the source. We typically think of 3 as constant and C as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Chi(i) to only have conditional Shannon entropy delta d. We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha-Vazirani sources: We construct a deterministic condenser that on input -, outputs a distribution which is close to having constant entropy gap, namely a distribution Z similar to {0, 1}(m) for m approximate to delta dt with min-entropy m-O(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a "one-shot" simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to Chi = Chi(1) ..... -Chi(t),, accumulate most of the entropy in Chi

关键词： condensers expander Graphs extractors random Walks randomized algorithm Santha-Vazirani sources

来源：评论

学校读者我要写书评

暂无评论

Quick Detection of High-degree Entities in Large Directed Networks 14

Quick Detection of High-degree Entities in Large Directed Ne...

引用

14th IEEE International Conference on Data Mining (IEEE ICDM)

作者： Avrachenkov, K. Litvak, N. Prokhorenkova, L. Ostroumova Suyargulova, E. Inria Rocquencourt France Univ Twente NL-7500 AE Enschede Netherlands Yandex Moscow Russia

ISBN: (纸本)9781479943036

In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collect and update statistics about popular entities, usually using the degree of an entity as an approximation of its popularity. We suggest a simple, efficient, and easy to implement two-stage randomized algorithm that provides highly accurate solutions to this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-00 most followed users, with more than 90% precision, in the online social network Twitter with approximately a billion of registered users. Our algorithm significantly outperforms existing methods and serves many different purposes such as finding the most popular users or the most popular interest groups in social networks. An important contribution of this work is the analysis of the proposed algorithm using Extreme Value Theory - a branch of probability that studies extreme events and properties of largest order statistics in random samples. Using this theory we derive an accurate prediction for the algorithm's performance and show that the number of API requests for finding the top-k most popular entities is sublinear in the number of entities. Moreover, we formally show that the high variability of the entities, expressed through heavy-tailed distributions, is the reason for the algorithm's efficiency. We quantify this phenomenon in a rigorous mathematical way.

关键词： application program interfaces randomised algorithms social networking (online) API requests approximation extreme value theory high-degree entities large directed networks online social network Twitter online social networks quick detection randomized algorithm statistics top-k most popular entities algorithm design and analysis Approximation algorithms Indexes Peer-to-peer computing Prediction algorithms Twitter social networks sublinear complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：