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

2019中国信息产业创新发展大会

作者： QILIAN YU LI XU SHUGUANG CUI Department of Electrical and Computer Engineering University of California at DavisDavisCA 95616U Institute of Computing Technology Chinese Academy of SciencesBeijing 100190China

Submodular optimization plays a significant role in combinatorial problems,since it captures the structure of the edge cuts in graphs,the coverage of sets,and so *** data mining and machine learning problems can be cast as submodular maximization problems with applications in recommendation systems and data *** this paper,we focus on the problem of maximizing a monotone submodular function subject to a d-knapsack constraint,for which we propose a streaming algorithm that achieves a((1/1+2d)-e)-approximation of the optimal value,while it only needs one single pass through the data set without storing all the data in the *** our experiments,we extensively evaluate the effectiveness of our proposed algorithm via two applications:news recommendation and scientific literature *** is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude,compared with existing approaches.

关键词： Submodular optimization streaming algorithm news recommendation scientific literature recommendation

来源：评论

学校读者我要写书评

暂无评论

Static and streaming Data Structures for Frechet Distance Queries

引用

ACM TRANSACTIONS ON algorithmS 2023年第4期19卷 1-36页

作者： Filtser, Arnold Filtser, Omrit Bar Ilan Univ Dept Comp Sci Bldg 503Room 307 IL-5290002 Ramat Gan Israel Open Univ Israel Dept Math & Comp Sci Derekh Ha Univ 1 IL-4353701 Raanana Israel

Given a curve P with points in R-d in a streaming fashion, and parameters epsilon > 0 andk, we construct a distance oracle that uses O(1/epsilon)(kd) log epsilon(-1) space, and given a query curve Q with k points in R-d returns in (O) over tilde (kd) time a 1 + epsilon approximation of the discrete Frechet distance between Q and P. In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension d, and therefore we generalize some useful tools and algorithms for curves under the discrete Frechet distance to work efficiently in high dimensions.

关键词： Frechet distance distance oracle streaming algorithm simplification high dimension the "zoom in" problem

来源：评论

学校读者我要写书评

暂无评论

Sequence submodular maximization meets streaming

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第1期41卷 43-55页

作者： Yang, Ruiqi Xu, Dachuan Guo, Longkun Zhang, Dongmei Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Qilu Univ Technol Shandong Acad Sci Sch Comp Sci & Technol Shandong Key Lab Comp Networks Jinan 250353 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

In this paper, we study the problem of maximizing a sequence submodular function in the streaming setting, where the utility function is defined on sequences instead of sets of elements. We encode the sequence submodular maximization with a weighted digraph, in which the weight of a vertex reveals the utility value in selecting a single element and the weight of an edge reveals the additional profit with respect to a certain selection sequence. The edges are visited in a streaming fashion and the aim is to sieve a sequence of at most k elements from the stream, such that the utility is maximized. In this work, we present an edge-based threshold procedure, which makes one pass over the stream, attains an approximation ratio of (1/(2 Delta+ 1) - O(epsilon)), consumes O(k Delta/epsilon) memory source in total and O(log(k Delta)/epsilon) update time per edge, where. is the minimum of the maximal outdegree and indegree of the directed graph.

关键词： Submodular maximization Sequence streaming algorithm Threshold

来源：评论

学校读者我要写书评

暂无评论

Parallel and streaming Truth Discovery in Large-Scale Quantitative Crowdsourcing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2016年第10期27卷 2984-2997页

作者： Ouyang, Robin Wentao Kaplan, Lance M. Toniolo, Alice Srivastava, Mani Norman, Timothy J. Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing Peoples R China US Army Res Lab Networked Sensing Fus Branch Adelphi MD 20783 USA Univ Aberdeen Dept Comp Sci Aberdeen Scotland Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90024 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA

To enable reliable crowdsourcing applications, it is of great importance to develop algorithms that can automatically discover the truths from possibly noisy and conflicting claims provided by various information sources. In order to handle crowdsourcing applications involving big or streaming data, a desirable truth discovery algorithm should not only be effective, but also be scalable. However, with respect to quantitative crowdsourcing applications such as object counting and percentage annotation, existing truth discovery algorithms are not simultaneously effective and scalable. They either address truth discovery in categorical crowdsourcing or perform batch processing that does not scale. In this paper, we propose new parallel and streaming truth discovery algorithms for quantitative crowdsourcing applications. Through extensive experiments on real-world and synthetic datasets, we demonstrate that 1) both of them are quite effective, 2) the parallel algorithm can efficiently perform truth discovery on large datasets, and 3) the streaming algorithm processes data incrementally, and it can efficiently perform truth discovery both on large datasets and in data streams.

