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

time-invariant degree growth in preferential attachment network models

Physical Review E 2020年第2期101卷 022309-022309页

作者： Jun Sun (孙骏) Matúš Medo Steffen Staab Institute for Web Science and Technologies Universität Koblenz–Landau 56070 Koblenz Germany Institute of Fundamental and Frontier Sciences University of Electronic Science and Technology of China Chengdu 610054 People's Republic of China Department of Radiation Oncology Inselspital Bern University Hospital and University of Bern 3010 Bern Switzerland and Department of Physics University of Fribourg 1700 Fribourg Switzerland Institute for Parallel and Distributed Systems Universität Stuttgart 70569 Stuttgart Germany and Web and Internet Science Research Group University of Southampton Southampton SO17 1BJ United Kingdom

Preferential attachment drives the evolution of many complex networks. Its analytical studies mostly consider the simplest case of a network that grows uniformly in time despite the accelerating growth of many real networks. Motivated by the observation that the average degree growth of nodes is time invariant in empirical network data, we study the degree dynamics in the relevant class of network models where preferential attachment is combined with heterogeneous node fitness and aging. We propose an analytical framework based on the time invariance of the studied systems and show that it is self-consistent only for two special network growth forms: the uniform and the exponential network growth. Conversely, the breaking of such time invariance explains the winner-takes-all effect in some model settings, revealing the connection between the Bose-Einstein condensation in the Bianconi-Barabási model and similar gelation in superlinear preferential attachment. Aging is necessary to reproduce realistic node degree growth curves and can prevent the winner-takes-all effect under weak conditions. Our results are verified by extensive numerical simulations.

关键词： Degree distributions Network formation & growth Preferential attachment real world networks Barabasi-Albert model Fitness models Preferential attachment models

来源：评论

学校读者我要写书评

暂无评论

Core-sets: An updated survey

引用

WILEY INTERDISCIPLINARY REVIEWS-DATA MINING AND KNOWLEDGE DISCOVERY 2020年第1期10卷 e1335-e1335页

作者： Feldman, Dan Univ Haifa Comp Sci Dept IL-3498838 Haifa Israel

In optimization or machine learning problems we are given a set of items, usually points in some metric space, and the goal is to minimize or maximize an objective function over some space of candidate solutions. For example, in clustering problems, the input is a set of points in some metric space, and a common goal is to compute a set of centers in some other space (points, lines) that will minimize the sum of distances to these points. In database queries, we may need to compute such a some for a specific query set of k centers. However, traditional algorithms cannot handle modern systems that require parallel real-time computations of infinite distributed streams from sensors such as GPS, audio or video that arrive to a cloud, or networks of weaker devices such as smartphones or robots. Core-set is a "small data" summarization of the input "big data," where every possible query has approximately the same answer on both data sets. Generic techniques enable efficient coreset maintenance of streaming, distributed and dynamic data. Traditional algorithms can then be applied on these coresets to maintain the approximated optimal solutions. The challenge is to design coresets with provable tradeoff between their size and approximation error. This survey summarizes such constructions in a retrospective way, that aims to unified and simplify the state-of-the-art. This article is categorized under Algorithmic Development > Structure Discovery Fundamental Concepts of Data and Knowledge > Big Data Mining Technologies > Machine Learning Algorithmic Development > Scalable Statistical Methods

关键词： big data cloud coresets distributed computation streaming

来源：评论

学校读者我要写书评

暂无评论

OCStore: Accelerating distributed Object Storage with Open-Channel SSDs 39

OCStore: Accelerating Distributed Object Storage with Open-C...

引用

39th IEEE International Conference on distributed Computing systems (ICDCS)

作者： Lu, Youyou Zhang, Jiacheng Yang, Zhe Pan, Liyang Shu, Jiwu Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Tsinghua Univ Inst Microelect Beijing Peoples R China

ISBN: (纸本)9781728125190

SSDs are getting widely used in data centers. It is a critical issue to design efficient software for exploiting the benefits of fast SSD hardware. In this paper, we propose OCStore, an object store based on open-channel SSDs for distributed object storage system. OCStore manages the objects directly on raw flash memory, mitigating redundant functions across the object store, the file system, and the FTL layers. It provides streamed transactional update, which not only ensures the multi-page atomicity leveraging the non-overwrite flash write features, but also provides isolation for independent I/O streams while enabling parallel accesses to different channels. OCStore also coordinates different channels to enable transaction-aware scheduling, so as to reduce transaction-level latency and provide low response time to distributed storage. We implement OCStore in Linux kernel on the real open-channel SSDs, and evaluate them as OSDs in Ceph. Evaluations show that OCStore outperforms state-of-the-art object stores by 1.5 x to 3.0 x, while providing much lower and stable latencies, and decreases up to 70% write traffic under heavy workloads.

关键词： distributed storage object store flash memory open-channel SSD

来源：评论

学校读者我要写书评

暂无评论

Contribution to Speeding-Up the Solving of Nonlinear Ordinary Differential Equations on parallel/Multi-Core Platforms for Sensing systems

引用

SENSORS 2020年第21期20卷 6130页

