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

IEEE International Symposium on Information Theory (ISIT)

作者： Falahatgar, Moein Jafarpour, Ashkan Orlitsky, Alon Pichapati, Venkatadheeraj Suresh, Ananda Theertha Univ Calif San Diego ECE La Jolla CA 92093 USA Yahoo La Jolla CA USA Univ Calif San Diego CSE La Jolla CA 92093 USA

ISBN: (纸本)9781509018062

Estimating the number of defective elements of a set has various biological applications including estimating the prevalence of a disease or disorder. Group testing has been shown to be more efficient than scrutinizing each element separately for defectiveness. In group testing, we query a subset of elements and the result of the query will be defective if the subset contains at least one defective element. We present an adaptive, randomized group-testing algorithm to estimate the number of defective elements with near-optimal number of queries. Our algorithm uses at most 2 log log d + O(1/delta(2) log 1/is an element of) queries and estimates the number of defective elements d up to a multiplicative factor of 1 +/- delta, with error probability <= is an element of. Also, we show an information-theoretic lower bound (1 - is an element of) log log d - 1 on the necessary number of queries any adaptive algorithm makes to estimate the number of defective elements for constant delta.

关键词： Group testing randomized algorithm Noisy binary search

来源：评论

学校读者我要写书评

暂无评论

A QoS-aware Task Allocation Model for Mobile Cloud Computing 2

A QoS-aware Task Allocation Model for Mobile Cloud Computing

引用

Second International Conference on Web Research (ICWR)

作者： Zarei, Mohammad Hossein Shirsavar, Milad Azizpour Yazdani, Nasser Univ Tehran Sch Elect & Comp Engn Router Lab Tehran Iran

ISBN: (纸本)9781509021666

Mobile Cloud Computing (MCC) tries to offload computation from mobile devices, including smartphones and tablets, to cloud providers to solve the limitations of mobile devices with the power of cloud computing. Providing cloud computing quality of service (QoS) in mobile devices is harder to achieve compared to fixed devices due to the limited computing resources, storage and energy in mobile devices. On the other hand, node mobility causes rapid changes in network topology. Tasks in cloud computing infrastructure are performed with different quality of service requirements. Using appropriate allocation of tasks to cloud computing resources, can improve QoS. In this paper, we formulate the task allocation problem as a minimum nonlinear optimization problem. A randomized algorithm is proposed in which the result is close to the optimal solution. It improves the QoS in mobile devices by choosing suitable cloud providers for a given user application. The results show that the proposed algorithm is faster and more scalable compared to optimal solution.

关键词： Mobile Cloud Computing Quality of Service Optimization Problem randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Generation of Communication Schedules for Multi-Mode Distributed Real-Time Applications

Generation of Communication Schedules for Multi-Mode Distrib...

引用

Design, Automation and Test in Europe Conference and Exhibition (DATE)

作者： Azim, Akramul Carvajal, Gonzalo Pellizzoni, Rodolfo Fischmeister, Sebastian Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9783981537024

A key problem in designing multi-mode real-time systems is the generation of schedules to reduce the complexities of transforming the model semantics to code. Moreover, distributed multi-mode applications are prone to suffer from delays incurred during mode changes. We therefore aim to generate communication schedules that have low average mode-change delay for multi-mode real-time distributed applications. In this paper, we use optimization constraints associated to timing requirements to generate state-based schedules for multi-mode communication systems, and illustrate the workflow for generating schedules from specifications through a real-time video monitoring case-study. Our experiments in the case-study demonstrate that schedules generated using the proposed method reduce the average mode-change delay in relation to a randomized algorithm and the well-known EDF scheduling algorithm.

关键词： bandwidth allocation delays processor scheduling randomised algorithms real-time systems video communication EDF scheduling algorithm average mode-change delay communication schedule generation earliest-deadline-first mode-change delay model semantics multimode communication systems multimode distributed real-time applications optimization constraints randomized algorithm real-time video monitoring state-based schedules Bandwidth Delays Real-time systems Schedules Streaming media Time division multiple access

来源：评论

学校读者我要写书评

暂无评论

