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

approximate Kernel Selection via Matrix Approximation

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2020年第11期31卷 4881-4891页

作者： Ding, Lizhong Liao, Shizhong Liu, Yong Liu, Li Zhu, Fan Yao, Yazhou Shao, Ling Gao, Xin Incept Inst Artificial Intelligence IIAI Abu Dhabi U Arab Emirates Tianjin Univ Sch Comp Sci & Technol Tianjin 300350 Peoples R China Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Peoples R China King Abdullah Univ Sci & Technol KAUST Computat Biosci Res Ctr CBRC Thuwal 23955 Saudi Arabia

Kernel selection is of fundamental importance for the generalization of kernel methods. This article proposes an approximate approach for kernel selection by exploiting the approximability of kernel selection and the computational virtue of kernel matrix approximation. We define approximate consistency to measure the approximability of the kernel selection problem. Based on the analysis of approximate consistency, we solve the theoretical problem of whether, under what conditions, and at what speed, the approximate criterion is close to the accurate one, establishing the foundations of approximate kernel selection. We introduce two selection criteria based on error estimation and prove the approximate consistency of the multilevel circulant matrix (MCM) approximation and Nystr m approximation under these criteria. Under the theoretical guarantees of the approximate consistency, we design approximate algorithms for kernel selection, which exploits the computational advantages of the MCM and Nystr m approximations to conduct kernel selection in a linear or quasi-linear complexity. We experimentally validate the theoretical results for the approximate consistency and evaluate the effectiveness of the proposed kernel selection algorithms.

关键词： Kernel Approximation algorithms Complexity theory Matrix decomposition Task analysis Learning systems Error analysis approximate algorithms approximate consistency kernel matrix approximation kernel selection

来源：评论

学校读者我要写书评

暂无评论

A succinct and approximate greedy algorithm for the Minimum Set Cover Problem

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2024年 81卷

作者： Delgado, Jorge Ferrada, Hector Navarro, Cristobal A. Univ Austral Chile Inst Informat Valdivia Chile

The Minimum Set Cover Problem (MSCP) is a combinatorial optimization problem belonging to the NP- Hard class in computer science. For this reason, there is no algorithm that in the worst case ensures finding an optimal solution in polynomial-time. For a given universe X , the popular greedy heuristic, called Greedy-SetCover, is the main theoretical contribution to obtain an approximate solution for the MSCP in polynomial-time, offering an optimal approximate ratio of (ln |X| + 1) . In this article, we propose an approximate algorithm for MSCP within a succinct representation of the input dataset, whose empirical performance improves Greedy-SetCover both in quality and execution time, while offering the same optimal approximation ratio for the problem. Our experiments show that the proposed algorithm is magnitudes of times faster than the aforementioned greedy one, obtaining on average a cardinality much closer to the optimal solution. Furthermore, because we work on a succinct representation that allows us to compute operations between sets using bitwise operators, we can process much larger datasets than state-of-the-art solutions. As a result, our proposal is also a suitable alternative for processing large datasets as required by the current Big Data era.

关键词： Combinatorial optimization Set cover NP-Hard Greedy algorithms approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

An approximate Algorithm for Maximum Inner Product Search over Streaming Sparse Vectors

引用

ACM TRANSACTIONS ON INFORMATION SYSTEMS 2024年第2期42卷 1-43页

作者： Bruch, Sebastian Nardini, Franco Maria Ingber, Amir Liberty, Edo Pinecone New York NY 10018 USA ISTI CNR Pisa Italy Pinecone Tel Aviv Israel

Maximum Inner Product Search or top-k retrieval on sparse vectors is well understood in information retrieval, with a number of mature algorithms that solve it exactly. However, all existing algorithms are tailored to text and frequency-based similarity measures. To achieve optimal memory footprint and query latency, they rely on the near stationarity of documents and on laws governing natural languages. We consider, instead, a setup in which collections are streaming-necessitating dynamic indexing-and where indexing and retrieval must work with arbitrarily distributed real-valued vectors. As we show, existing algorithms are no longer competitive in this setup, even against naive solutions. We investigate this gap and present a novel approximate solution, called SINNAMON, that can efficiently retrieve the top-k results for sparse real valued vectors drawn from arbitrary distributions. Notably, SINNAMON offers levers to trade off memory consumption, latency, and accuracy, making the algorithm suitable for constrained applications and systems. We give theoretical results on the error introduced by the approximate nature of the algorithm and present an empirical evaluation of its performance on two hardware platforms and synthetic and real-valued datasets. We conclude by laying out concrete directions for future research on this general top-k retrieval problem over sparse vectors.