关键词： Crowdsourcing truth discovery quantitative task big data parallel algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Better streaming algorithms for clustering problems 03

Better streaming algorithms for clustering problems

引用

Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

作者： Moses Charikar Liadan O'Callaghan Rina Panigrahy Princeton University Stanford University Cisco Systems

ISBN: (纸本)9781581136746

We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k--Median problem which produces a constant factor approximation in one pass using storage space O(k poly log n). This is a significant improvement of the previous best algorithm which yielded a 2O(1/ε) approximation using O(nε) space. Next we give a streaming algorithm for the k--Median problem with an arbitrary distance function. We also study algorithms for clustering problems with outliers in the streaming model. Here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.

关键词： clustering k-median streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming submodular maximization under d-knapsack constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-21页

作者： Chen, Zihan Liu, Bin Du, Hongmin W. Ocean Univ China Sch Math Sci Qingdao 266100 Peoples R China Rutgers State Univ Accounting & Informat Syst Dept Piscataway NJ USA

Submodular optimization is a key topic in combinatorial optimization, which has attracted extensive attention in the past few years. Among the known results, most of the submodular functions are defined on set. But recently some progress has been made on the integer lattice. In this paper, we study two problem of maximizing submodular functions with d-knapsack constraints. First, for the problem of maximizing DR-submodular functions with d-knapsack constraints on the integer lattice, we propose a one pass streaming algorithm that achieves a 1-theta/1+d-approximation with (log(d beta(-1))/beta epsilon) memory complexity and (log(d beta(-1))/epsilon) log (sic)b(sic)(infinity)) update time per element, where theta = min(alpha + epsilon, 0.5 + epsilon) and alpha, beta are the upper and lower bounds for the cost of each item in the stream. Then we devise an improved streaming algorithm to reduce the memory complexity to O (d/beta epsilon) with unchanged approximation ratio and query complexity. Then for the problem of maximizing submodular functions with d-knapsack constraints under noise, we design a one pass streaming algorithm. When epsilon -> 0, it achieves a 1/1-alpha+d-approximate ratio, memory complexity O ( log(d beta(-1))/beta epsilon) and query complexity O (log(d beta(-1))/epsilon) per element. As far as we know, these two are the first streaming algorithms under their corresponding problems.

关键词： streaming algorithm d-Knapsack constraints Integer lattice Noise

来源：评论

学校读者我要写书评

暂无评论

The Space Complexity of Recognizing Well-Parenthesized Expressions in the streaming Model: The Index Function Revisited

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第10期60卷 6646-6668页

作者： Jain, Rahul Nayak, Ashwin Natl Univ Singapore Dept Comp Sci Ctr Quantum Technol Singapore 117543 Singapore Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada

We show an Omega (root n/T) lower bound for the space required by any unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak (2009) and rigorously establishes that bidirectional streams are exponentially more efficient in space usage as compared with unidirectional ones. We obtain the lower bound by analyzing the information that is necessarily revealed by the players about their respective inputs in a two-party communication protocol for a variant of the index function, namely augmented index. We show that in any communication protocol that computes this function correctly with constant error on the uniform distribution (a "hard" distribution), either Alice reveals Omega(n) information about her n-bit input, or Bob reveals Omega(1) information about his (log n)-bit input, even when the inputs are drawn from an "easy" distribution, the uniform distribution over inputs that evaluate to 0. The information cost tradeoff is obtained by a novel application of the conceptually simple and familiar ideas, such as average encoding and the cut-and-paste property, of randomized protocols. Motivated by recent examples of exponential savings in space by streaming quantum algorithms, we also study quantum protocols for augmented index. Defining an appropriate notion of information cost for quantum protocols involves a delicate balancing act between its applicability and the ease with which we can analyze it. We define a notion of quantum information cost, which reflects some of the nonintuitive properties of quantum information. We show that in quantum protocols that compute the augmented index function correctly with constant error on the uniform distribution, either Alice reveals Omega (n/t) information about her n-bit input, or Bob reveals Omega (1/t) information about his (log n)-bit input, where t is the number of

