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

Improving compressed matrix multiplication using control variate method

INFORMATION PROCESSING LETTERS 2025年 187卷

作者： Verma, Bhisham Dev Dubey, Punit Pankaj Pratap, Rameshwar Thakur, Manoj Indian Inst Technol Mandi Mandi Himachal Prades India Indian Inst Technol Hyderabad Telangana India

The seminal work by Pagh [1] proposed a matrix multiplication algorithm for real-valued squared matrices called Compressed Matrix Multiplication (CMM) having a sparse matrix output product. The algorithm is based on a popular sketching technique called Count-Sketch [2] and Fast Fourier Transform (FFT). For input square matrices A and B of order n and the product matrix AB with Frobenius norm ||AB||(F), the algorithm offers an unbiased estimate for each entry, i.e., (AB)(i,j) of the product matrix AB with a variance bounded by ||AB||(2)(F)/b, where b is the compressed bucket size. Thus, the variance will eventually become high for a small bucket size. In this work, we address the high variance problem of CMM with the help of a simple and practical technique based on classical variance reduction methods in statistics. Our techniques rely on the Control Variate (CV) method. We suggest rigorous theoretical analysis for variance reduction and complement it via supporting empirical evidence.

关键词： Count-Sketch Matrix multiplication sketching algorithms Control variate

来源：评论

学校读者我要写书评

暂无评论

Minwise-Independent Permutations with Insertion and Deletion of Features 16th

Minwise-Independent Permutations with Insertion and Deletion...

引用

16th International Conference on Similarity Search and Applications

作者： Pratap, Rameshwar Kulkarni, Raghav IIT Hyderabad Hyderabad Telangana India Chennai Math Inst Chennai Tamil Nadu India

ISBN: (纸本)9783031469930;9783031469947

The seminal work of Broder et al. [5] introduces the minHash algorithm that computes a low-dimensional sketch of high-dimensional binary data that closely approximates pairwise Jaccard similarity. Since its invention, minHash has been commonly used by practitioners in various big data applications. In many real-life scenarios, the data is dynamic and their feature sets evolve over time. We consider the case when features are dynamically inserted and deleted in the dataset. A naive solution to this problem is to repeatedly recompute minHash with respect to the updated dimension. However, this is an expensive task as it requires generating fresh random permutations. To the best of our knowledge, no systematic study of minHash is recorded in the context of dynamic insertion and deletion of features. In this work, we initiate this study and suggest algorithms that make the minHash sketches adaptable to the dynamic insertion and deletion of features. We show a rigorous theoretical analysis of our algorithms and complement it with supporting experiments on several real-world datasets. Empirically we observe a significant speed-up in the running time while simultaneously offering comparable performance with respect to running minHash from scratch. Our proposal is efficient, accurate, and easy to implement in practice.

关键词： sketching algorithms Jaccard similarity estimation Streaming algorithms Locality sensitive hashing (LSH)

来源：评论

学校读者我要写书评

暂无评论

BagMinHash - Minwise Hashing Algorithm for Weighted Sets 18

BagMinHash - Minwise Hashing Algorithm for Weighted Sets

引用

24th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

作者： Ertl, Otmar Dynatrace Linz Austria

ISBN: (纸本)9781450355520

Minwise hashing has become a standard tool to calculate signatures which allow direct estimation of Jaccard similarities. While very efficient algorithms already exist for the unweighted case, the calculation of signatures for weighted sets is still a time consuming task. BagMinHash is a new algorithm that can be orders of magnitude faster than current state of the art without any particular restrictions or assumptions on weights or data dimensionality. Applied to the special case of unweighted sets, it represents the first efficient algorithm producing independent signature components. A series of tests finally verifies the new algorithm and also reveals limitations of other approaches published in the recent past.

来源：评论

学校读者我要写书评

暂无评论

Correlation Sketches for Approximate Join-Correlation Queries 21

