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

ULTRA: Unlimited Transfers for Efficient Multimodal Journey Planning

TRANSPORTATION SCIENCE 2023年第6期57卷 1536-1559页

作者： Baum, Moritz Buchhold, Avalentin Sauer, Jonas Wagner, Dorothea Zuendorfa, Tobias Karlsruhe Inst Technol D-76131 Karlsruhe Germany

We study a multimodal journey planning scenario consisting of a public transit network and a transfer graph that represents a secondary transportation mode (e.g., walking, cycling, e-scooter). The objective is to compute Pareto-optimal journeys with respect to arrival time and the number of used public transit trips. Whereas various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. Existing approaches, therefore, typically only support limited walking between stops by either imposing a maximum transfer distance or requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called unlimited transfers (ULTRA): given an unlimited transfer graph, which may represent any non-schedule based transportation mode, ULTRA computes a small number of transfer shortcuts that are provably sufficient for computing a Pareto set of optimal journeys. These transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-query algorithm family. Our extensive experimental evaluation shows that ULTRA improves these algorithms from limited to unlimited transfers without sacrificing query speed. This is true not just for walking, but also for faster transfer modes, such as bicycle or car. Compared with the state of the art for multimodal journey planning, the fastest ULTRA-based algorithm achieves a speedup of an order of magnitude.

关键词： journey planning public transit algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Improved and extended locating functionality on compressed suffix arrays

引用

JOURNAL OF DISCRETE algorithmS 2015年 32卷 53-63页

作者： Gog, Simon Navarro, Gonzalo Petri, Matthias Karlsruhe Inst Technol Inst Theoret Informat D-76021 Karlsruhe Germany Univ Chile Dept Comp Sci Ctr Biotechnol & Bioengn Santiago Chile Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia

Compressed Suffix Arrays (CSAs) offer the same functionality as classical suffix arrays (SAs), and more, within space close to that of the compressed text, and in addition they can reproduce any text fragment. Furthermore, their pattern search times are comparable to those of SAs. This combination has made CSAs extremely successful substitutes for SAs in space-demanding applications. Their weakest point is that they are orders of magnitude slower when retrieving the precise positions of pattern occurrences. SAs have other well-known shortcomings, inherited by CSAs, such as not retrieving those positions in a useful order. In this paper we present new techniques that, on the one hand, improve the current space/time tradeoffs for retrieving pattern occurrences in CSAs, and on the other, efficiently support extended pattern locating functionalities, such as retrieving occurrences in text order or limiting the occurrences to within a text window. Our experimental results display considerable savings with respect to the baseline techniques in many cases of interest: in some cases we outperform their time by a factor of two or three. (C) 2015 Elsevier B. V. All rights reserved.

关键词： Compressed suffix array Inverted indexes algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Gerbil: a fast and memory-efficient k-mer counter with GPU-support

引用

algorithmS FOR MOLECULAR BIOLOGY 2017年第1期12卷 9-9页

作者： Erbert, Marius Rechner, Steffen Mueller-Hannemann, Matthias Martin Luther Univ Halle Wittenberg Inst Comp Sci Von Seckendorff Pl 1 D-06120 Halle Saae Germany

Background: A basic task in bioinformatics is the counting of k-mers in genome sequences. Existing k-mer counting tools are most often optimized for small k = 32. Our software is the result of an intensive process of ... 详细信息

Background: A basic task in bioinformatics is the counting of k-mers in genome sequences. Existing k-mer counting tools are most often optimized for small k < 32 and suffer from excessive memory resource consumption or degrading performance for large k. However, given the technology trend towards long reads of next-generation sequencers, support for large k becomes increasingly important. Results: We present the open source k-mer counting software Gerbil that has been designed for the efficient counting of k-mers for k >= 32. Our software is the result of an intensive process of algorithm engineering. It implements a two-step approach. In the first step, genome reads are loaded from disk and redistributed to temporary files. In a second step, the k-mers of each temporary file are counted via a hash table approach. In addition to its basic functionality, Gerbil can optionally use GPUs to accelerate the counting step. In a set of experiments with real-world genome data sets, we show that Gerbil is able to efficiently support both small and large k. Conclusions: While Gerbil's performance is comparable to existing state-of-the-art open source k-mer counting tools for small k < 32, it vastly outperforms its competitors for large k, thereby enabling new applications which require large values of k.

关键词： k-mer counting de novo assembly Genome sequences GPU computing algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Fog-Computing-Based Heartbeat Detection and Arrhythmia Classification Using Machine Learning

