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

Proceedings of the 15th conference on Computational linguistics - Volume 2

作者： Günther Görz Marcus Kesseler University of Erlangen-Nürnberg

This paper discusses to which extent the concept of "anytime algorithms" can be applied to parsing algorithms with feature unification. We first try to give a more precise definition of what an anytime algorithm is. We arque that parsing algorithms have to be classified as contract algorithms as opposed to (truly) interruptible algorithms. With the restriction that the transaction being active at the time an interrupt is issued has to be completed before the interrupt can be executed, it is possible to provide a parser with limited anytime behavior, which is in fact being realized in our research prototype.

关键词： speech analysis anytime algorithms parsing

来源：评论

学校读者我要写书评

暂无评论

Efficient anytime Anywhere algorithms for Closeness Centrality in Large and Dynamic Graphs 30

Efficient Anytime Anywhere Algorithms for Closeness Centrali...

引用

30th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Santos, Eunice E. Korah, John Murugappan, Vairavan Subramanian, Suresh IIT Dept Comp Sci Chicago IL 60616 USA

ISBN: (纸本)9781509036820

Recent advances in social network analysis methodologies for large (millions of nodes and billions of edges) and dynamic (evolving at different rates) networks have focused on leveraging new high performance architectures, parallel/distributed tools and novel data structures. However, there has been less focus on designing scalable and efficient algorithms to handle the challenges of dynamism in large-scale networks. In our previous work, we presented an overarching anytime anywhere framework for designing parallel and distributed social network analysis algorithms that are scalable to large network sizes and can handle dynamism. A key contribution of our work is to leverage the anytime and anywhere properties of graph analysis problems to design algorithms that can efficiently handle network dynamism by reusing partial results, and by reducing re-computations. In this paper, we present an algorithm for closeness centrality analysis that can handle changes in the network in the form of edge deletions. Using both theoretical analysis and experimental evaluations, we examine the performance of our algorithm with different network sizes and dynamism rates.

关键词： social network analysis parallel and distributed processing centrality analysis dynamic graphs anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

Automatically improving the anytime behaviour of optimisation algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第3期235卷 569-582页

作者： Lopez-Ibanez, Manuel Stuetzle, Thomas ULB IRIDIA B-1050 Brussels Belgium

Optimisation algorithms with good anytime behaviour try to return as high-quality solutions as possible independently of the computation time allowed. Designing algorithms with good anytime behaviour is a difficult task, because performance is often evaluated subjectively, by plotting the trade-off curve between computation time and solution quality. Yet, the trade-off curve may be modelled also as a set of mutually nondominated, bi-objective points. Using this model, we propose to combine an automatic configuration tool and the hypervolume measure, which assigns a single quality measure to a nondominated set. This allows us to improve the anytime behaviour of optimisation algorithms by means of automatically finding algorithmic configurations that produce the best nondominated sets. Moreover, the recently proposed weighted hypervolume measure is used here to incorporate the decision-maker's preferences into the automatic tuning procedure. We report on the improvements reached when applying the proposed method to two relevant scenarios: (i) the design of parameter variation strategies for MAX-MIN Ant System and (ii) the tuning of the anytime behaviour of SCIP, an open-source mixed integer programming solver with more than 200 parameters. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Metaheuristics anytime algorithms Automatic configuration Offline tuning

来源：评论

学校读者我要写书评

暂无评论

Practical algorithms for execution engine selection in data flows

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2015年 45卷 133-148页

作者： Kougka, Georgia Gounaris, Anastasios Tsichlas, Kostas Aristotle Univ Thessaloniki Thessaloniki Greece

Data-intensive flows are increasingly encountered in various settings, including business intelligence and scientific scenarios. At the same time, flow technology is evolving. Instead of resorting to monolithic solutions, current approaches tend to employ multiple execution engines, such as Hadoop clusters, traditional DBMSs, and stand-alone tools. We target the problem of allocating flow activities to specific heterogeneous and interdependent execution engines while minimizing the flow execution cost. To date, the state-of-the-art is limited to simple heuristics. Although the problem is intractable, we propose practical anytime solutions that are capable of outperforming those simple heuristics and yielding allocation plans in seconds even when optimizing large flows on ordinary machines. Moreover, we prove the NP-hardness of the problem in the generic case and we propose an exact polynomial solution for a specific form of flows, namely, linear flows. We thoroughly evaluate our solutions in both real-world and flows synthetic, and the results show the superiority of our solutions. Especially in real-world scenarios, we can decrease execution time up to more than 3 times. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Data flows Resource allocation Heterogeneous machines anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-processor Search and Scheduling Problems with Setup Cost