Correlation Sketches for Approximate Join-Correlation Querie...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Santos, Aecio Bessa, Aline Chirigati, Fernando Musco, Christopher Freire, Juliana NYU New York NY 10003 USA Springer Nat Berlin Germany

ISBN: (纸本)9781450383431

The increasing availability of structured datasets, from Web tables and open-data portals to enterprise data, opens up opportunities to enrich analytics and improve machine learning models through relational data augmentation. In this paper, we introduce a new class of data augmentation queries: join-correlation queries. Given a column Q and a join column K-Q from a query table T-Q, retrieve tables T-X in a dataset collection such that T-X is joinable with T-Q on K-Q and there is a column C is an element of T-X such that Q is correlated with C. A naive approach to evaluate these queries, which first finds joinable tables and then explicitly joins and computes correlations between Q and all columns of the discovered tables, is prohibitively expensive. To efficiently support correlated column discovery, we 1) propose a sketching method that enables the construction of an index for a large number of tables and that provides accurate estimates for join-correlation queries, and 2) explore different scoring strategies that effectively rank the query results based on how well the columns are correlated with the query. We carry out a detailed experimental evaluation, using both synthetic and real data, which shows that our sketches attain high accuracy and the scoring strategies lead to high-quality rankings.

关键词： sketching algorithms join-correlation estimation dataset search confidence intervals approximate query processing

来源：评论

学校读者我要写书评

暂无评论

Raising the Level of Abstraction for Sketch-Based Network Telemetry with SketchPlan 24

Raising the Level of Abstraction for Sketch-Based Network Te...

引用

ACM Internet Measurement Conference (IMC)

作者： Srivastava, Milind Hung, Shao-Tse Namkung, Hun Lin, Kate Ching-Ju Liu, Zaoxing Sekar, Vyas Carnegie Mellon Univ Pittsburgh PA 15213 USA Natl Yang Ming Chiao Tung Univ Taipei Taiwan Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9798400705922

While sketch-based network telemetry is attractive, realizing its potential benefits has been elusive in practice. Existing sketch solutions offer low-level interfaces and impose high effort on operators to satisfy telemetry intents with required accuracies. Extending these approaches to reduce effort results in inefficient deployments with poor accuracy-resource tradeoffs. We present SketchPlan, an abstraction layer for sketch-based telemetry to reduce effort and achieve high efficiency. SketchPlan takes an ensemble view across telemetry intents and sketches, instead of existing approaches that consider each intent-sketch pair in isolation. We show that SketchPlan improves accuracy-resource tradeoffs by up-to 12x and up-to 60x vs. baselines, in single-node and network-wide settings. SketchPlan is open-sourced at: https: //***/milindsrivastava1997/SketchPlan.

关键词： sketching algorithms Network measurement Network telemetry

来源：评论

学校读者我要写书评

暂无评论

Towards Better Bounds for Finding Quasi-Identifiers 23

Towards Better Bounds for Finding Quasi-Identifiers

引用

42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Hildebrant, Ryan Quoc-Tung Le Duy-Hoang Ta Vu, Hoa T. Univ Calif Irvine Irvine CA 92697 USA Univ Lyon ENS Lyon UCBL CNRSInriaLIP F-69342 Lyon 07 France Natl Univ Singapore Singapore Singapore San Diego State Univ San Diego CA 92182 USA

ISBN: (纸本)9798400701276