引用

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

作者： Scire, Alessandro Tropeano, Fabrizio Anagnostopoulos, Aris Chatzigiannakis, Ioannis Sapienza Univ Rome Dept Comp Control & Management Engn Antonio Ruber I-00185 Rome Italy

Designing advanced health monitoring systems is still an active research topic. Wearable and remote monitoring devices enable monitoring of physiological and clinical parameters (heart rate, respiration rate, temperature, etc.) and analysis using cloud-centric machine-learning applications and decision-support systems to predict critical clinical states. This paper moves from a totally cloud-centric concept to a more distributed one, by transferring sensor data processing and analysis tasks to the edges of the network. The resulting solution enables the analysis and interpretation of sensor-data traces within the wearable device to provide actionable alerts without any dependence on cloud services. In this paper, we use a supervised-learning approach to detect heartbeats and classify arrhythmias. The system uses a window-based feature definition that is suitable for execution within an asymmetric multicore embedded processor that provides a dedicated core for hardware assisted pattern matching. We evaluate the performance of the system in comparison with various existing approaches, in terms of achieved accuracy in the detection of abnormal events. The results show that the proposed embedded system achieves a high detection rate that in some cases matches the accuracy of the state-of-the-art algorithms executed in standard processors.

关键词： ECG automated detection of abnormalities heartbeat classification data mining recurrent neural network long-short term memory algorithm engineering experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Large-scale graph generation: Recent results of the SPP 1736 - Part II

引用

IT-INFORMATION TECHNOLOGY 2020年第3-4期62卷 135-144页

作者： Meyer, Ulrich Penschuck, Manuel Goethe Univ Inst Comp Sci D-60325 Frankfurt Germany

The selection of input data is a crucial step in virtually every empirical study. Experimental campaigns in algorithm engineering, experimental algorithmics, network analysis, and many other fields often require suited network data. In this context, synthetic graphs play an important role, as data sets of observed networks are typically scarce, biased, not sufficiently understood, and may pose logistic and legal challenges. Just like processing huge graphs becomes challenging in the big data setting, new algorithmic approaches are necessary to generate such massive instances efficiently. Here, we update our previous survey [35] on results for large-scale graph generation obtained within the DFG priority programme SPP 1736 (algorithms for Big Data);to this end, we broaden the scope and include recently published results.

关键词： Random graphs scalable graph generators algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs

引用

algorithmS 2020年第8期13卷 191页

作者： D'Emidio, Mattia Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy

