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

34th ACM/SIGAPP Annual International Symposium on Applied Computing (SAC)

作者： Moutafis, Panagiotis Garcia-Garcia, Francisco Mavrommatis, George Vassilakopoulos, Michael Corral, Antonio Iribarne, Luis Univ Thessaly Dept Elect & Comp Engn Data Structuring & Engn Lab Volos Greece Univ Almeria Dept Informat Almeria Spain

ISBN: (纸本)9781450359337

Given two datasets of points (called Query and Training), the Group (K) Nearest Neighbor (GNN) query retrieves (K) points of the Training dataset with the smallest sum of distances to every point of the Query one. This spatial query has been studied during the recent years and several performance improving techniques and pruning heuristics have been proposed. But this is the first time a parallel and distributed algorithm, using the mapreduce programming framework, is ever used. In this work, we present a multi phased algorithm, consisting of alternating local and parallel phases, which can be used to effectively process the GNN query when the Query dataset fits in memory, but the Training one belongs to the Big Data category. We make use of some of the pruning heuristics and effective calculation techniques of the literature, as well as different indexing methods and finally perform some comparative benchmarks with several datasets.

关键词： Spatial query processing Group nearest-neighbor query mapreduce algorithms

来源：评论

学校读者我要写书评

暂无评论

Extending Standard mapreduce algorithms 2

Extending Standard MapReduce Algorithms

引用

2nd IEEE International Conference on Multimedia Big Data (BigMM)

作者： Hashem, Hadi Ranc, Daniel Telecom SudParis Inst Mines Telecom LOR Software Networks Dept Rue Charles Fourier 9 F-91011 Evry France

ISBN: (纸本)9781509021796

The information rate nowadays is expanding very quickly and contains complex and heterogeneous data types (text, images, videos, GPS data, purchase transactions...) that require powerful computing engines, able to easily store and process such complex structures. Gartner's definition of the 3Vs (volume, velocity, variety) describing this expansion of data will then lead to extract the unnamed forth V (value) from BigData. This added value addresses the need for valuation of enterprise data. In this paper, we discuss the existing mapreduce implementation techniques and the need of a different approach based on the pre-processing of the data. The goal is to show interesting results in terms of data processing costs, performance and green computing.

关键词： mapreduce algorithms Pre-Processing Data Modeling BigData Tools

来源：评论

学校读者我要写书评

暂无评论

Efficient Processing of Skyline Queries Using mapreduce

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2017年第5期29卷 1031-1044页

作者： Park, Yoonjae Min, Jun-Ki Shim, Kyuseok Seoul Natl Univ Dept Elect & Comp Engn Kwanak POB 34 Seoul 151600 South Korea Korea Univ Technol & Educ Sch Comp Sci & Engn Cheonan 330708 Chungnam South Korea

The skyline operator has attracted considerable attention recently due to its broad applications. However, computing a skyline is challenging today since we have to deal with big data. For data-intensive applications, the mapreduce framework has been widely used recently. In this paper, we propose the efficient parallel algorithm SKY-MR+ for processing skyline queries using mapreduce. We first build a quadtree-based histogram for space partitioning by deciding whether to split each leaf node judiciously based on the benefit of splitting in terms of the estimated execution time. In addition, we apply the dominance power filtering method to effectively prune non-skyline points in advance. We next partition data based on the regions divided by the quadtree and compute candidate skyline points for each partition using mapreduce. Finally, we check whether each skyline candidate point is actually a skyline point in every partition using mapreduce. We also develop the workload balancing methods to make the estimated execution times of all available machines to be similar. We did experiments to compare SKY-MR+ with the state-of-the-art algorithms using mapreduce and confirmed the effectiveness as well as the scalability of SKY-MR+.

关键词： Skyline queries mapreduce algorithms distributed and parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Distributed k-Clique Mining for Large Networks Using mapreduce

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第3期33卷 964-974页

作者： Shahrivari, Saeed Jalili, Saeed Tarbiat Modares Univ Tehran 14115111 Iran

Mining cliques of a network is an important problem that has many applications in different fields like social networks, bioinformatics, and web analysis. In most applications, mining fixed sized cliques, known as k-cliques, is enough. However, mining cliques of a large network is very challenging using current solutions, and it takes a considerable time using a commodity machine. Also, very large networks cannot be efficiently loaded into memory of a single machine. To overcome these limitations, we have proposed a solution named KCminer, which is based on state space search and can be totally fitted into the mapreduce framework. Using the mapreduce framework, it is possible to run KCminer on cloud computing platforms and hence, process very large networks in feasible time. Our experiments which were performed on a cloud computing platform with 100 machines show that KCminer is both fast and scalable. Besides the mapreduce framework, KCminer executes efficiently on parallel shared memory systems. We performed some experiments on a commodity multicore desktop and showed that KCminer can effectively use the power of all cores. The experimental results show that even using a single thread, KCminer is much faster than available serial tools like MACE.

