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

R-Kleene: A high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks

引用

algorithmICA 2007年第2期47卷 203-213页

作者： D'Alberto, Paolo Nicolau, Alexandru Carnegie Mellon Univ Dept Elect & Comp Sci Pittsburgh PA 15213 USA

We propose a novel divide-and-conquer algorithm for the solution of the all-pair shortest-path problem for directed and dense graphs with no negative cycles. We propose R-Kleene, a compact and in-place recursive algorithm inspired by Kleene's algorithm. R-Kleene delivers a better performance than previous algorithms for randomly generated graphs represented by highly dense adjacency matrices, in which the matrix components can have any integer value. We show that R-Kleene, unchanged and without any machine tuning, yields consistently between (1)/(7) and (1)/(2) of the peak performance running on five very different uniprocessor systems.

关键词： algorithm engineering performance evaluation optimizations

来源：评论

学校读者我要写书评

暂无评论

A privacy-preserving smart parking system using an IoT elliptic curve based security platform

引用

COMPUTER COMMUNICATIONS 2016年 89-90卷 165-177页

作者： Chatzigiannakis, Ioannis Vitaletti, Andrea Pyrgelis, Apostolos Sapienza Univ Rome Dept Comp Control & Management Engn DIAG Rome Italy Comp Technol Inst & Press Diophantus CTI Patras Greece UCL Dept Comp Sci London England

Since the initial visions proposed in the SmartDust project fifteen years ago, Wireless Sensor Networks have seen a tremendous development, leading to the realization of the Internet of Things (IoT). Today, there is a large variety of hardware and software to choose from that is easy to set up and use. Even though there is an increasing number of real-world applications that employ large deployments of IoT devices, the wireless nature of communication in combination with the low-end capabilities of the devices raises security and privacy issues that have not been properly addressed. Considering also that sensor node brands are very different in their capabilities, providing a single solution is very challenging. In this paper we adopt Elliptic Curve Cryptography (ECC) as an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources, i.e., speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. We provide a generic implementation of ECC that runs on different host operating systems, such as Contiki, TinyOS, iSenseOS, ScatterWeb and Arduino. Furthermore, it runs on smartphone platforms such as Android and iPhone and also any linux based systems (e.g., raspberryPi). Our implementation does not contain any platform-specific specializations, allowing a single implementation to run natively on heterogeneous networks. We look into the Smart Parking application domain and provide a solution that protects the privacy of the users by totally avoiding the exchange of confidential information. We also show how to protect a user's privacy by adapting the tool of zero knowledge proofs (ZKP) with our ECC implementation. We study the performance of our system in an real-world outdoor IoT testbed and analyze the exec

关键词： Smart city Privacy Wireless sensor networks algorithm engineering Performance evaluation

来源：评论

学校读者我要写书评

暂无评论

Optimized succinct data structures for massive data

引用

SOFTWARE-PRACTICE & EXPERIENCE 2014年第11期44卷 1287-1314页

作者： Gog, Simon Petri, Matthias Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic 3001 Australia

Succinct data structures provide the same functionality as their corresponding traditional data structure in compact space. We improve on functions rank and select, which are the basic building blocks of FM-indexes and other succinct data structures. First, we present a cache-optimal, uncompressed bitvector representation that outperforms all existing approaches. Next, we improve, in both space and time, on a recent result by Navarro and Providel on compressed bitvectors. Last, we show techniques to perform rank and select on 64-bit words that are up to three times faster than existing methods. In our experimental evaluation, we first show how our improvements affect cache and runtime performance of both operations on data sets larger than commonly used in the evaluation of succinct data structures. Our experiments show that our improvements to these basic operations significantly improve the runtime performance and compression effectiveness of FM-indexes on small and large data sets. To our knowledge, our improvements result in FM-indexes that are either smaller or faster than all current state of the art implementations. Copyright (C) 2013 John Wiley & Sons, Ltd.

关键词： succinct data structures binary sequences FM-index algorithm engineering massive data sets rank select SSE hugepages

来源：评论

学校读者我要写书评

暂无评论

Heap Construction-50 Years Later

引用

COMPUTER JOURNAL 2017年第5期60卷 657-674页

作者： Edelkamp, Stefan Elmasry, Amr Katajainen, Jyrki Univ Bremen Inst Artificial Intelligence Fallturm 1 D-28359 Bremen Germany Univ Alexandria Dept Comp Engn & Syst Alexandria 21544 Egypt Univ Copenhagen Dept Comp Sci Univ Pk 5 DK-2100 Copenhagen East Denmark