引用

THEORY OF COMPUTING SYSTEMS 2017年第4期60卷 637-670页

作者： Angelopoulos, Spyros Arsenio, Diogo Durr, Christoph Lopez-Ortiz, Alejandro UPMC Univ Paris 06 Sorbonne Univ CNRS LIP6 Paris France Univ Paris Diderot CNRS Paris France Univ Paris Diderot Inst Math Paris France Univ Waterloo Canada Sch Comp Sci Waterloo ON Canada

We study two optimization problems in a multiprocessor environment in the presence of set-up costs. The first problem involves multiple parallel searchers (e.g., robots) that must locate a target which lies in one of many concurrent rays, and at an unknown position from their common origin. Every time a searcher turns direction, it incurs a turn cost. The objective is to derive a search strategy for locating the target as efficiently as possible. The second problem involves contract algorithms, namely algorithms in which the available computation time is specified prior to their execution. In particular, we seek a schedule of executions of contract algorithms for several different problems in identical parallel processors so as to efficiently simulate an interruptible algorithm, assuming that each execution incurs a given set-up cost. The performance of the search and scheduling strategies are evaluated by means of well-established measures, namely the competitive ratio and the acceleration ratio, respectively. In this paper we provide near-optimal strategies for the above problems, using an approach based on infinite linear-programming formulations. More precisely, we present a search strategy (resp. schedule) which is optimal when the number of rays (resp. problems) is a multiple of the number of searchers (resp. processors). For the general case, we show that the corresponding solutions are very close to optimal.

关键词： Online search Scheduling Linear programming anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

引用

COMPUTER VISION AND IMAGE UNDERSTANDING 2008年第3期110卷 378-389页

作者： Brooks, Rupert Arbel, Tal Precup, Doina McGill Univ Ctr Intelligent Machines Montreal PQ H3A 2A7 Canada McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada

Image alignment refers to finding the best transformation from a fixed reference image to a new image of a scene. This process is often optimizing a similarity measure between images, computed based on the image data. However, in time-critical applications state-of-the-art methods for computing similarity are too slow. Instead of using all the image data to compute similarity, one could use only a subset of pixels to improve the speed, but often this comes at the cost of reduced accuracy. These kinds of tradeoffs between the amount of computation and the accuracy of the result have been addressed in the field of real-time artificial intelligence as deliberation control problems. We propose that the optimization of a similarity measure is a natural application domain for deliberation control using the anytime algorithm framework. In this paper, we present anytime versions for the computation of two common image similarity measures: mean squared difference and mutual information. Off-line, we learn a performance profile specific to each measure, which is then used on-line to select the appropriate amount of pixels to process at each optimization step. When tested against existing techniques, our method achieves comparable quality and robustness with significantly less computation. (C) 2007 Elsevier Inc. All rights reserved.

关键词： similarity measures efficient image alignment efficient image registration anytime algorithms deliberation control

来源：评论

学校读者我要写书评

暂无评论

Monitored Reconstruction: Computed Tomography as an anytime Algorithm

引用

IEEE ACCESS 2020年 8卷 110759-110774页

作者： Bulatov, Konstantin Chukalina, Marina Buzmakov, Alexey Nikolaev, Dmitry Arlazarov, Vladimir V. Russian Acad Sci Fed Res Ctr Comp Sci & Control Moscow 119333 Russia Smart Engines Serv LLC Moscow 121205 Russia Smart Engines Serv LLC Dept Xray Comp Vis Moscow 121205 Russia Russian Acad Sci Fed Sci Res Ctr Crystallog & Photon Moscow 119333 Russia Russian Acad Sci Inst Informat Transmiss Problems Kharkevich Inst Moscow 127051 Russia