关键词： Cloud computing Data mining Memory management Task analysis Social networking (online) Bioinformatics Multicore processing k-clique mining mapreduce algorithms parallel graph

来源：评论

学校读者我要写书评

暂无评论

Security and privacy aspects in mapreduce on clouds: A survey

引用

COMPUTER SCIENCE REVIEW 2016年第0期20卷 1-28页

作者： Derbeko, Philip Dolev, Shlomi Gudes, Ehud Sharma, Shantanu EMC Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

mapreduce is a programming system for distributed processing of large-scale data in an efficient and fault tolerant manner on a private, public, or hybrid cloud. mapreduce is extensively used daily around the world as an efficient distributed computation tool for a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and analysis of social networks. Security and privacy of data and mapreduce computations are essential concerns when a mapreduce computation is executed in public or hybrid clouds. In order to execute a mapreduce job in public and hybrid clouds, authentication of mappers-reducers, confidentiality of data-computations, integrity of data-computations, and correctness-freshness of the outputs are required. Satisfying these requirements shields the operation from several types of attacks on data and mapreduce computations. In this paper, we investigate and discuss security and privacy challenges and requirements, considering a variety of adversarial capabilities, and characteristics in the scope of mapreduce. We also provide a review of existing security and privacy protocols for mapreduce and discuss their overhead issues. (C). 2016 Elsevier Inc. All rights reserved.

关键词： Cloud computing Distributed computing Hadoop HDFS Hybrid cloud Private cloud Public cloud mapreduce algorithms Privacy Security

来源：评论

学校读者我要写书评

暂无评论

algorithms for processing the group K nearest-neighbor query on distributed frameworks

引用

DISTRIBUTED AND PARALLEL DATABASES 2021年第3期39卷 733-784页

作者： Moutafis, Panagiotis Garcia-Garcia, Francisco Mavrommatis, George Vassilakopoulos, Michael Corral, Antonio Iribarne, Luis Univ Thessaly Dept Elect & Comp Engn Data Struct & Engn Lab Volos Greece Univ Almeria Dept Informat Almeria Spain

Given two datasets of points (called Query and Training), the Group (K) Nearest-Neighbor (GKNN) query retrieves (K) points of the Training with the smallest sum of distances to every point of the Query. This spatial query has been studied during the recent years and several performance improving techniques and pruning heuristics have been proposed. In previous work, we presented the first mapreduce algorithm, consisting of alternating local and parallel phases, which can be used to effectively process the GKNN query when the Query fits in memory, while the Training one belongs to the Big Data category. In this paper, we present a significantly improved algorithm that incorporates a new high-performance refining method, a fast way to calculate distance sums for pruning purposes and several other minor coding and algorithmic improvements. Moreover, we transform this algorithm (which has been implemented in the Hadoop framework) to SpatialHadoop (a popular distributed framework that is dedicated to spatial processing), using a novel two-level partitioning method. Using real world and synthetic datasets, we also present a thorough experimental study of the Hadoop and SpatialHadoop versions of the algorithm, including a backstage analysis of the algorithm's performance, using metrics that highlight its internal functioning. Finally, we present an experimental comparison of the Hadoop, the SpatialHadoop versions and the version of our previous work, showing that the improved versions are the big winners, with the SpatialHadoop one being faster than its Hadoop counterpart.

关键词： Spatial query processing Group nearest-neighbor query mapreduce algorithms Hadoop SpatialHadoop

来源：评论

学校读者我要写书评

暂无评论

BigFCM: Fast, precise and scalable FCM on hadoop

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2017年 77卷 29-39页

作者： Ghadiri, Nasser Ghaffari, Meysam Nikbakht, Mohammad Amin Isfahan Univ Technol Dept Elect & Comp Engn Esfahan Iran Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA

Clustering plays an important role in mining big data both as a modeling technique and a preprocessing step in many data mining process implementations. Fuzzy clustering provides more flexibility than non fuzzy methods by allowing each data record to belong to more than one cluster to some degree. However, a serious challenge in fuzzy clustering is the lack of scalability. Massive datasets in emerging fields such as geosciences, biology, and networking do require parallel and distributed computations with high performance to solve real-world problems. Although some clustering methods are already improved to execute on big data platforms, their execution time is highly increased for gigantic datasets. In this paper, a scalable Fuzzy C-Means (FCM) clustering method named BigFCM is proposed and designed for the Hadoop distributed data platform. Based on the mapreduce programming model, the proposed algorithm exploits several mechanisms including an efficient caching design to achieve several orders of magnitude reduction in execution time. The BigFCM performance compared with Apache Mahout K-Means and Fuzzy K-Means through an evaluation framework developed in this research. Extensive evaluation using over multi-gigabyte datasets including SUSY and HIGGS shows that BigFCM is scalable while it preserves the quality of clustering. (C) 2017 Elsevier B.V. All rights reserved.

