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

Online region computations for Euler diagrams with relaxed drawing conventions

JOURNAL OF VISUAL LANGUAGES AND COMPUTING 2017年第Feb.期38卷 18-37页

作者： Cordasco, Gennaro De Chiara, Rosario Fish, Andrew Seconda Univ Napoli Dipartimento Psicol Naples Italy Poste Italians Software Factory Napoli Naples Italy Univ Brighton Sch Comp Engn & Math Brighton E Sussex England

Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Efficient algorithms to quickly compute the abstract regions of an Euler diagram upon curve addition and removal have previously been developed (the single marked point approach, SMPA), but a strict set of drawing conventions (called well-formedness conditions) were enforced, meaning that some abstract diagrams are not representable as concrete diagrams. We present a new methodology (the multiple marked point approach, MMPA) enabling online region computation for Euler diagrams under the relaxation of the drawing convention that zones must be connected regions. Furthermore, we indicate how to extend the methods to deal with the relaxation of any of the drawing conventions, with the use of concurrent line segments case being of particular importance. We provide complexity analysis and compare the MMPA with the SMPA. We show that these methods are theoretically no worse than other comparators, whilst our methods apply to any case, and are likely to be faster in practise due to their online nature. The machinery developed for the concurrency case could be of use in Euler diagram drawing techniques (in the context of the Euler Graph), and in computer graphics (e.g. the development of an advanced variation of a winged edge data structure that deals with concurrency). The algorithms are presented for generic curves;specialisations such as utilising fixed geometric shapes for curves may occur in applications which can enhance capabilities for fast computations of the algorithms' input structures. We provide an implementation of these algorithms, utilising ellipses, and provide time-based experimental data for benchmarking purposes.

关键词： Euler diagrams Region computation on-line algorithms Interactive Diagram Construction

来源：评论

学校读者我要写书评

暂无评论

Faster string matching based on hashing and bit-parallelism

引用

INFORMATION PROCESSING LETTERS 2017年第Jul.期123卷 51-55页

作者： Al-Ssulami, Abdulrakeeb M. Mathkour, Hassan King Saud Univ Dept Comp Sci Coll Comp & Informat Sci Riyadh 11543 Saudi Arabia

String matching is the process of finding the number of occurrences of a pattern P of length m in a text T of length n, where in practice m is much smaller than n. In this paper, we present a faster variation of HASHq based on improved hashing and greedy skip. Experimental results confirm that the proposed algorithm, namely FHASHq, is faster than HASHq, SBNDMq and FSBNDM algorithms on alphabets of size 4 (DNA alphabet), 128, 256, and 512. (C) 2017 Elsevier B.V. All rights reserved.

关键词： String matching q-Gram hashing on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Fair Resource Allocation Over Time 18

Fair Resource Allocation Over Time

引用

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

作者： Evripidis Bampis Bruno Escoffier Sasa Mladenovic Sorbonne Université LIP6 Paris France

We consider the over-time version of the Max-Min Fair Allocation problem. Given a time horizon $t=1,2,łdots, T$, with at each time t a set of demands and a set of available resources that may change over the time defining instance $I_t$, we seek a sequence of solutions $S_1, S_2, łdots , S_T$ that (1) are near-optimal at each time t , and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k -lookahead setting where at time t , the instances at times $t+1, łdots, t+k$ are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes $\mathcalNP $-hard even for families of instances for which the static problem is trivial. Then, we provide a $\fracρ ρ+1 $-approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a $\fracρ ρ+1 $-competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a $\fracρ 2 (2 ρ + 1) $-approximation algorithm using as subroutine a ρ-approximation algorithm for the static version.

关键词： scheduling santa claus approximation algorithms on-line algorithms fairness resource allocation

来源：评论

学校读者我要写书评

暂无评论

ODR: On-line Delay Reduction Approach for Transferring Dynamically-Generated Big Flows Leveraging Software-Defined Networks

ODR: On-line Delay Reduction Approach for Transferring Dynam...

引用

IEEE International Conference on Electro Information Technology

作者： Samah Rahamneh Lina Sawalha Department of Electrical and Computer Engineering Western Michigan University Kalamazoo MI USA