关键词： approximate algorithms maximum inner product search sparse vectors

来源：评论

学校读者我要写书评

暂无评论

ε-approximate Coded Matrix Multiplication Is Nearly Twice as Efficient as Exact Multiplication

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第3期2卷 845-854页

作者： Jeong, Haewon Devulapalli, Ateet Cadambe, Viveck R. Calmon, Flavio P. Harvard Univ John A Paulson Sch Engn & Appl Sci Cambridge MA 02138 USA Penn State Univ Sch Elect Engn & Comp Sci University Pk PA 16801 USA

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of P computation nodes where each node stores 1/m of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with epsilon relative error from any m of the P nodes for any epsilon > 0. We obtain this result through a careful specialization of MatDot codes - a class of matrix multiplication codes previously developed in the context of exact recovery (epsilon = 0). Since prior results showed that MatDot codes achieve the best exact recovery threshold for a class of linear coding schemes, our result shows that allowing for mild approximations leads to a system that is nearly twice as efficient as exact reconstruction. For Entangled-Poly codes - which are generalizations of MatDot codes - we show that approximation reduces the recovery threshold from p(2)q+ q - 1 to p(2)q, when the input matrices A, B are split respectively in to a p x q and q x p grids of equal-sized submatrices.

关键词： Coded computing distributed computing fault-tolerant computing error correction codes approximate algorithms matrix multiplication distributed machine learning

来源：评论

学校读者我要写书评

暂无评论

approximate triclique coloring for register allocation

引用

INFORMATION PROCESSING LETTERS 1996年第5期60卷 249-253页

作者： Venkatesan, G Rangan, CP INDIAN INST TECHNOL DEPT COMP SCI & ENGNMADRAS 600036TAMIL NADUINDIA

A graph is said to be a triclique if its vertex set can be partitioned into three cliques, i.e. if its complement is tripartite. We prove that the colouring problem is NP-complete even when restricted to tricliques whose complements are planar tripartite line graphs. We then proceed to give a factor 1.5-approximation algorithm for the colouring problem on tricliques. In fact, our algorithm works for all graphs G which satisfy alpha(G) less than or equal to 3 and actually guarantees an approximation ratio that is at most 3/4+n/(4 chi(G)). We then indicate how this problem may be useful in the context of the register allocation problem that arises in compiler design.

关键词： triclique chromatic number register allocation graph (RAG) control-flow graph algorithms approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

An approximate Algorithm for Quantum Hamiltonian Identification with Complexity Analysis

引用

IFAC-PapersOnLine 2017年第1期50卷 11744-11748页

作者： Wang, Yuanlong Dong, Daoyi Petersen, Ian R. Zhang, Jun School of Engineering and Information Technology University of New South Wales CanberraACT2600 Australia Centre for Quantum Computation and Communication Technology Australia Research Council CanberraACT2600 Australia Research School of Engineering Australian National University CanberraACT0200 Australia Joint Institute of UM-SJTU Shanghai Jiao Tong University Shanghai200240 China

Identification of the Hamiltonian is vital for characterizing the dynamical evolution of a quantum system. The dimension of a multi-qubit system increases exponentially with the qubit number, which usually leads to daunting computational complexity for general Hamiltonian identification algorithms. In this paper, we design an efficient quantum Hamiltonian identification method based on periodical sampling. The computational complexity is O(M2+ MN2), where M is the number of unknown parameters to be identified in the Hamiltonian and N is the length of the sampling data. Numerical results with different data lengths demonstrate the effectiveness of the proposed identification algorithm. © 2017

关键词： Hamiltonians Computational complexity Quantum computers Quantum optics approximate algorithms Complexity analysis Dynamical evolution Identification algorithms Identification method Quantum Hamiltonians Quantum system Sampling data

来源：评论

学校读者我要写书评

暂无评论

Sliding Window-based approximate Triangle Counting over Streaming Graphs with Duplicate Edges 21