Computing shortest-path distances is a fundamental primitive in the context of graph data mining, since this kind of information is essential in a broad range of prominent applications, which include social network analysis, data routing, web search optimization, database design and route planning. Standard algorithms for shortest paths (e.g., Dijkstra's) do not scale well with the graph size, as they take more than a second or huge memory overheads to answer a singlequery on the distancefor large-scale graph datasets. Hence, they are not suited to mine distances from big graphs, which are becoming the norm in most modern application contexts. Therefore, to achieve faster query answering, smarter and more scalable methods have been designed, the most effective of them based on precomputing and querying a compact representation of the transitive closure of the input graph, called the 2-hop-coverlabeling. To use such approaches in realistictime-evolvingscenarios, when the managed graph undergoes topological modifications over time, specificdynamic algorithms, carefully updating the labeling as the graph evolves, have been introduced. In fact, recomputing from scratch the 2-hop-coverstructure every time the graph changes is not an option, as it induces unsustainable time overheads. While the state-of-the-art dynamic algorithm to update a 2-hop-coverlabeling againstincrementalmodifications (insertions of arcs/vertices, arc weights decreases) offers very fast update times, the only known solution fordecrementalmodifications (deletions of arcs/vertices, arc weights increases) is still far from being considered practical, as it requires up to tens of seconds of processing per update in several prominent classes of real-world inputs, as experimentation shows. In this paper, we introduce a new dynamic algorithm to update 2-hop-coverlabelings against decremental changes. We prove its correctness, formally analyze its worst-case performance, and assess its effectiveness throug

关键词： large graph mining algorithm engineering experimental algorithmics time-evolving data big data processing

来源：评论

学校读者我要写书评

暂无评论

Convex-Hull algorithms: Implementation, Testing, and Experimentation

引用

algorithmS 2018年第12期11卷 195-195页

作者： Gamby, Ask Neve Katajainen, Jyrki Univ Copenhagen Dept Comp Sci Univ Pk 5 DK-2100 Copenhagen East Denmark Jyrki Katajainen & Co DK-3390 Hundested Denmark Tech Univ Denmark Natl Space Inst DK-2800 Lyngby Denmark

From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: plane-sweep,torch, quickhull, and throw-away. With a new set of space-efficient implementations, the experimental results-in the integer-arithmetic setting-are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.

关键词： computational geometry algorithm convex hull rectilinear convex hull algorithm engineering implementation testing experimentation robustness performance

来源：评论

学校读者我要写书评

暂无评论

On Finding Optimal (Dynamic) Arborescences

引用

algorithmS 2023年第12期16卷 559-559页

作者： Espada, Joaquim Francisco, Alexandre P. Rocher, Tatiana Russo, Luis M. S. Vaz, Catia Invest & Desenvolvimento Lisboa INESC ID Inst Engn Sistemas & Comp P-1000029 Lisbon Portugal Univ Lisbon Inst Super Tecn P-1049001 Lisbon Portugal Inst Politecn Lisboa Inst Super Engn Lisboa P-1959007 Lisbon Portugal

Let G=(V,E) be a directed and weighted graph with a vertex set V of size n and an edge set E of size m such that each edge (u,v)is an element of E has a real-valued weight w(u,c). An arborescence in G is a subgraph T=(V,E ') such that, for a vertex u is an element of V, which is the root, there is a unique path in T from u to any other vertex v is an element of V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with a minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely, edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well-known problem with applications in several domains such as network design optimization and phylogenetic inference. In this paper, we revisit the algorithmic ideas proposed by several authors for this problem. We provide detailed pseudocode, as well as implementation details, and we present experimental results regarding large scale-free networks and phylogenetic inference. Our implementation is publicly available.

关键词： optimal arborescences Edmonds' algorithm dynamic algorithm algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Competition: An Adaptive Protocol Stack for High-Dependability based on the Population Protocols Paradigm 16

Competition: An Adaptive Protocol Stack for High-Dependabili...

引用

Proceedings of the 2016 International Conference on Embedded Wireless Systems and Networks

作者： Dimitrios Amaxilatis Ioannis Chatzigiannakis Computer Engineering & Informatics Department University of Patras and Computer Technology Institute & Press (CTI) Department of Computer Control and Management Engineering Sapienza University of Rome and Computer Technology Institute & Press (CTI)

No abstract available.

ISBN: (纸本)9780994988607

No abstract available.

关键词： Low Power and Lossy Networks Adaptive Protocols algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Multimodal Route and Tour Planning in Urban Environments

Multimodal Route and Tour Planning in Urban Environments

引用

IEEE Symposium on Computers and Communications

作者： Julian Dibbelt Damianos Gavalas Vlasios Kasapakis Charalampos Konstantopoulos Spyros Kontogiannis Grammati Pantziou Dorothea Wagner Christos Zaroliagis Karlsruhe Institute of Technology Karlsruhe Germany Dept of Informatics University of Piraeus Patras Greece Dept of Product & Systems Design Engineering University of the Aegean Patras Greece Dept of Computer Science & Engineering University of Ioannina Patras Greece Dept of Computer Engineering & Informatics University of Patras Patras Greece Dept of Cultural Technology & Communication University of the Aegean Patras Greece Dept of Informatics Technological Educational Institution of Athens Patras Greece

The environmental impact of the steadily increasing demand for mobility of people and goods, especially in urban environments, raises public concern and presents challenges that need to be addressed in the interest of long-term sustainability. Along this line, the inherently eco-friendly human mobility which involves the use of urban public transit networks must be encouraged and eased. This necessitates the development of context-aware services that hide the complexity of public transit networks while considering all available transportation modalities (e.g. bus, metro, tram, walking and cycling) in order to provide sophisticated route planning tailored to both residents and visitors of urban areas. The EU-funded eCOMPASS research project has addressed this challenge through establishing a methodological framework for route planning optimization. A core objective of the project has been to employ novel algorithm engineering approaches for delivering a comprehensive set of tools and services (accessible from web/mobile application interfaces) for mobile end users to enable eco-awareness in urban multi-modal transfers. eCOMPASS delivered web and mobile services providing multi-modal public transportation route planning, considering contextual information as well as various restrictions and/or user constraints. Herein, we report the motivation, main scientific innovations and present the end-products of eCOMPASS with respect to multimodal human mobility.

关键词： Multimodal route planning Tourist tour planning algorithm engineering Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：