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

A randomized SCHEDULING algorithm FOR MULTIPROCESSOR ENVIRONMENTS

PARALLEL PROCESSING LETTERS 2012年第4期22卷 1250015-1250015页

作者： Mishra, Pramod Kumar Mishra, Kamal Sheel Mishra, Abhishek Tripathi, Anil Kumar Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Comp Sci Varanasi 221005 Uttar Pradesh India Banaras Hindu Univ Ctr Interdisciplinary Math Sci Dept Sci & Technol Varanasi 221005 Uttar Pradesh India Sch Management Sci Khushipur Varanasi 221011 Uttar Pradesh India Indian Inst Technol Rajasthan Ctr Excellence Informat & Commun Technol Jodhpur 342011 Rajasthan India Indian Inst Technol Banaras Hindu Univ Dept Comp Engn Varanasi 221005 Uttar Pradesh India

In this paper, we propose a randomized scheduling algorithm on a fully connected homogeneous multiprocessor environment. This is a randomized version of our earlier algorithm in which we used priority of modules that was dependent on the computation and the communication times associated with the modules. First we propose a generalization of our earlier scheduling algorithm with restricted number of clusters to reduce the time complexity. Then we apply randomization to the generalized algorithm and demonstrate its superiority over our previous work. We show the complexity of our proposed algorithm as O(ab vertical bar V vertical bar(vertical bar V vertical bar+vertical bar E vertical bar)log(vertical bar V vertical bar + vertical bar E vertical bar). Here a is the number of randomization steps, and b is a limit on the number of clusters formed. If we use a and b as constants, then this gives a better complexity in comparison with the complexity of our previous algorithm that was O(vertical bar V vertical bar (2)(vertical bar V vertical bar + vertical bar E vertical bar)log(vertical bar V vertical bar+vertical bar E vertical bar)). In comparison with our previous work we get a performance improvement of up to 6.63%;and a performance improvement of up to 12.56% when compared with Sarkar's Edge Zeroing algorithm.

关键词： Clustering distributed computing homogeneous systems randomized algorithm task allocation

来源：评论

学校读者我要写书评

暂无评论

Robust neighbor discovery in multi-hop multi-channel heterogeneous wireless networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 92卷 15-34页

作者： Zeng, Yanyan Mills, K. Alex Gokhale, Shreyas Mittal, Neeraj Venkatesan, S. Chandrasekaran, R. Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA JPMorgan Chase New York NY USA

An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate within one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A cognitive radio transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A cognitive radio node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a cognitive radio network. In this work, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions (e.g., maximum node degree known or unknown) for both synchronous and asynchronous systems under minimal knowledge. We also show that our randomized algorithms are naturally suited to tolerate unreliable channels and adversarial attacks. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Multi-hop multi-channel wireless network Cognitive radio technology Heterogeneous channel availability Neighbor discovery randomized algorithm Asynchronous system Clock drift Lossy channel Jamming attack

来源：评论

学校读者我要写书评

暂无评论

A randomized APPROACH TO EFFICIENT KERNEL CLUSTERING

A RANDOMIZED APPROACH TO EFFICIENT KERNEL CLUSTERING

引用

IEEE Global Conference on Signal and Information Processing (GlobalSIP)

作者： Pourkamali-Anaraki, Farhad Becker, Stephen Univ Colorado Dept Elect Comp & Energy Engn Boulder CO 80309 USA Univ Colorado Dept Appl Math Boulder CO 80309 USA

ISBN: (纸本)9781509045457

Kernel-based K-means clustering has gained popularity due to its simplicity and the power of its implicit non-linear representation of the data. A dominant concern is the memory requirement since memory scales as the square of the number of data points. We provide a new analysis of a class of approximate kernel methods that have more modest memory requirements, and propose a specific one-pass randomized kernel approximation followed by standard K-means on the transformed data. The analysis and experiments suggest the method is accurate, while requiring drastically less memory than standard kernel K-means and significantly less memory than Nystrom based approximations.

关键词： Kernel methods Unsupervised learning Low-rank approximation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast and robust circle detection method using isosceles triangles sampling

引用

PATTERN RECOGNITION 2016年 54卷 218-228页

作者： Zhang, Hanqing Wiklund, Krister Andersson, Magnus Umea Univ Dept Phys Linneaus Vaeg 9 SE-90187 Umea Sweden

Circle detection using randomized sampling has been developed in recent years to reduce computational intensity. However, randomized sampling is sensitive to noise that can lead to reduced accuracy and false-positive candidates. To improve on the robustness of randomized circle detection under noisy conditions this paper presents a new methodology for circle detection based upon randomized isosceles triangles sampling. It is shown that the geometrical property of isosceles triangles provides a robust criterion to find relevant edge pixels which, in turn, offers an efficient means to estimate the centers and radii of circles. For best efficiency, the estimated results given by the sampling from individual connected components of the edge map were analyzed using a simple clustering approach. To further improve on the accuracy we applied a two-step refinement process using chords and linear error compensation with gradient information of the edge pixels. Extensive experiments using both synthetic and real images have been performed. The results are compared to leading state-of-the-art algorithms and it is shown that the proposed methodology has a number of advantages: it is efficient in finding circles with a low number of iterations, it has high rejection rate of false-positive circle candidates, and it has high robustness against noise. All this makes it adaptive and useful in many vision applications. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Circle detection randomized algorithm Sampling strategy Isosceles triangles

来源：评论

学校读者我要写书评

暂无评论

Stability analysis of sampled-data switched systems with quantization

引用

AUTOMATICA 2016年 69卷 157-168页

作者： Wakaiki, Masashi Yamamoto, Yutaka Univ Calif Santa Barbara Ctr Control Dynam Syst & Computat CCDC Santa Barbara CA 93106 USA Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

We propose a stability analysis method for sampled-data switched linear systems with finite-level static quantizers. In the closed-loop system, information on the active mode of the plant is transmitted to the controller only at each sampling time. This limitation of switching information leads to a mode mismatch between the plant and the controller, and the system may become unstable. A mode mismatch also makes it difficult to find an attractor set to which the state trajectory converges. A switching condition for stability is characterized by the total time when the modes of the plant and the controller are different. Under this condition, we derive an ultimate bound on the state trajectories by using a common Lyapunov function computed from a randomized algorithm. The switching condition can be reduced to a dwell-time condition. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Quantization Sampled-data control Switched systems Lyapunov function randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Noise Adding Mechanisms for Approximate Differential Privacy

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第2期62卷 952-969页

作者： Geng, Quan Viswanath, Pramod Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Google Inc New York NY 10011 USA

We study the (nearly) optimal mechanisms in (epsilon, delta)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utility-maximization/cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between epsilon and delta in utility and privacy analysis for histogram-like query functions, and show that the (epsilon, delta)-differential privacy is a framework not much more general than the (epsilon, 0)-differential privacy and (0, delta)-differential privacy in the context of l(1) and l(2) cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of l(1) and l(2) cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (epsilon, delta) -> (0, 0)). We conclude that in (epsilon, delta)-differential privacy, the optimal noise magnitude and the noise power are Theta(min((1/epsilon), (1/delta))) and Theta(min((1/epsilon(2)), (1/delta(2)))), respectively, in the high privacy regime.

