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

29th International Conference on Scientifc and Statistical Database Management (SSDBM)

作者： Qin, Chengjie Rusu, Florin GraphSQL Inc Millbrae CA 94030 USA Univ Calif Merced Merced CA USA

ISBN: (纸本)9781450352826

Big Model analytics tackles the training of massive models that go beyond the available memory of a single computing device, e.g., CPU or GPU. It generalizes Big Data analytics which is targeted at how to train memory-resident models over out-of-memory training data. In this paper, we propose an in-database solution for Big Model analytics. We identify dot-product as the primary operation for training generalized linear models and introduce the first array-relation dot-product join database operator between a set of sparse arrays and a dense relation. This is a constrained formulation of the extensively studied sparse matrix vector multiplication (SpMV) kernel. The paramount challenge in designing the dot-product join operator is how to optimally schedule access to the dense relation based on the non-contiguous entries in the sparse arrays. We propose a practical solution characterized by two technical contributions-dynamic batch processing and array reordering. We devise three heuristics - LSH, Radix, and K-center - for array reordering and analyze them thoroughly. We execute extensive experiments over synthetic and real data that confirm the minimal overhead the operator incurs when sufficient memory is available and the graceful degradation it suffers as memory becomes scarce. Moreover, dot-product join achieves an order of magnitude reduction in execution time over alternative solutions.

关键词： Database systems

来源：评论

学校读者我要写书评

暂无评论

Scalable asynchronous gradient descent optimization for out-of-core models 43

Scalable asynchronous gradient descent optimization for out-...

引用

43rd International Conference on Very Large Data Bases, VLDB 2017

作者： Qin, Chengjie Torres, Martin Rusu, Florin GraphSQL Inc. United States University of California Merced United States

Existing data analytics systems have approached predictive model training exclusively from a data-parallel perspective. Data examples are partitioned to multiple workers and training is executed concurrently over different partitions, under various synchronization policies that emphasize speedup or convergence. Since models with millions and even billions of features become increasingly common nowadays, model management becomes an equally important task for effective training. In this paper, we present a general framework for parallelizing stochastic optimization algorithms over massive models that cannot fit in memory. We extend the lockfree HOGWILD!-family of algorithms to disk-resident models by vertically partitioning the model offline and asynchronously updating the resulting partitions online. Unlike HOGWILD!, concurrent requests to the common model are minimized by a preemptive push-based sharing mechanism that reduces the number of disk accesses. Experimental results on real and synthetic datasets show that the proposed framework achieves improved convergence over HOGWILD! and is the only solution scalable to massive models. © 2017 VLDB Endowment.

关键词： Optimization

来源：评论

学校读者我要写书评

暂无评论

From "think like a vertex" to "think like a graph" 40th

From "think like a vertex" to "think like a graph"

引用

Proceedings of the 40th International Conference on Very Large Data Bases, VLDB 2014

作者： Tiany, Yuanyuan Balminx, Andrey Corsten, Severin Andreas Tatikonda, Shirish McPherson, John IBM Almaden Research Center United States GraphSQL United States IBM Deutschland GmbH Germany

To meet the challenge of processing rapidly growing graph and network data created by modern applications, a number of distributed graph processing systems have emerged, such as Pregel and GraphLab. All these systems divide input graphs into partitions, and employ a "think like a vertex" programming model to support iterative graph computation. This vertex-centric model is easy to program and has been proved useful for many graph algorithms. However, this model hides the partitioning information from the users, thus prevents many algorithm-specific optimizations. This often results in longer execution time due to excessive network messages (e.g. in Pregel) or heavy scheduling overhead to ensure data consistency (e.g. in GraphLab). To address this limitation, we propose a new "think like a graph" programming paradigm. Under this graph-centric model, the partition structure is opened up to the users, and can be utilized so that communication within a partition can bypass the heavy message passing or scheduling machinery. We implemented this model in a new system, called Giraph++, based on Apache Giraph, an open source implementation of Pregel. We explore the applicability of the graph-centric model to three categories of graph algorithms, and demonstrate its flexibility and superior performance, especially on well-partitioned data. For example, on a web graph with 118 million vertices and 855 million edges, the graph-centric version of connected component detection algorithm runs 63X faster and uses 204X fewer network messages than its vertex-centric counterpart. © 2013 VLDB Endowment.

关键词： Message passing

来源：评论

学校读者我要写书评

暂无评论

FlowFlex: Malleable scheduling for flows of MapReduce jobs

FlowFlex: Malleable scheduling for flows of MapReduce jobs

引用

14th ACM/IFIP/USENIX Middleware Conference, Middleware 2013

作者： Nagarajan, Viswanath Wolf, Joel Balmin, Andrey Hildrum, Kirsten IBM T. J. Watson Research Center United States GraphSQL United States