Fruit-fly Inspired Neighborhood Encoding for Classification 21

Fruit-fly Inspired Neighborhood Encoding for Classification

引用

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

作者： Sinha, Kaushik Ram, Parikshit Wichita State Univ Wichita KS 67260 USA IBM Res AI New York NY USA

ISBN: (纸本)9781450383325

Inspired by the fruit-fly olfactory circuit, the Fly Bloom Filter [4] is able to efficiently summarize the data with a single pass and has been used for novelty detection. We propose a new classifier that effectively encodes the different local neighborhoods for each class with a per-class Fly Bloom Filter. The inference on test data requires an efficient FlyHash [6] operation followed by a high-dimensional, but very sparse, dot product with the per-class Bloom Filters. On the theoretical side, we establish conditions under which the predictions of our proposed classifier agrees with the predictions of the nearest neighbor classifier. We extensively evaluate our proposed scheme with 71 data sets of varied data dimensionality to demonstrate that the predictive performance of our proposed neuroscience inspired classifier is competitive to the nearest-neighbor classifiers and other single-pass classifiers.

关键词： nearest-neighbor classification randomized algorithm bio-inspired

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Log-Determinant Computation via Weighted L₂ Polynomial Approximation with Prior Distribution of Eigenvalues 1

引用

3rd International Conference on High-Performance Computing and Applications (HPCA)

作者： Peng, Wei Wang, Hongxia Natl Univ Def Technol Coll Sci Sanyi Ave Changsha 410073 Hunan Peoples R China

ISBN: (数字)9783319325576

ISBN: (纸本)9783319325576;9783319325569

Since the classic determinant computation method Cholesky decomposition may devastate sparsity of matrices and cost cubic steps, it is impractical to apply this method to large-scale symmetric positive-definite matrices due to limitation of storage and efficiency. Therefore, a randomized algorithm is proposed to calculate log-determinants of symmetric positive-definite matrices via stochastic trace approximations, implemented by weighted L-2 orthogonal polynomial expansions with efficient recursion formulas and matrix-vector multiplications based on the matrix eigenvalue distribution. As Chebyshev expansions have been applied to this problem before, our main contribution is proposing the strategies of weighted function selection based on prior eigenvalue distribution, which generalizes approximating polynomials for this problem and may accelerate computation.

关键词： Log-determinant Best approximation Eigenvalue distribution randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Counting distinct items over update streams

引用

16th International Symposium on algorithms and Computations (ISAAC 2005)

作者： Ganguly, Sumit Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

ISBN: (纸本)3540309357

In data streaming applications, data arrives at rapid rates and in high volume, thus making it essential to process each stream update very efficiently in terms of both time and space. A data stream is a sequence of data records that must be processed continuously in an online fashion using sub-linear space and sub-linear processing time. We consider the problem of tracking the number of distinct items over data streams that allow insertion and deletion operations. We present two algorithms that improve on the space and time complexity of existing algorithms. (c) 2007 Elsevier B. V. All rights reserved.

关键词： randomized algorithm online algorithm data stream distinct items negative dependence

来源：评论

学校读者我要写书评

暂无评论

Interaction Testing, Fault Location, and Anonymous Attribute-Based Authorization

Interaction Testing, Fault Location, and Anonymous Attribute...

引用

作者： Lanus, Erin Arizona State University

学位级别：Ph.D.

This dissertation studies three classes of combinatorial arrays with practical applications in testing, measurement, and security. Covering arrays are widely studied in software and hardware testing to indicate the presence of faulty interactions. Locating arrays extend covering arrays to achieve identification of the interactions causing a fault by requiring additional conditions on how interactions are covered in rows. This dissertation introduces a new class, the anonymizing arrays, to guarantee a degree of anonymity by bounding the probability a particular row is identified by the interaction presented. Similarities among these arrays lead to common algorithmic techniques for their construction which this dissertation explores. Differences arising from their application domains lead to the unique features of each class, requiring tailoring the techniques to the specifics of each problem. One contribution of this work is a conditional expectation algorithm to build covering arrays via an intermediate combinatorial object. Conditional expectation efficiently finds intermediate-sized arrays that are particularly useful as ingredients for additional recursive algorithms. A cut-and-paste method creates large arrays from small ingredients. Performing transformations on the copies makes further improvements by reducing redundancy in the composed arrays and leads to fewer rows. This work contains the first algorithm for constructing locating arrays for general values of d and t. A randomized computational search algorithmic framework verifies if a candidate array is (&dmacr;,t)-locating by partitioning the search space and performs random resampling if a candidate fails. algorithmic parameters determine which columns to resample and when to add additional rows to the candidate array. Additionally, analysis is conducted on the performance of the algorithmic parameters to provide guidance on how to tune parameters to prioritize speed, accuracy, or a combination of both. T