We revisit the problem of finding small epsilon-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x(1),x(2),...,x(n)}. The goal is to find a small subset of coordinates that separates at least (1 -epsilon) ((n)(2)) pairs of tuples. When.. is large, they provided a fast algorithm that runs on Theta(m /epsilon) tuples sampled uniformly at random. We show that the sample size can be improved to Theta(m/root epsilon). Our algorithm also enjoys a faster running time. To obtain this result, we consider a decision problem that takes a subset of coordinates A subset of [m]. It rejects if.. separates fewer than ( 1 - epsilon) ((n)(2)) pairs of tuples, and accepts if.. separates all ((n)(2)) pairs of tuples. The algorithm must be correct with probability at least 1 -delta for all 2m choices of A. We show that for algorithms based on uniform sampling: center dot Theta (m/root epsilon) samples are sufficient and necessary so that delta <= e-m. center dot Omega (root logm/epsilon) samples are necessary so that delta is a constant. Closing the gap between the upper and lower bounds in this case is still an open question. The analysis is based on a constrained version of the balls-into-bins problem whose worst case can be determined using Karush Kuhn Tucker (KKT) conditions. We believe our analysis may be of independent interest. We also study a related problem that asks for the following sketching algorithm: with given parameters alpha,k and epsilon, the algorithm takes a subset of coordinates A of size at most k and returns an estimate of the number of unseparated pairs in A up to a ( 1 +/- epsilon) factor if it is at least alpha((n)(2)). We show that even for constant alpha and success probability, such a sketching algorithm must use Omega(mk log epsilon (- 1)) bits of space;on the other hand, uniform sampling yields a sketch of size Theta(mk/alpha epsilon(2)) for this purpose.

关键词： sketching algorithms sample complexity lower bounds quasi-identifiers

来源：评论

学校读者我要写书评

暂无评论

Sequential Sensing with Model Mismatch

Sequential Sensing with Model Mismatch

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Song, Ruiyang Xie, Yao Pokutta, Sebastian Tsinghua Univ Elect Engn Beijing Peoples R China Georgia Inst Technol Ind & Syst Engn Atlanta GA 30332 USA

ISBN: (纸本)9781467377041

We characterize the performance of sequential information guided sensing, Info-Greedy Sensing [1], when there is a mismatch between the true signal model and the assumed model, which may be a sample estimate. In particular, we consider a setup where the signal is low-rank Gaussian and the measurements are taken in the directions of eigenvectors of the covariance matrix Sigma in a decreasing order of eigenvalues. We establish a set of performance bounds when a mismatched covariance matrix (Sigma) over cap is used, in terms of the gap of signal posterior entropy, as well as the additional amount of power required to achieve the same signal recovery precision. Based on this, we further study how to choose an initialization for Info-Greedy Sensing using the sample covariance matrix, or using an efficient covariance sketching scheme.

关键词： compressed sensing information theory sequential methods high-dimensional statistics sketching algorithms

来源：评论

学校读者我要写书评

暂无评论

Near-Linear Time and Fixed-Parameter Tractable algorithms for Tensor Decompositions 15

Near-Linear Time and Fixed-Parameter Tractable Algorithms fo...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Mahankali, Arvind, V Woodruff, David P. Zhang, Ziyu Stanford Univ Stanford CA 94305 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA MIT CSAIL Cambridge MA USA

ISBN: (纸本)9783959773096

We study low rank approximation of tensors, focusing on the Tensor Train and Tucker decompositions, as well as approximations with tree tensor networks and general tensor networks. As suggested by hardness results also shown in this work, obtaining (1 + s) approximation algorithms for rank k tensor train and Tucker decompositions efficiently may be computationally hard for these problems. Therefore, we propose different algorithms that respectively satisfy some of the objectives above while violating some others within a bound, known as bicriteria algorithms. On the one hand, for rank-k tensor train decomposition for tensors with q modes, we give a (1 + s)-approximation algorithm with a small bicriteria rank (0(qk I 5) up to logarithmic factors) and 0 (q " nnz(A)) running time, up to lower order terms. Here nnz(A) denotes the number of non-zero entries in the input tensor A. We also show how to convert the algorithm of [28] into a relative error approximation algorithm, but their algorithm necessarily has a running time of 0(qr2 " nnz(A)) n " poly(qk/s) when converted to a (1 + s)-approximation algorithm with bicriteria rank r. Thus, the running time of our algorithm is better by at least a k2 factor. To the best of our knowledge, our work is the first to achieve a near-input-sparsity time relative error approximation algorithm for tensor train decomposition. Our key technique is a method for efficiently obtaining subspace embeddings for a matrix which is the flattening of a Tensor Train of q tensors- the number of rows in the subspace embeddings is polynomial in q, thus avoiding the curse of dimensionality. We extend our algorithm to tree tensor networks and tensor networks on arbitrary graphs. Another way of coping with intractability is by looking at fixed-parameter tractable (FPT) algorithms. We give FPT algorithms for the tensor train, Tucker, and Canonical Polyadic (CP) decompositions, which are simpler than the FPT algorithms of [52], since our algorithms do