关键词： streaming algorithm space complexity Dyck language communication complexity information cost augmented index quantum information theory quantum communication

来源：评论

学校读者我要写书评

暂无评论

Discriminative streaming Network Embedding

引用

KNOWLEDGE-BASED SYSTEMS 2020年 190卷 105138-105138页

作者： Qi, Yiyan Cheng, Jiefeng Chen, Xiaojun Cheng, Reynold Bifet, Albert Wang, Pinghui Xi An Jiao Tong Univ NSKEYLAB Xian Peoples R China AI Secur Lab Tencent Shenzhen Peoples R China Shenzhen Univ Coll Comp Sci & Software Shenzhen Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Paris Saclay Telecom ParisTech LTCI St Aubin France Xi An Jiao Tong Univ Shenzhen Res Sch Shenzhen Peoples R China

Many real-world networks (e.g., friendship network among Facebook users) generate data (e.g., friend requests) in a stream fashion. Recently, several network embedding methods are proposed to learn embeddings on such networks incrementally. However, these methods perform incremental updates in a heuristic manner and thus fail to quantitatively restrict the differences between incremental learning and direct learning on the entire network (i.e., the batch learning). Moreover, they ignore the node labels (e.g., interests) when learning node embeddings, which undermines the performance of network embeddings for applications such as node classification. To solve this problem, in this paper we propose a novel network embedding framework, Discriminative streaming Network Embedding (DimSim). When an edge insertion/deletion occurs, DimSim fast learns node embeddings incrementally, which is desired for many online applications such as anomaly detection. With the incremental learning method, at any time, the objective function well approximates to that of batch learning on the current snapshot. More importantly, the average amount of updating operations of DimSim for processing each newly coming edge is aboutO(n(1-lambda)) , where lambda is constant between 1 and 2 and n is the number of nodes. As a result, DimSim can be increasingly fast as the network grows, which adheres to the intuition that an edge insertion/deletion has a smaller impact on larger networks. In addition, we also utilize node label information to learn discriminative node embeddings and we deliberately design a new model to automatically trade-off the node-specific importance of topology and label information. Extensive experiments on real-world streaming networks show that our method DimSim is up to 50 times faster and 40% more accurate than the state-of-the-arts. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Network embedding streaming algorithm Discriminative model

来源：评论

学校读者我要写书评

暂无评论

streaming Approach to Quadratic Covariation Estimation Using Financial Ultra-High-Frequency Data

引用

COMPUTATIONAL ECONOMICS 2023年第1期62卷 463-485页

作者： Holy, Vladimir Tomanova, Petra Prague Univ Econ & Business Dept Econometr Winston Churchill Sq 1938-4 Prague 13067 3 Czech Republic

We investigate the computational issues related to the memory size in the estimation of quadratic covariation, taking into account the specifics of financial ultra-high-frequency data. In multivariate price processes, we consider both contamination by the market microstructure noise and the non-synchronicity of the observations. We formulate a multi-scale, flat-top realized kernel, non-flat-top realized kernel, pre-averaging and modulated realized covariance estimators in quadratic form and fix their bandwidth parameter at a constant value. This allows us to operate with limited memory and formulate this estimation as a streaming algorithm. We compare the performance of the estimators with fixed bandwidth parameter in a simulation study. We find that the estimators ensuring positive semidefiniteness require much higher bandwidth than the estimators without this constraint.

关键词： Ultra-high-frequency data Market microstructure noise Quadratic covariation streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-Rank Tucker Approximation of a Tensor from streaming Data

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2020年第4期2卷 1123-1150页

作者： Sun, Yiming Guo, Yang Luo, Charlene Tropp, Joel Udell, Madeleine Cornell Univ Dept Stat & Data Sci Ithaca NY 14853 USA Univ Wisconsin Madison Dept Comp Sci Madison WI 53706 USA Columbia Univ New York NY 10027 USA CALTECH Dept Comp Math Sci Pasadena CA 91125 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that the algorithm produces useful results that improve on the state-of-the-art for streaming Tucker decomposition.

关键词： Tucker decomposition tensor compression dimension reduction sketching method randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：