We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in- place heap-construction algorithm that runs in Theta(N) worst-case time and performs at most 1.625N+ o(N) element comparisons, 1.5N + o(N) element moves, N/B + O(N/M . lgN) cache misses, and 1.375N+ o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro;however, their algorithm requires Theta(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Theta(N/S) such that each of its leaves root a bottom tree of size Theta(S). When S = Theta(lgN/lglgN), we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd's sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice.

关键词： data structures binary heaps heap construction algorithm engineering element comparisons element moves cache misses branch mispredictions

来源：评论

学校读者我要写书评

暂无评论

Lossless asymmetric single instruction multiple data codec

引用

SOFTWARE-PRACTICE & EXPERIENCE 2012年第9期42卷 1095-1106页

作者： Wassenberg, Jan Fraunhofer IOSB SZA D-76275 Ettlingen Germany

This report introduces a new lossless asymmetric single instruction multiple data codec designed for extremely efficient decompression of large satellite images. A throughput in excess of 3GB/s allows decompression to proceed in parallel with asynchronous transfers from fast block devices such as disk arrays. This is made possible by a simple and fast single instruction multiple data entropy coder that removes leading null bits. Our main contribution is a new approach for vectorized prediction and encoding. Unlike previous approaches that treat the entropy coder as a black box, we account for its properties in the design of the predictor. The resulting compressed stream is 1.2 to 1.5 times as large as JPEG-2000, but can be decompressed 100 times as quickly even faster than copying uncompressed data in memory. Applications include streaming decompression for out of core visualization. To the best of our knowledge, this is the first entirely vectorized algorithm for lossless compression. Copyright (c) 2011 John Wiley & Sons, Ltd.

关键词： lossless compression image compression SIMD algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

An Experimental Study of New and Known Online Packet Buffering algorithms

引用

algorithmICA 2010年第4期57卷 725-746页

作者： Albers, Susanne Jacobs, Tobias Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.

关键词： Packet buffering Network switch Online algorithm Performance analysis algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

algorithms for art gallery illumination

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第1期68卷 23-45页

作者： Ernestus, Maximilian Friedrichs, Stephan Hemmer, Michael Kokemueller, Jan Kroeller, Alexander Moeini, Mahdi Schmidt, Christiane TU Braunschweig Algorithms Grp IBR Muhlenpfordtstr 23 D-38106 Braunschweig Germany Max Planck Inst Informat Saarbrucken Germany Saarbrucken Grad Sch Comp Sci Saarbrucken Germany Tech Univ Kaiserslautern Chair Business Informat Syst & Operat Res BISOR Postfach 3049Erwin Schrodinger Str D-67653 Kaiserslautern Germany Linkoping Univ Commun & Transport Syst ITN Linkoping Sweden

The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.

关键词： Art gallery problem Fading Computational geometry Linear program Non-linear program Lipschitz function algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic update of arc-flags

引用

NETWORKS 2014年第3期63卷 243-259页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Univ Perugia Dept Math & Informat I-06123 Perugia Italy Univ Pisa Dept Comp Sci I-56127 Pisa Italy Univ Aquila Dept Comp Sci Informat Engn & Math I-67100 Laquila Italy

Best connections in real networks are usually found by applying Dijkstra's shortest paths algorithm. Unfortunately, networks deriving from real-world applications are huge, yielding unsustainable times to compute shortest paths. Therefore, considerable research has been conducted in recent years to accelerate Dijkstra's algorithm on typical instances of transportation and communication networks, such as road networks. These efforts have led to the development of many so called speed-up techniques, as for example Arc-Flags. The main drawback of many of these techniques, including Arc-Flags, is that they do not work well in the realistic dynamic scenarios where the networks change over time. In this article, we introduce a new data structure, named Road-Signs, which is used to update the Arc-Flags of a graph in fully dynamic scenarios. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and does not require large space consumption for sparse networks. We develop a fully dynamic algorithm for updating Arc-Flags, by updating Road-Signs, each time that a modification occurs on an edge of the network. We show that this algorithm is better than recomputation from scratch of Arc-Flags in terms of the affected parameters of the input, which makes this solution suitable to be efficient in practice. However, it is not better than recomputation from scratch in the worst case. We also propose an experimental study to evaluate the practical performance of the new dynamic algorithm. To this aim, we use real-world road networks subject to sequences of weight change operations. Our experiments show a significant speed-up in the updating phase with respect to the recomputation from scratch of *** (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 243-259 2014

关键词： speed-up techniques road networks dynamic algorithms arc-flags shortest paths algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Top-k Distance Queries on Large Time-Evolving Graphs

引用

IEEE ACCESS 2023年 11卷 102228-102242页

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

Fast extraction of top- k distances from graph data is a primitive of paramount importance in the fields of data mining, network analytics and machine learning, where ranked distances are exploited for several purposes (e.g., link prediction or network classification). While investigation on computational methods to address this retrieval task for regularly sized, static inputs has been extensive, much less is known when managed graphs are massive, i.e., having millions of vertices/edges, and time-evolving, i.e., when their structure can grow over time, a scenario that introduces a number of scalability and effectiveness issues otherwise not arising. Since, nowadays, most real-world applications exploiting top- k distances have to handle inherently dynamic and rapidly growing graphs, in this paper we present the first dynamic indexing scheme that supports very fast queries on top- k distances when graphs are massive and incrementally time-evolving. We assess the scalability and effectiveness of our method through extensive experimentation on both real-world and artificial graph datasets.

关键词： Heuristic algorithms Data structures Scalability Data mining Labeling Computational modeling Time complexity algorithm design and analysis algorithm engineering dynamic algorithms k shortest distances massive graph mining

来源：评论

学校读者我要写书评

暂无评论

A TALE OF 2 GREPS

引用

SOFTWARE-PRACTICE & EXPERIENCE 1988年第11期18卷 1063-1072页

作者： HUME, A AT & T Bell Laboratories 600 Mountain Avenue Murray Hill NJ 07974 U.S.A.

Text searching programs such as the UNIX system tools grep and egrep require more than just good algorithms; they need to make efficient use of system resources such as I/O. I describe improving the I/O management in grep and egrep by using a new fast I/O library fio to replace the normal I/O library stdio . I also describe incorporating the Boyer-Moore algorithm into egrep ; egrep is now typically 8–10 (for some common patterns 30–40) times faster than grep .

关键词： Pattern matching Tuning Regular expression algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：