关键词： Low rank approximation sketching algorithms Tensor decomposition

来源：评论

学校读者我要写书评

暂无评论

Iris: Amortized, Resource Efficient Visualizations of Voluminous Spatiotemporal Datasets 7

Iris: Amortized, Resource Efficient Visualizations of Volumi...

引用

7th IEEE/ACM International Conference on Big Data Computing, Applications and Technologies (BDCAT)

作者： Bruhwiler, Kevin Buddhika, Thilina Pallickara, Shrideep Pallickara, Sangmi Lee Colorado State Univ Dept Comp Sci Ft Collins CO 80521 USA

ISBN: (纸本)9780738123967

The growth in observational data volumes over the past decade has occurred alongside a need to make sense of the phenomena that underpin them. Visualization is a key component of the data wrangling process that precedes the analyses that informs these insights. The crux of this study is interactive visualizations of spatiotemporal phenomena from voluminous datasets. Spatiotemporal visualizations of voluminous datasets introduce challenges relating to interactivity, overlaying multiple datasets and dynamic feature selection, resource capacity constraints, and scaling. In this study we describe our methodology to address these challenges. We rely on a novel mix of algorithms and systems innovations working in concert to ensure effective apportioning and amortization of workloads and enable interactivity during visualizations. In particular our research prototype, Iris, leverages sketching algorithms, effective query predicate generation and evaluation, avoids performance hotspots, harnesses coprocessors for hardware acceleration, and convolutional neural network based encoders to render visualizations while preserving responsiveness and interactivity. We also report on several empirical benchmarks that demonstrate the suitability of our methodology to preserve interactivity while utilizing resources effectively to scale.

关键词： Spatiotemporal Data Visualization sketching algorithms Neural Networks

来源：评论

学校读者我要写书评

暂无评论

μMon: Empowering Microsecond-level Network Monitoring withWavelets 24

μMon: Empowering Microsecond-level Network Monitoring withW...

引用

ACM SIGCOMM Conference

作者： Zheng, Hao Huang, Chengyuan Han, Xiangyu Zheng, Jiaqi Wang, Xiaoliang Tian, Chen Dou, Wanchun Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China

ISBN: (纸本)9798400706141

Network monitoring is essential for network management and optimization. In modern data centers, fluctuations in flow rates and network congestion events (e.g., microbursts) typically manifest on a microsecond timescale. However, the time granularity of network monitoring systems has not been refined correspondingly to efficiently capture these behaviors. Attaining the monitoring granularity at the microsecond scale can greatly facilitate network performance analysis and management, but poses considerable challenges regarding memory, bandwidth, and deployment costs. We propose mu Mon, a novel microsecond-level network monitoring system for data centers. The key of mu Mon is WaveSketch, an innovative algorithm that measures and compresses flow rate curves using in-dataplane wavelet transform. WaveSketch allows for more accurate characterization of application traffic patterns and aids in profiling transport algorithms. Furthermore, by combining the fine-grained flow rate measurements with network-collected congestion information, mu Mon can 'replay' congestion events to analyze their cause and impact. We evaluate mu Mon through testbed deployment and simulations at a granularity of 8.192 mu s. The evaluation results demonstrate that mu Mon can achieve a 90% accuracy in microsecond-level rate measurements with an average of 5 Mbps bandwidth overhead per host. Additionally, it can capture 99% heavy congestion events with 31-82 Mbps bandwidth overhead per switch.

关键词： Network Monitoring sketching algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：