关键词： Computer science attribute-based access control combinatorial testing covering array locating array randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized GCUR decompositions

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2024年第4期50卷 77-77页

作者： Cao, Zhengbang Wei, Yimin Xie, Pengpeng Ocean Univ China Sch Math Sci Qingdao 266100 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Key Lab Math Nonlinear Sci Shanghai 200433 Peoples R China

By exploiting the random sampling techniques, this paper derives an efficient randomized algorithm for computing a generalized CUR decomposition, which provides low-rank approximations of both matrices simultaneously in terms of some of their rows and columns. For large-scale data sets that are expensive to store and manipulate, a new variant of the discrete empirical interpolation method known as L-DEIM, which needs much lower cost and provides a significant acceleration in practice, is also combined with the random sampling approach to further improve the efficiency of our algorithm. Moreover, adopting the randomized algorithm to implement the truncation process of restricted singular value decomposition (RSVD), combined with the L-DEIM procedure, we propose a fast algorithm for computing an RSVD based CUR decomposition, which provides a coordinated low-rank approximation of the three matrices in a CUR-type format simultaneously and provides advantages over the standard CUR approximation for some applications. We establish detailed probabilistic error analysis for the algorithms and provide numerical results that show the promise of our approaches.

关键词： Generalized CUR decomposition Generalized SVD Restricted SVD L-DEIM randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized Parameterized algorithms for the Kidney Exchange Problem

引用

algorithmS 2019年第2期12卷 50-50页

作者： Lin, Mugang Wang, Jianxin Feng, Qilong Fu, Bin Cent S Univ Sch Comp Sci & Engn Changsha 410083 Hunan Peoples R China Hengyang Normal Univ Sch Comp Sci & Technol Hengyang 421002 Peoples R China Hunan Prov Key Lab Intelligent Informat Proc & Ap Hengyang 421002 Peoples R China Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 <= L <= 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L >= 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

关键词： kidney exchange problem randomized algorithm parameterized algorithm random partitioning multilinear monomial detection

来源：评论

学校读者我要写书评

暂无评论

randomized low-rank approximation of parameter-dependent matrices

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2024年第6期31卷

作者： Kressner, Daniel Lam, Hei Yin EPF Lausanne Inst Math CH-1015 Lausanne Switzerland

This work considers the low-rank approximation of a matrix A(t) depending on a parameter t in a compact set D subset of R-d. Application areas that give rise to such problems include computational statistics and dynamical systems. randomized algorithms are an increasingly popular approach for performing low-rank approximation and they usually proceed by multiplying the matrix with random dimension reduction matrices (DRMs). Applying such algorithms directly to A(t) would involve different, independent DRMs for every t, which is not only expensive but also leads to inherently non-smooth approximations. In this work, we propose to use constant DRMs, that is, A(t) is multiplied with the same DRM for every t. The resulting parameter-dependent extensions of two popular randomized algorithms, the randomized singular value decomposition and the generalized Nystrom method, are computationally attractive, especially when A(t) admits an affine linear decomposition with respect to t. We perform a probabilistic analysis for both algorithms, deriving bounds on the expected value as well as failure probabilities for the approximation error when using Gaussian random DRMs. Both, the theoretical results and numerical experiments, show that the use of constant DRMs does not impair their effectiveness;our methods reliably return quasi-best low-rank approximations.

关键词： dimension reduction matrix approximation numerical linear algebra randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：