ISBN: (纸本)9783642450648

We introduce FlowFlex, a highly generic and effective scheduler for flows of MapReduce jobs connected by precedence constraints. Such a flow can result, for example, from a single user-level Pig, Hive or Jaql query. Each flow is associated with an arbitrary function describing the cost incurred in completing the flow at a particular time. The overall objective is to minimize either the total cost (minisum) or the maximum cost (minimax) of the flows. Our contributions are both theoretical and practical. Theoretically, we advance the state of the art in malleable parallel scheduling with precedence constraints. We employ resource augmentation analysis to provide bicriteria approximation algorithms for both minisum and minimax objective functions. As corollaries, we obtain approximation algorithms for total weighted completion time (and thus average completion time and average stretch), and for maximum weighted completion time (and thus makespan and maximum stretch). Practically, the average case performance of the FlowFlex scheduler is excellent, significantly better than other approaches. Specifically, we demonstrate via extensive experiments the overall performance of FlowFlex relative to optimal and also relative to other, standard MapReduce scheduling schemes. All told, FlowFlex dramatically extends the capabilities of the earlier Flex scheduler for singleton MapReduce jobs while simultaneously providing a solid theoretical foundation for both. © IFIP International Federation for Information Processing 2013.

关键词： MapReduce

来源：评论

学校读者我要写书评

暂无评论

From "Think Like a Vertex" to "Think Like a Graph"

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2013年第3期7卷 193-204页

作者： Tian, Yuanyuan Balmin, Andrey Corsten, Severin Andreas Tatikonda, Shirish McPherson, John IBM Almaden Res Ctr Yorktown Hts NY 10598 USA GraphSQL Redwood City CA 94065 USA IBM Deutschland GmbH Berlin Germany

关键词： Graph theory Iterative methods Machinery Message passing Open source software Open systems Scheduling Connected component Graph algorithms Graph computations Modern applications Open source implementation Partition structures Programming models Programming paradigms

来源：评论

学校读者我要写书评

暂无评论

PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2013年第14期6卷 1678-1689页

作者： Popescut, Adrian Daniel Balmin, Andrey Ercegoyac, Vuk Ailamaki, Anastasia Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland IBM Almaden Res Ctr San Jose CA USA GraphSQL Mountain View CA USA Google Inc Menlo Pk CA USA

Machine learning algorithms are widely used today for analytical tasks such as data cleaning, data categorization, or data filtering. At the same time, the rise of social media motivates recent uptake in large scale graph processing. Both categories of algorithms are dominated by it er a tivesubtasks,i.e., processing steps which are executed repetitively until a convergence condition is met. Optimizing cluster resource allocations among multiple workloads of iterative algorithms motivates the need for estimating their runtime, which in turn requires: i) predicting the number of iterations, and ii) predicting the processing time of each iteration. As both parameters depend on the characteristics of the dataset and on the convergence function, estimating their values before execution is difficult.

关键词： Forecasting

来源：评论

学校读者我要写书评

暂无评论

Scalable Topic-Specific Influence Analysis on Microblogs 14

Scalable Topic-Specific Influence Analysis on Microblogs

引用

7th ACM International Conference on Web Search and Data Mining (WSDM)

作者： Bi, Bin Tian, Yuanyuan Sismanis, Yannis Balmin, Andrey Cho, Junghoo Univ Calif Los Angeles Los Angeles CA 90024 USA IBM Almaden Res Ctr San Jose CA USA Google Mountain View CA USA GraphSQL San Francisco CA USA

ISBN: (纸本)9781450323512

Social influence analysis on microblogs, such as Twitter, has been playing a crucial role in online advertising and brand management. While most previous influence analysis schemes rely only on the links between users to find key influencers, they omit the important text content created by the users. As a result, there is no way to differentiate the social influence in different aspects of life (topics). Although a few prior works do support topic-specific influence analysis, they either separate the analysis of content from that of network structure, or assume that content is the only cause of links, which is clearly an inappropriate assumption for microblog networks. To address the limitations of the previous approaches, we propose a novel Followship-LDA (FLDA) model, which integrates both content topic discovery and social influence analysis in the same generative process. This model properly captures the content-related and content-independent reasons why a user follows another in a microblog network. We demonstrate that FLDA produces results with significantly better precision than existing approaches. Furthermore, we propose a distributed Gibbs sampling algorithm for FLDA, and demonstrate that it provides excellent scalability on large clusters. Finally, we incorporate the FLDA model in a general search framework for topic-specific influencers. A user freely expresses his/her interest by typing a few keywords, the search framework will return a ranked list of key influencers that satisfy the user's interest.

关键词： social influence analysis