Computed tomography is an important technique for non-destructive analysis of an object's internal structure, relevant for scientific studies, medical applications, and industry. Pressing challenges emerging in the field of tomographic imaging include speeding up reconstruction, reducing the time required to obtain the X-ray projections, and reducing the radiation dose imparted to the object. In this paper, we introduce a model of a monitored reconstruction process, in which the acquiring of projections is interspersed with image reconstruction. This model allows to examine the tomographic reconstruction process as an anytime algorithm and consider a problem of finding the optimal stopping point, corresponding to the required number of X-ray projections for the currently scanned object. We outline the theoretical framework for the monitored reconstruction, propose ways of constructing stopping rules for various reconstruction quality metrics and provide their experimental evaluation. Due to stopping at different times for different objects, the proposed approach allows to achieve a higher mean reconstruction quality for a given mean number of X-ray projections. Conversely, fewer projections on average are used to achieve the same mean reconstruction quality.

关键词： Image reconstruction Computed tomography X-ray imaging Monitoring Medical diagnostic imaging anytime algorithms computed tomography dose reduction monitored reconstruction optimal stopping X-ray tomography

来源：评论

学校读者我要写书评

暂无评论

Potential-based bounded-cost search and anytime Non-Parametric A

引用

ARTIFICIAL INTELLIGENCE 2014年 214卷 1-25页

作者： Stern, Roni Felner, Ariel van den Berg, Jur Puzis, Rami Shah, Rajat Goldberg, Ken Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Utah Sch Comp Salt Lake City UT USA Univ Calif Berkeley Berkeley CA 94720 USA

This paper presents two new search algorithms: Potential Search (PTS) and anytime Potential Search/anytime Non-Parametric A* (APTS/ANA*). Both algorithms are based on a new evaluation function that is easy to implement and does not require user-tuned parameters. PTS is designed to solve bounded-cost search problems, which are problems where the task is to find as fast as possible a solution under a given cost bound. APTS/ANA* is a non-parametric anytime search algorithm discovered independently by two research groups via two very different derivations. In this paper, co-authored by researchers from both groups, we present these derivations: as a sequence of calls to PTS and as a non-parametric greedy variant of anytime Repairing A*. We describe experiments that evaluate the new algorithms in the 15-puzzle, KPP-COM, robot motion planning, gridworld navigation, and multiple sequence alignment search domains. Our results suggest that when compared with previous anytime algorithms, APTS/ANA*: (1) does not require user-set parameters, (2) finds an initial solution faster, (3) spends less time between solution improvements, (4) decreases the suboptimality bound of the current-best solution more gradually, and (5) converges faster to an optimal solution when reachable. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Heuristic search anytime algorithms Robotics

来源：评论

学校读者我要写书评

暂无评论

GSST: anytime guaranteed search

引用

AUTONOMOUS ROBOTS 2010年第1期29卷 99-118页

作者： Hollinger, Geoffrey Kehagias, Athanasios Singh, Sanjiv Carnegie Mellon Univ Inst Robot Pittsburgh PA 15217 USA Aristotle Univ Thessaloniki Fac Engn Thessaloniki 54124 Greece

We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.

关键词： Multi-robot coordination Graph search anytime algorithms Decentralized computation Pursuit/evasion

来源：评论

学校读者我要写书评

暂无评论

anytime route planning with constrained devices

引用

COMPUTERS & ELECTRICAL ENGINEERING 2016年第0期54卷 53-67页

作者： Braga, Marcus de L. dos Santos, Alyson de J. Pedroza, Aloysio C. P. Costa, Luis Henrique M. K. de Amorim, Marcelo Dias Ghamri-Doudane, Yacine Univ Fed Rio de Janeiro PEE COPPE GTA Rio De Janeiro Brazil UPMC Sorbonne Univ CNRS LIP6 Paris France Univ La Rochelle L3i La Rochelle France

Urban mobility became a major challenge around the world, with frequent congestion and ever growing travel time. Albeit recent advances in the area of Intelligent Transportation Systems (ITS), it is still difficult to predict and manage the road infrastructure due to dynamics and instability of the traffic. One key issue is how, given some traffic monitoring information, a vehicle decides to dynamically change its route. In this paper, we analyze algorithms of the anytime class to make the route planning considering GPS traces of buses in Rio de Janeiro, as a measurement of traffic flows. anytime algorithms inform, in a timely fashion, a sub-optimal response and progressively improves it as time goes by. We evaluate time and memory consumption, route length, arrival time, average velocity, distance traveled, and pathways on an experimental platform composed of Raspberry Pi nodes. For different time windows, the results show that ARA(*) allows finding alternative routes that, if used, help reduce traffic congestion. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Route planning ARA Vehicular networks anytime algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：