Data analytics techniques are changing the way businesses address core activities like planning, performance evaluation, and decision making. Recently, greater insights are reached as a result of applying such techniques to sets of data growing in diverse dimensions (big data). This attracted extensive research efforts to tackle big data transfer, processing, and storage challenges. Despite being similar in purpose to typical data transfer through the network, big data transfer poses significant changes. These changes warrant a new look at the techniques being used not limited to simple bandwidth increase. In this paper, we propose and implement an on-line algorithm to minimize the delay experienced by near real-time dynamically-generated big data flows when traveling through diverse networks leveraging Software Defined Networking (SDN). The algorithm exploits a comprehensive network view and statistics gathered by SDN controller to move big flows adaptively. The objective function is to minimize the network delay constrained to Service Level Agreement (SLA), in addition to network status. The proposed On-line Delay Reduction (ODR) approach outperforms the de facto Equal Cost Multi-Path (ECMP) algorithm with 19% to 24% reduction in delay.

关键词： Big Data SDN on-line algorithms Network Optimization

来源：评论

学校读者我要写书评

暂无评论

Fast Average-Case Pattern Matching on Weighted Sequences

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2018年第8期29卷 1331-1343页

作者： Barton, Carl Liu, Chang Pissisy, Solon P. European Bioinformat Inst Wellcome Genome Campus Hinxton England Kings Coll London Dept Informat London England

A weighted string is a string in which a set of letters may occur at each position with respective occurrence probabilities. Weighted strings, also known as position weight matrices, weighted sequences or uncertain sequences, naturally arise in many contexts. In this paper, we study the problem of weighted string matching with a special focus on average-case analysis. Given a weighted pattern string x of length m, a text string y of length n > m, both on a constant-sized alphabet of size sigma, and a cumulative weight threshold 1/z, defined as the minimal probability of occurrence of factors in a weighted string, we present an on-line algorithm requiring average-case search time o(n) for pattern matching for weight ratio z/m < min{1/2 log z+1/z, log sigma/log z(log m+log log sigma)}. For a pattern string x of length m, a weighted text string y of length n > m, both on a constant-sized alphabet, and a cumulative weight threshold 1/z, we present an on-line algorithm requiring average-case search time o(n) for the same weight ratio. The importance of these algorithms lies on the fact that, for these ratios, they can work in sublinear search time in the size of the input text, and in linear preprocessing costs in the size of the pattern.

关键词： Pattern matching weighted strings uncertain sequences on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal On-line Computation of Stack Distances for MIN and OPT 17

Optimal On-Line Computation of Stack Distances for MIN and O...

引用

14th ACM International Conference on Computing Frontiers

作者： Bilardi, Gianfranco Ekanadham, Kattamuri Pattnaik, Pratap Univ Padua Dept Informat Engn Via Gradenigo 6A I-35131 Padua Italy IBM TJ Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY 10598 USA

ISBN: (纸本)9781450344876

The replacement policies known as MIN and OPT are optimal for a two-level memory hierarchy. The computation of the cache content for these policies requires the off-line knowledge of the entire address trace. However, the stack distance of a given access, that is, the smallest capacity of a cache for which that access results in a hit, is independent of future accesses and can be computed on-line. Off-line and on-line algorithms to compute the stack distance in time O(V) per access have been known for several decades, where V denotes the number of distinct addresses within the trace. The off-line time bound was recently improved to O(root V log V). This paper introduces the Critical Stack Algorithm for the online computation of the stack distance of MIN and OPT, in time O (log V) per access. The result exploits a novel analysis of properties of OPT and data structures based on balanced binary trees. A corresponding Omega (log V) lower bound is derived by a reduction from element distinctness;this bound holds in a variety of models of computation and applies even to the off-line simulation of just one cache capacity.

关键词： Memory hierarchy replacement policy stack distance MIN OPT on-line algorithms balanced trees lower bounds element distinctness

来源：评论

学校读者我要写书评

暂无评论

Efficient event handling in Wireless Sensor and Actor Networks: An on-line computation approach

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2016年第0期75卷 181-199页