来源：评论

学校读者我要写书评

暂无评论

Dynamically Optimizing Queries over Large Scale Data Platforms 14

Dynamically Optimizing Queries over Large Scale Data Platfor...

引用

ACM SIGMOD International Conference on Management of Data

作者： Karanasos, Konstantinos Balmin, Andrey Kutsch, Marcel Ozcan, Fatma Ercegovac, Vuk Xia, Chunyang Jackson, Jesse IBM Res Almaden San Jose CA 95120 USA GraphSQL Millbrae CA USA Apple Inc Cupertino CA USA Google Mountain View CA USA IBM Silicon Valley Lab San Jose CA USA IBM Res San Jose CA USA

ISBN: (纸本)9781450323765

Enterprises are adapting large-scale data processing platforms, such as Hadoop, to gain actionable insights from their "big data". Query optimization is still an open challenge in this environment due to the volume and heterogeneity of data, comprising both structured and un/semi-structured datasets. Moreover, it has become common practice to push business logic close to the data via user defined functions (UDFs), which are usually opaque to the optimizer, further complicating cost-based optimization. As a result, classical relational query optimization techniques do not fit well in this setting, while at the same time, suboptimal query plans can be disastrous with large datasets. In this paper, we propose new techniques that take into account UDFs and correlations between relations for optimizing queries running on large scale clusters. We introduce "pilot runs", which execute part of the query over a sample of the data to estimate selectivities, and employ a cost-based optimizer that uses these selectivities to choose an initial query plan. Then, we follow a dynamic optimization approach, in which plans evolve as parts of the queries get executed. Our experimental results show that our techniques produce plans that are at least as good as, and up to 2x (4x) better for Jaql (Hive) than, the best hand-written left-deep query plans.

关键词： query optimization large-scale data platforms adaptive query processing pilot runs

来源：评论

学校读者我要写书评

暂无评论

Scalable Asynchronous Gradient Descent Optimization for Out-of-Core Models

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2017年第10期10卷 986-997页

作者： Qin, Chengjie Torres, Martin Rusu, Florin Univ Calif Merced Merced CA USA GraphSQL Inc Redwood City CA 94065 USA

Existing data analytics systems have approached predictive model training exclusively from a data-parallel perspective. Data examples are partitioned to multiple workers and training is executed concurrently over different partitions, under various synchronization policies that emphasize speedup or convergence. Since models with millions and even billions of features become increasingly common nowadays, model management becomes an equally important task for effective training. In this paper, we present a general framework for parallelizing stochastic optimization algorithms over massive models that cannot fit in memory. We extend the lock-free HOGWILD!-family of algorithms to disk-resident models by vertically partitioning the model offline and asynchronously updating the resulting partitions online. Unlike HOGWILD!, concurrent requests to the common model are minimized by a preemptive push-based sharing mechanism that reduces the number of disk accesses. Experimental results on real and synthetic datasets show that the proposed framework achieves improved convergence over HOGWILD! and is the only solution scalable to massive models.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Uniform-scale assessment of role minimization in bipartite networks and its application to access control

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2018年 507卷 381-397页

作者： Wu, Liuyi Dong, Lijun Wang, Yi Zhang, Feng Lee, Victor E. Kang, Xiaojun Liang, Qingzhong China Univ Geosci Sch Comp Sci Wuhan 430074 Hubei Peoples R China China Univ Geosci Hubei Key Lab Intelligent Geoinformat Proc Wuhan 430074 Hubei Peoples R China China Univ Geosci Sch Math & Phys Wuhan 430074 Hubei Peoples R China GraphSQL Inc Mountain View CA 94043 USA

As an important kind of complex network models, bipartite network is widely used in many applications such as access control. The process of finding a set of structural communities in a bipartite network is called role mining, which has been extensively used to automatically generate roles for structural communities. Role minimization, aiming to get the fewest roles to reduce the administrative complexity of the access control, is the simplest and most popular form of role mining. Current assessment metrics of role minimization results are based on the absolute values, and cannot measure or compare the results from different algorithms and different datasets on a uniform scale. To address this problem, this study proposes a framework of mark-based evaluation for role minimization (MERM) to provide a normalized measure for different role minimization results on a uniform scale. According to MERM, for each dataset, three quantitative reference marks are established to mirror the level of role minimization results. The marks are entirely determined by the inherent features of a dataset but have nothing to do with any role mining algorithm. Based on the marks, a normalized score vector is constructed to estimate the performance of results, independent of the size of any dataset. MERM can assess varieties of role minimization results on a uniform scale. The experimental results show the effectiveness of MERM: the different results generated from nine algorithms on six datasets can be measured on a uniform scale. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Complex network Bipartite network Access control Role mining Role minimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：