关键词： Data privacy randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Bounded information dissemination in multi-channel wireless networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第3期31卷 996-1012页

作者： Yan, Yu Yu, Dongxiao Wang, Yuexuan Yu, Jiguo Lau, Francis C. M. Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Qufu Normal Univ Sch Comp Sci Rizhao 276800 Peoples R China

More and more wireless networks and devices now operate on multiple channels, which poses the question: How to use multiple channels to speed up communication? In this paper, we answer this question for the case of wireless ad-hoc networks where information dissemination is a primitive operation. Specifically, we propose a randomized distributed algorithm for information dissemination that is very near the optimal. The general information dissemination problem is to deliver information packets, stored initially in different nodes (the packet holders), to all the nodes in the network, and the objective is to minimize the time needed. With an eye toward the reality, we assume a model where the packet holders are determined by an adversary, and neither the number nor the identities of packet holders are known to the nodes in advance. Not knowing the value of sets this problem apart from broadcasting and all-to-all communication (gossiping). We study the information dissemination problem in single-hop networks with bounded-size messages. We present a randomized algorithm which can disseminate all packets in rounds with high probability, where is the number of available channels and is the bound on the number of packets a message can carry. Compared with the lower bound , the given algorithm is very close to the asymptotical optimal except for an additive factor. Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination, which also breaks the lower bound that holds for single-channel networks (even if is infinity).