作者： Konstantopoulos, Charalampos Pantziou, Grammati Venetis, Ioannis E. Gavalas, Damianos Univ Piraeus Dept Informat Piraeus Greece Technol Educ Inst Athens Dept Informat Athens Greece Univ Aegean Dept Cultural Technol & Commun Mitilini Greece

The real time response of actors to events occurring in a network area is of critical importance in Wireless Sensor and Actor Networks (WSANs). This in turn requires fast notification of actors from Sensor Nodes (SNs) about events as well as effective coordination of actors for prompt event handling. In this paper, we introduce an on-line distributed protocol for event handling in a WSAN. Existing techniques usually select actors nearby the current event for handling it. However, this greedy approach may eventually lead to a slow response to events because it does not consider the spatial distribution that future events might have. In contrast, in order to cater for future events, the proposed solution probabilistically selects actors for event handling, allowing distant actors to be selected as well. This randomized approach guarantees fast average responsiveness to events, a balanced energy consumption among actors and low energy consumption for SNs. These merits have also been confirmed in the experimental results where the performance of the proposed approach has also been evaluated. In addition, the event-handling scheme presented in this work features efficient distributed algorithms for sensor to actor and actor to actor coordination which are of independent interest. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Wireless sensor and actor networks on-line algorithms k-Server problem Routing

来源：评论

学校读者我要写书评

暂无评论

On-line maximum matching in complete multi-partite graphs with an application to optical networks

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 123-136页

作者： Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel TelHai Acad Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Finding a maximum matching in a graph is a classical problem. The on-line versions of the problem in which the vertices and/or edges of the graph are given one at a time and an algorithm has to calculate a matching incrementally have been studied for more than two decades. Many variants of the problem are considered in the literature. The pioneering work (Karp, 1990) considers a bipartite graph where the vertices of one part are revealed one at a time together with their incident edges. In this work we consider maximal d-colorable graphs which are exactly the complete d-partite graphs. The vertices arrive one at a time together with their incident edges, or equivalently with their corresponding colors in some given d-coloring of the graph. We present an optimal 2/3-competitive deterministic algorithm for this on-line problem. This problem is closely related to that of minimizing the cost of line terminals in star topology optical network. We consider lightpaths arriving in an on-line fashion on a given star network. Our result implies a tight 10/9-competitive algorithm for finding a wavelength assignment minimizing the cost of line terminals in such a network. (C) 2014 Published by Elsevier B.V.

关键词： on-line algorithms Maximum matching Multi-partite graphs Optical networks Switching cost

来源：评论

学校读者我要写书评

暂无评论

Improved neural dynamics for online Sylvester equations solving

引用

INFORMATION PROCESSING LETTERS 2016年第7期116卷 455-459页

作者： Chen, Ke Tampere Univ Technol Dept Signal Proc Tampere 33720 Finland

A novel implicit dynamic system together with its electronic implementation is firstly proposed and investigated for online solution of Sylvester equations. In view of the success of recently-proposed Zhang implicit dynamics, our proposed model is also designed in the implicit-dynamical fashion. Compared to the existing neural dynamics, i.e., conventional gradient explicit dynamics and Zhang implicit dynamics, our implicit dynamic system can achieve superior global exponential convergence performance. Computer simulation results demonstrate theoretical analysis of our proposed dynamic model for real-time solution of Sylvester equations. (C) 2016 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Parallel-processing Neural dynamics Sylvester equations Global exponential convergence

来源：评论

学校读者我要写书评

暂无评论

Online scheduling of unit jobs on three machines with rejection: A tight result

引用

INFORMATION PROCESSING LETTERS 2016年第3期116卷 252-255页

作者： Epstein, Leah Zebedat-Haider, Hanan Univ Haifa Dept Math IL-31999 Haifa Israel Sapir Coll Dept Comp Sci Sderot Israel

We design an algorithm of the best possible competitive ratio for preemptive and non preemptive scheduling of unit size jobs with rejection on three identical machines. The algorithm does not use preemption even for the preemptive variant, and it has the interesting feature that one of its parameters is not fixed in advance, and it is defined based on the properties of the first input job having a sufficiently large rejection penalty. (C) 2015 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Scheduling Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：