作者： Tavakkoli, Vahid Mohsenzadegan, Kabeh Chedjou, Jean Chamberlain Kyamakya, Kyandoghere Univ Klagenfurt Inst Smart Syst Technol A-9020 Klagenfurt Austria

Solving ordinary differential equations (ODE) on heterogenous or multi-core/parallel embedded systems does significantly increase the operational capacity of many sensing systems in view of processing tasks such as self-calibration, model-based measurement and self-diagnostics. The main challenge is usually related to the complexity of the processing task at hand which costs/requires too much processing power, which may not be available, to ensure a real-time processing. Therefore, a distributed solving involving multiple cores or nodes is a good/precious option. Also, speeding-up the processing does also result in significant energy consumption or sensor nodes involved. There exist several methods for solving differential equations on single processors. But most of them are not suitable for an implementation on parallel (i.e., multi-core) systems due to the increasing communication related network delays between computing nodes, which become a main and serious bottleneck to solve such problems in a parallel computing context. Most of the problems faced relate to the very nature of differential equations. Normally, one should first complete calculations of a previous step in order to use it in the next/following step. Hereby, it appears also that increasing performance (e.g., through increasing step sizes) may possibly result in decreasing the accuracy of calculations on parallel/multi-core systems like GPUs. In this paper, we do create a new adaptive algorithm based on the Adams-Moulton and Parareal method (we call it PAMCL) and we do compare this novel method with other most relevant implementations/schemes such as the so-called DOPRI5, PAM, etc. Our algorithm (PAMCL) is showing very good performance (i.e., speed-up) while compared to related competing algorithms, while thereby ensuring a reasonable accuracy. For a better usage of computing units/resources, the OpenCL platform is selected and ODE solver algorithms are optimized to work on both GPUs and CPUs. This

关键词： ODE Solver OpenCL Parareal parallel multi-core computing sensing systems heterogenous embedded systems

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel optimizations of a high-performance SIFT on GPUs

引用

JOURNAL OF parallel AND distributed COMPUTING 2019年 124卷 78-91页

作者： Li, Zhihao Jia, Haipeng Zhang, Yunquan Liu, Shice Li, Shigang Wang, Xiao Zhang, Hao Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing Peoples R China Univ Chinese Acad Sci Sch Comp & Control Engn Beijing Peoples R China Fudan Univ Shanghai Key Lab Intelligent Informat Proc Shanghai Peoples R China

Stable local image feature detection is a fundamental problem in computer vision and is critical for obtaining the corresponding interest points among images. As a popular and robust feature extraction algorithm, the scale invariant feature transform (SIFT) is widely used in various domains, such as image stitching and remote sensing image registration. However, the computational complexity of SIFT is extremely high, which limits its application in real-time systems and large-scale data processing tasks. Thus, we propose several efficient optimizations to realize a high-performance SIFT (HartSift) by exploiting the computing resources of CPUs and GPUs in a heterogeneous machine. Our experimental results show that HartSift processes an image within 3.07 similar to 7.71 ms, which is 55.88 similar to 121.99 times, 5.17 similar to 6.88 times, and 1.25 similar to 1.79 times faster than OpenCV SIFT, SiftGPU, and CudaSift, respectively. (C) 2018 Elsevier Inc. All rights reserved.

关键词： HartSift SIFT CPU High performance Feature extraction

来源：评论

学校读者我要写书评

暂无评论

HyConv: Accelerating Multi-Phase CNN Computation by Fine-Grained Policy Selection

引用

IEEE TRANSACTIONS ON parallel AND distributed systems 2019年第2期30卷 388-399页

作者： Li, Xiaqing Zhang, Guangyan Wang, Zhufan Zheng, Weimin Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Jilin Univ Minist Educ Key Lab Symbol Computat & Knowledge Engn Changchun 130012 Jilin Peoples R China

Existing GPU-based approaches cannot yet meet the performance requirement for training very large convolutional neural networks (CNNs), where convolutional layers (Conv-layers) dominate the training time. In this paper, we find that no single convolution policy can always perform the fastest across all the computing phases. Then, we propose an approach called HyConv to accelerating multi-phase CNN computation by fine-grained policy selection. HyConv encapsulates existing convolution policies into a set of modules, and selects the fastest policy (a.k.a., winner policy) via one-round runtime measurement for computing each phase. Furthermore, HyConv uses a winner database to record the current winner policies, avoiding duplicate measurement later for the same parameter configuration. Our experimental results indicate that over all the used real-world CNN networks, HyConv consistently outperforms existing approaches on either a single GPU or four GPUs, with speedups of up to 3.3x and up to 1.6x over cuDNN-MM respectively. Such improvement can be explained by our result that HyConv delivers obviously better performance for most of single Conv-layers. Furthermore, HyConv has the ability to work with any parameter configuration and thus keeps better usability.

关键词： Convolution policy convolutional neural network deep learning general-purpose GPU parallel computing

来源：评论

学校读者我要写书评

暂无评论

A scalable and distributed actor-based version of the Node2Vec algorithm 20

A scalable and distributed actor-based version of the Node2V...

引用