关键词： Information dissemination Multi-channel wireless network Distributed algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Towards Dynamic Demand Response On Efficient Consumer Grouping algorithmics

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2016年第1期1卷 20-34页

作者： Pal, Ranjan Chelmis, Charalampos Frincu, Marc Prasanna, Viktor Univ Southern Calif Dept Comp Sci Los Angeles CA 90007 USA Univ Southern Calif Dept Elect Engn Los Angeles CA 90007 USA SUNY Albany Dept Comp Sci 1400 Washington Ave Albany NY 12222 USA West Univ Timisoara Dept Comp Sci Timisoara 300223 Romania

The widespread monitoring of electricity consumption due to increasingly pervasive deployment of networked sensors in urban environments has resulted in an unprecedentedly large volume of data being collected. Particularly, with the emerging Smart Grid technologies becoming more ubiquitous, real-time and online analytics for discovering the underlying structure of increasing-dimensional (w.r.t. time) consumer time series data are crucial to convert the massive amount of fine-grained energy information gathered from residential smart meters into appropriate demand response (DR) insights. In this paper we propose READER and OPTIC, that are real-time and online algorithmic pre-processing frameworks respectively, for effective DR in the Smart Grid. READER (OPTIC) helps discover underlying structure from increasing-dimensional consumer consumption time series data in a provably optimal real-time (online) fashion. READER (OPTIC) catalyzes the efficacy of DR programs by systematically and efficiently managing the energy consumption data deluge, at the same time capturing in real-time (online), specific behavior, i.e., households or time instants with similar consumption patterns. The primary feature of READER (OPTIC) is a real-time (online) randomized approximation algorithm for grouping consumers based on their electricity consumption time series data, and provides two crucial benefits: (i) time efficiently tackles high volume, increasing-dimensional time series data and (ii) provides provable worst case grouping performance guarantees. We validate the grouping and DR efficacy of READER and OPTIC via extensive experiments conducted on both, a USC microgrid dataset as well as a synthetically generated dataset.

关键词： Time series consumer grouping randomized algorithm demand response

来源：评论

学校读者我要写书评

暂无评论

Scalable wake-up of multi-channel single-hop radio networks

引用

THEORETICAL COMPUTER SCIENCE 2016年 615卷 23-44页

作者： Chlebus, Bogdan S. De Marco, Gianluca Kowalski, Dariusz R. Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Univ Salerno Dipartimento Informat I-84084 Salerno Italy Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(k log(1/b) k log n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b > d log log n, for some constant d > 1, which wakes up a network in O(k/b log n log(b log n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log n(log b + log log n)), because any deterministic algorithm requires Omega(k/b log n/k) time. We give a randomized algorithm that wakes up a network within O(k(1/b) In 1/epsilon) rounds with a probability that is at least 1 - epsilon, for any 0 < epsilon < 1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log(-1) (1/p) log n log(1/b) k), and the other in time O(log(-1) (1/p) k/b log n log(b log n)) when the inequality b > log(128b log n) holds, both with probabilities that are at least 1 - 1/poly(n). (c) 2015 Elsevier B.V. All rights reserved.

关键词： Multiple access channel Radio network Multi-channel Wake-up Synchronization Deterministic algorithm randomized algorithm Distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

The Optimal Noise-Adding Mechanism in Differential Privacy

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第2期62卷 925-951页

作者： Geng, Quan Viswanath, Pramod Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Google Inc New York NY 10011 USA

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal epsilon-differentially private mechanism for a single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for l(1) and l(2) cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (epsilon is small), the Laplacian mechanism is asymptotically optimal as epsilon -> 0;in the low privacy regime (epsilon is large), the minimum magnitude and second moment of noise are Theta (Delta e((-epsilon/2))) and Theta(Delta(2)e((-2 epsilon/3))) as epsilon -> +infinity, respectively, while the corresponding figures when using the Laplacian mechanism are Delta/epsilon and 2 Delta(2)/epsilon(2), where Delta is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

关键词： Data privacy randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：