Sliding Window-based Approximate Triangle Counting over Stre...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Gou, Xiangyang Zou, Lei Peking Univ Beijing Peoples R China Natl Engn Lab Big Data Anal Technol & Applicat PI Beijing Peoples R China

ISBN: (纸本)9781450383431

Streaming graph analysis is gaining importance in various fields due to the natural dynamicity in many real graph applications. However, approximately counting triangles in real-world streaming graphs with edge duplication and expiration remains an unsolved problem. In this paper, we propose SWTC algorithm to address approximate sliding-window triangle counting problem in streaming graphs with edge duplication. In SWTC, we propose a fixed-length slicing strategy that addresses both unbiased sampling and cardinality estimation issues with a bounded memory usage. We theoretically prove the superiority of our method in sample graph size and estimation accuracy under given memory upper bound. Extensive experiments also confirm that our approach has higher accuracy compared with the baseline method under the same memory usage.

关键词： streaming graphs approximate algorithms triangle counting

来源：评论

学校读者我要写书评

暂无评论

Fast approximate Distance Queries in Unweighted Graphs Using Bounded Asynchrony 1

引用

29th International Workshop on Languages and Compilers for Parallel Computing (LCPC)

作者： Fidel, Adam Sabido, Francisco Coral Riedel, Colton Amato, Nancy M. Rauchwerger, Lawrence Texas A&M Univ Dept Comp Sci & Engn Parasol Lab College Stn TX 77843 USA

ISBN: (数字)9783319527093

ISBN: (纸本)9783319527093;9783319527086

We introduce a new parallel algorithm for approximate breadth-first ordering of an unweighted graph by using bounded asynchrony to parametrically control both the performance and error of the algorithm. This work is based on the k-level asynchronous (KLA) paradigm that trades expensive global synchronizations in the level-synchronous model for local synchronizations in the asynchronous model, which may result in redundant work. Instead of correcting errors introduced by asynchrony and redoing work as in KLA, in this work we control the amount of work that is redone and thus the amount of error allowed, leading to higher performance at the expense of a loss of precision. Results of an implementation of this algorithm are presented on up to 32,768 cores, showing 2.27x improvement over the exact KLA algorithm and 3.8x improvement over the level-synchronous version with minimal error on several graph inputs.

关键词： Parallel graph algorithms Breadth-first search Distance query approximate algorithms Asynchronous Distributed memory

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for approximate Betweenness Centrality Computation 13

An Efficient Algorithm for Approximate Betweenness Centralit...

引用

22nd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Chehreghani, Mostafa Haghir Katholieke Univ Leuven Dept Comp Sci Celestijnenlaan 200a Box 2402 B-3001 Leuven Belgium

ISBN: (纸本)9781450322638

Betweenness centrality is an important centrality measure widely used in social network analysis, route planning etc. However, even for mid-size networks, it is practically intractable to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased approximation of betweenness centrality. The proposed framework can be adapted with different sampling techniques and give diverse methods. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error and present a sampling method partially satisfying the conditions. We perform extensive experiments and show the high efficiency and accuracy of the proposed method.

关键词： Centrality betweenness centrality social network analysis approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Constant Query Time (1+ε)-approximate Distance Oracle for Planar Graphs 26th

Constant Query Time (1+ε)-Approximate Distance Oracle for P...

引用

26th International Symposium on algorithms and Computation (ISAAC)

作者： Gu, Qian-Ping Xu, Gengchun Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783662489710;9783662489703

We give a (1 + epsilon)-approximate distance oracle with 0(1) query time for an undirected planar graph G with n vertices and non negative edge length. For epsilon > 0 and any two vertices u and v in G, our oracle gives a distance (d) over tilde (u, v) with stretch (1 + epsilon) in 0(1) time. The oracle has size 0(n log n(logn/epsilon + f (epsilon)) and pre-processing time 0 (n log n(log(3) n/epsilon(2) f (epsilon)), where f (epsilon) = 2(O(1/epsilon)). This is the first (1+epsilon) approximate distance oracle with 0(1) query time independent of and the size and pre-processing time nearly linear in n, and improves the query time 0(1/epsilon) of previous (1 + epsilon)-approximate distance oracle with size nearly linear in n.

关键词： Distance oracle Planar graphs approximate algorithms Graph decomposition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：