关键词： mapreduce algorithms Unsupervised learning and clustering Data mining Clustering Vagueness and fuzzy logic Big data

来源：评论

学校读者我要写书评

暂无评论

Assignment Problems of Different-Sized Inputs in mapreduce

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2016年第2期11卷 18-18页

作者： Afrati, Foto Dolev, Shlomi Korach, Ephraim Sharma, Shantanu Ullman, Jeffrey D. Natl Tech Univ Athens Sch Elect & Comp Engn Zografos 15780 Greece Ben Gurion Univ Negev Beer Sheva Israel Stanford Univ Dept Comp Sci Stanford CA 94305 USA Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

A mapreduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have a capacity that limits the sets of inputs they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any mapreduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which each input of a list, X, is required to meet each input of another list, Y, in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.

关键词： Distributed computing mapping schema mapreduce algorithms reducer capacity and reducer capacity and communication cost trade-off

来源：评论

学校读者我要写书评

暂无评论

An Effective and Efficient mapreduce Algorithm for Computing BFS-Based Traversals of Large-Scale RDF Graphs

引用

algorithms 2016年第1期9卷 7-7页

作者： Cuzzocrea, Alfredo Cosulschi, Mirel de Virgilio, Roberto Univ Trieste DIA Dept I-34127 Trieste Italy ICAR CNR I-34127 Trieste Italy Univ Craiova Dept Comp Sci Craiova 200585 Romania Univ Rome Tre Dipartimento Informat & Automaz I-00146 Rome Italy

Nowadays, a leading instance of big data is represented by Web data that lead to the definition of so-called big Web data. Indeed, extending beyond to a large number of critical applications (e.g., Web advertisement), these data expose several characteristics that clearly adhere to the well-known 3V properties (i.e., volume, velocity, variety). Resource Description Framework (RDF) is a significant formalism and language for the so-called Semantic Web, due to the fact that a very wide family of Web entities can be naturally modeled in a graph-shaped manner. In this context, RDF graphs play a first-class role, because they are widely used in the context of modern Web applications and systems, including the emerging context of social networks. When RDF graphs are defined on top of big (Web) data, they lead to the so-called large-scale RDF graphs, which reasonably populate the next-generation Semantic Web. In order to process such kind of big data, mapreduce, an open source computational framework specifically tailored to big data processing, has emerged during the last years as the reference implementation for this critical setting. In line with this trend, in this paper, we present an approach for efficiently implementing traversals of large-scale RDF graphs over mapreduce that is based on the Breadth First Search (BFS) strategy for visiting (RDF) graphs to be decomposed and processed according to the mapreduce framework. We demonstrate how such implementation speeds-up the analysis of RDF graphs with respect to competitor approaches. Experimental results clearly support our contributions.

关键词： mapreduce algorithms BFS-traversals of RDF graphs effective and efficient algorithms for big data processing

来源：评论

学校读者我要写书评

暂无评论

Randomized Composable Coresets for Matching and Vertex Cover 17

Randomized Composable Coresets for Matching and Vertex Cover

引用

29th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Assadi, Sepehr Khanna, Sanjeev Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

ISBN: (纸本)9781450345934

A common approach for designing scalable algorithms for massive data sets is to distribute the computation across, say k, machines and process the data using limited communication between them. A particularly appealing framework here is the simultaneous communication model whereby each machine constructs a small representative summary of its own data and one obtains an approximate/exact solution from the union of the representative summaries. If the representative summaries needed for a problem are small, then this results in a communication-efficient and round-optimal (requiring essentially no interaction between the machines) protocol. Some well-known examples of techniques for creating summaries include sampling, linear sketching, and composable coresets. These techniques have been successfully used to design communication efficient solutions for many fundamental graph problems. However, two prominent problems are notably absent from the list of successes, namely, the maximum matching problem and the minimum vertex cover problem. Indeed, it was shown recently that for both these problems, even achieving a modest approximation factor of polylog(n) requires using representative summaries of size (Omega) over tilde (n(2)) i.e. essentially no better summary exists than each machine simply sending its entire input graph. The main insight of our work is that the intractability of matching and vertex cover in the simultaneous communication model is inherently connected to an adversarial partitioning of the underlying graph across machines. We show that when the underlying graph is randomly partitioned across machines, both these problems admit randomized composable coresets of size (O) over tilde (n) that yield an (O) over tilde (1)-approximate solution(1). In other words, a small subgraph of the input graph at each machine can be identified as its representative summary and the final answer then is obtained by simply running any maximum matching or minimum vertex cover

关键词： vertex cover randomized composable coresets distributed computing mapreduce algorithms simultaneous communication complexity matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：