20th workshop "From Objects to Agents", WOA 2019

作者： Lombardo, Gianfranco Poggi, Agostino Department of Engineering and Architecture University of Parma Parma Italy

The analysis of systems that can be modeled as networks of interacting entities is becoming often more important in different research fields. The application of machine learning algorithms, like prediction tasks over nodes and edges, requires a manually feature extraction or a learning task to extract them automatically (embedding techniques). Several approaches have been proposed in the last years and the most promising one is represented by the Node2Vec algorithm. However, common limitations of graph embedding techniques are related to memory requirements and to the time complexity. In this paper, we propose a scalable and distributed version of this algorithm called ActorNode2vec, developed on an actor-based architecture that allows to overcome these kind of constraints. We demonstrate the efficacy of this approach with a real large network by analyzing the sensitivity of two algorithm’s parameters (walk length and number of walks) with a comparison with the original algorithm. Results shows an average reduction between the 65% and the 82% in terms of the required computational times. © 2019 CEUR-WS. All rights reserved.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

distributed classification of text streams: Limitations, challenges, and solutions 2019

Distributed classification of text streams: Limitations, cha...

引用

13th International workshop on real-time Business Intelligence and Analytics, BIRTE 2019, in conjunction with the VLDB 2019 Conference

作者： Trofimov, Artem Sokolov, Nikita Shavkunov, Mikhail Kuralenok, Igor Novikov, Boris Saint Petersburg State University JetBrains Research Saint Petersburg Russia ITMO university Saint Petersburg Russia National Research University Higher School of Economics Saint Petersburg Russia Yandex Saint Petersburg Russia

ISBN: (纸本)9781450376600

Text stream classification is an important problem that is difficult to solve at scale. Batch processing systems, widely adopted for text classification tasks, cannot provide for low latency. distributed stream processing systems can offer low latency, but do not support the same level of fault tolerance and determinism as the batch systems. In this work, we demonstrate how the distributed stream processing features can affect the results of a typical text classification data flow. Our analysis shows emerged trade-offs between fault tolerance and reproducibility on the one side, and performance on the other side. We outline potential ways to solve the revealed issues and to handle streaming features. © 2019 Association for Computing Machinery.

关键词： Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Extending a Work-Stealing Framework with Priorities and Weights 9

Extending a Work-Stealing Framework with Priorities and Weig...

引用

9th IEEE/ACM workshop on Irregular Applications - Architectures and Algorithms (IA3)

作者： Nakashima, Ryusuke Yoritaka, Hiroshi Yasugi, Masahiro Hiraishi, Tasuku Umatani, Seiji Kyushu Inst Technol Fukuoka Japan Kyoto Univ Kyoto Japan Kanagawa Univ Yokohama Kanagawa Japan Ad Sol Nissin Corp Tokyo Japan

ISBN: (纸本)9781728159874

This paper proposes priority- and weight-based steal strategies for an idle worker (thief) to select a victim worker in work-stealing frameworks. Typical work-stealing frameworks employ uniformly random victim selection. We implemented the proposed strategies on a work-stealing framework called Tascell;Tascell programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as priorities or weights in the enhanced Tascell framework. To reduce the total task-division cost, the proposed strategies avoid stealing small tasks. With a priority-based strategy, a thief selects the victim that has the highest known priority at that point in time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. The proposed selection strategies outperformed uniformly random victim selection. Our evaluation uses a parallel implementation of the "highly serial" version of the Barnes-Hut force-calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.

关键词： parallel programming languages work stealing priority weight concurrency many-core Barnes-Hut algorithm

来源：评论

学校读者我要写书评

暂无评论

Continuously Distinct Sampling over Centralized and distributed High Speed Data Streams

引用

IEEE TRANSACTIONS ON parallel AND distributed systems 2019年第2期30卷 300-314页

作者： Wang, Pinghui Wang, Xiangyu Tao, Jing Zhang, Peng Guan, Xiaohong Xi An Jiao Tong Univ MOE Key Lab Intelligent Networks & Network Secur POB 108828 Xianning West Rd Xian 710049 Shaanxi Peoples R China Tsinghua Univ Tsinghua Natl Lab Informat Sci & Technol Beijing Peoples R China

Distinct sampling is fundamental for computing statistics (e.g., the age and gender distribution of distinct users accessing a particular website) depending on the set of distinct keys (e.g., user IDs) in a large and high speed data stream such as a sequence of key-update pairs. However, the major shortcoming of existing methods is their high computational cost incurred by determining whether each incoming key in the data stream is currently in the set of sampled keys and keeping track of sampled keys' update aggregations. To solve this challenge, we develop a new method random projection and eviction (RPE) that uses a list of buckets to continuously sample distinct keys and their update aggregations. RPE processes each key-update pair with small and nearly constant time complexity O(1). Besides centralized data streams, we also develop a novel method DRPE to deal with distributed data streams consisting of key-update pairs observed at multiple distributed sites. We conduct extensive experiments on real-world datasets, and the results demonstrate that RPE and DRPE reduce the memory, computational, and message costs of state-of-the-art methods by several times.

关键词： Data stream distinct sampling sketch

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：