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

On deterministic sketching and streaming for sparse recovery and norm estimation

LINEAR ALGEBRA AND ITS APPLICATIONS 2014年 441卷 152-167页

作者： Nelson, Jelani Nguyen, Huy L. Woodruff, David P. Inst Adv Study Princeton NJ 08540 USA Princeton Univ Princeton NJ 08540 USA IBM Almaden Res Ctr San Jose CA 95120 USA

We study classic streaming and sparse recovery problems using deterministic linear sketches, including l(1)/l(1) and l(infinity)/l(1) sparse recovery problems (the latter also being known as l(1)-heavy hitters), norm estimation, and approximate inner product. We focus on devising a fixed matrixA is an element of R-mxn and a deterministic recovery/estimation procedure which work for all possible input vectors simultaneously. Our results improve upon existing work, the following being our main contributions: A proof that l(infinity)/l(1) sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Our upper bound for the number of measurements is m = 0(epsilon(-2) min{log n, (log n/log(1/epsilon))2}), which holds for any 0 < 8 < 1/2. We can also obtain fast sketching and recovery algorithms by making use of the Fast Johnson-Lindenstrauss transform. Both our running times and number of measurements improve upon previous work. We can also obtain better error guarantees than previous work in terms of a smaller tail of the input vector. A new lower bound for the number of linear measurements required to solve l(1)/l(1) sparse recovery. We show Omega(k/epsilon(2) + klog(n/k)/epsilon) measurements are required to recover an x' with parallel to x-x'parallel to(1) <= (1+epsilon)parallel to x(tail(k))parallel to(1) where x(tail(k)) isx projected onto all but its largest k coordinates in magnitude. A tight bound of m = Theta(epsilon(-2) log(epsilon(2)n)) on the number of measurements required to solve deterministic norm estimation, i.e., to recover parallel to x parallel to(2) +/- epsilon parallel to x parallel to(1). For all the problems we study, tight bounds are already known for the randomized complexity from previous work, except in the case of l(1)/l(1) sparse recovery, where a nearly tight bound is known. Our work thus aims to study the deterministic complexities of these problems. We remark that some of th

关键词： streaming algorithms Sparse recovery Heavy hitters Norm estimation Data streams

来源：评论

学校读者我要写书评

暂无评论

streaming APPROXIMATION RESISTANCE OF EVERY ORDERING CSP

引用

COMPUTATIONAL COMPLEXITY 2024年第1期33卷 6-6页

作者： Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15232 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Toyota Technol Inst Chicago IL 60637 USA

An ordering constraint satisfaction problem (OCSP) is de-fined by a family F of predicates mapping permutations on{1,...,k}to{0,1}. An instance of Max-OCSP(F)on n variables consists of a list of constraints, each consisting of a predicate from F applied on kdis-tinct variables. The goal is to find an ordering of thenvariables that maximizes the number of constraints for which the induced orderingon the k variables satisfies the predicate. OCSPs capture well-studied problems including 'maximum acyclic subgraph' (MAS) and "maximum betweenness". In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) stream-ing setting, when an instance is presented as a stream of constraints. We show that for everyF,Max-OCSP(F) is approximation-resistant too(n)-space streaming algorithms, i.e., algorithms using o(n) space can-not distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In th ecase of MAS, our result shows that for every>0,MASis not (1/2+)-approximable ino(n) space. The previous best inapproximability result, due to Guruswami & Tao(2019), only ruled out 3/4-approximations ino(root n) space. Our results build on recent works of Chouet al.(2022b,2024) who provide a tight, linear-space inapproximability theorem fora broad class of "standard" (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet sizeq) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for stan-dard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following "partition expansion" property with high probability: For every partition of then variables into small blo

关键词： streaming algorithms approximation resistance constraint satisfaction problems ordering constraints

来源：评论

学校读者我要写书评

暂无评论

RECOGNIZING WELL-PARENTHESIZED EXPRESSIONS IN THE streaming MODEL

引用

SIAM JOURNAL ON COMPUTING 2014年第6期43卷 1880-1905页

作者： Magniez, Frederic Mathieu, Claire Nayak, Ashwin Univ Paris Diderot Sorbonne Paris Cite CNRS LIAFA Paris France Ecole Normale Super UMR CNRS 8548 Dept Informat Paris France Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada

Motivated by a concrete problem and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem DYCK(s) of checking matching parentheses, with s different types of parentheses. We present a one-pass randomized streaming algorithm for DYCK(2) with space of O(root n log n) bits, time per letter polylog(n), and one-sided error. We prove that this one-pass algorithm is optimal, up to a log n factor, even when two-sided error is allowed. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for DYCK(2) with space of O((log n)(2)), time polylog(n) and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to DYCK(s) since this problem is reducible to DYCK(2) for a suitable notion of reduction in the streaming model. Except for an extra O(root log s) multiplicative overhead in the space required in the one-pass algorithm, the resource requirements are of the same order. For the lower bound, we exhibit hard instances ASCENSION(m) of DYCK(2) with length in Theta(mn). We embed these in what we call a "one-pass" communication problem with 2m-players, where m is an element of(O) over bar (n). To establish the hardness of ASCENSION(m), we follow the "information cost" approach, but with a few twists. We prove a direct sum result that reduces ASCENSION(m) to a two-player protocol for MOUNTAIN, which is in fact a variant of INDEX, a fundamental problem in communication complexity. We finish the argument with a new information cost lower bound for MOUNTAIN.

关键词： streaming algorithms communication complexity information cost Dyck languages well-parenthesized expressions

来源：评论

学校读者我要写书评

暂无评论

Running Median Algorithm and Implementation for Integer streaming Applications

引用

IEEE EMBEDDED SYSTEMS LETTERS 2019年第2期11卷 58-61页

作者： Cadenas, Oswaldo Megson, Graham M. London South Bank Univ Sch Engn London SE1 0AA England Univ Westminster Dept Comp Sci London W1B 2UW England

A novel algorithm is proposed to compute the median of a running window of m integers in O(Ig Ig m) time. For a new window, the new median value is computed as a simple decision based on the previous median, and the values removed and inserted into the window. This facilitates implementations based on data structures that support fast ordinal predecessor/successor operations. The results show accelerations of up to factors of six for integer data streaming in typical embedded processors.

关键词： Embedded processors median median filter running median streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

streaming simplification of tetrahedral meshes

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2007年第1期13卷 145-155页

作者： Vo, Huy T. Callahan, Steven P. Lindstrom, Peter Pascucci, Valerio Silva, Claudio T. Sci Comp & Imaging Inst Salt Lake City UT 84112 USA Lawrence Livermore Natl Lab Ctr Appl Sci Comp Livermore CA 94551 USA Univ Utah Sch Comp Salt Lake City UT 84112 USA

Unstructured tetrahedral meshes are commonly used in scientific computing to represent scalar, vector, and tensor fields in three dimensions. Visualization of these meshes can be difficult to perform interactively due to their size and complexity. By reducing the size of the data, we can accomplish real-time visualization necessary for scientific analysis. We propose a two-step approach for streaming simplification of large tetrahedral meshes. Our algorithm arranges the data on disk in a streaming, I/O-efficient format that allows coherent access to the tetrahedral cells. A quadric-based simplification is sequentially performed on small portions of the mesh in-core. Our output is a coherent streaming mesh which facilitates future processing. Our technique is fast, produces high quality approximations, and operates out-of-core to process meshes too large for main memory.

关键词： computational geometry and object modeling out-of-core algorithms streaming algorithms mesh simplification large meshes tetrahedral meshes

来源：评论

学校读者我要写书评

暂无评论

Barcodes of Towers and a streaming Algorithm for Persistent Homology

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2019年第4期61卷 852-879页

作者： Kerber, Michael Schreiber, Hannah Graz Univ Technol Kopernikusgasse 24 A-8010 Graz Austria

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG, 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.

关键词： Persistent homology Topological data analysis Matrix reduction streaming algorithms Simplicial approximation

来源：评论

学校读者我要写书评

暂无评论

Bipartite Graph Matchings in the Semi-streaming Model

Bipartite Graph Matchings in the Semi-streaming Model

引用

17th Annual European Symposium on algorithms

作者： Eggert, Sebastian Kliemann, Lasse Srivastav, Anand Univ Kiel Inst Informat D-24118 Kiel Germany

ISBN: (纸本)9783642041273

We present an algorithm for finding a large matching in a bipartite graph in the semi-streaming model. In this model, the input graph G = (V, E) is represented as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(n polylog n) bits, where n = vertical bar V vertical bar. For epsilon > 0, our algorithm finds a 1/1+epsilon-approximation of a maximum-cardinality matching and uses O ((1/epsilon)(8)) passes over the input stream. The only previously known algorithm with such arbitrarily good approximation though for general graphs required exponentially many Omega ((1/epsilon)(1/epsilon))passes (McGregor 2005).

关键词： bipartite graph matching streaming algorithms approx. algorithms

来源：评论

学校读者我要写书评

暂无评论

Set Cover in the One-pass Edge-arrival streaming Model 23

Set Cover in the One-pass Edge-arrival Streaming Model

引用

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

作者： Khanna, Sanjeev Konrad, Christian Alexandru, Cezar-Mihail Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Univ Bristol Dept Comp Sci Bristol Avon England

ISBN: (纸本)9798400701276

We study the Set Cover problem in the one-pass edge-arrival streaming model. In this model, the input stream consists of a sequence of tuples (S, u), indicating that element u is contained in set S. This setting captures the streaming Dominating Set problem and is more general and harder to solve than the Set Cover set-arrival setting, where entire sets with all their elements arrive in the stream one-by-one. We prove the following results (n is the size of the universe, m is the number of sets): (1) A work by [Khanna, Konrad, ITCS'22] on streaming Dominating Set implies a one-pass (O) over tilde (root n)-approximation algorithm with space (O) over tilde (m) for edge-arrival Set Cover in adversarially ordered streams. We show that this space bound is best possible up to poly-log factors in that every alpha-approximation algorithm, for alpha = Omega(root n), requires space (Omega) over tilde (mn(2)/alpha(4)) in adversarially ordered streams, even if the algorithm is only required to output an alpha-approximation of the size of an optimal cover. (2) As our main result, we give a one-pass (O) over tilde (root n)-approximation algorithm with space (O) over tilde (m/root n) for edge-arrival Set Cover in random order streams. This result together with the lower bound mentioned above establishes a strong separation between the adversarial and random order settings. (3) Finally, in adversarial order streams, we showthat non-trivial algorithms with space o(m) can be achieved at the expense of increased approximation factors (O) over tilde (root n), which is in contrast to the set-arrival setting, where space (O) over tilde (n) is enough for a Theta(root n)-approximation, and space Omega(n) is needed for an o(n/log n)-approximation. We give an alpha-approximation algorithm for one-pass edge-arrival Set Cover with space (O) over tilde (mn/alpha(2)), for every alpha = (Omega) over tilde(root n).

关键词： streaming algorithms Set Cover Random Order Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

Pseudorandom Hashing for Space-bounded Computation with Applications in streaming 64

Pseudorandom Hashing for Space-bounded Computation with Appl...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Kacham, Praneeth Pagh, Rasmus Thorup, Mikkel Woodruff, David P. Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9798350318944

We revisit Nisan's classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashPRG, that can be thought of as a symmetric version of Nisan's generator over larger alphabets. Our generator allows a trade-off between seed length and the time needed to compute a given block of the generator's output. HashPRG can be used to obtain derandomizations with much better update time and without sacrificing space for a large number of data stream algorithms, for example: Andoni's F-p estimation algorithm for constant p > 2 (ICASSP, 2017) assumes a random oracle, but achieves optimal space and constant update time. Using HashPRG's time-space trade-off we eliminate the random oracle assumption while preserving the other properties. Previously no time-optimal derandomization was known. Using similar techniques, we give an algorithm for a relaxed version of l(p) sampling in a turnstile stream. Both of our algorithms use (O) over tilde (d(1-2/p)) bits of space and have O(1) update time. For 0 < p < 2, the 1 +/- epsilon approximate F-p estimation algorithm of Kane et al., (STOC, 2011) uses an optimal O(epsilon(-2) log d) bits of space but has an update time of O(log(2)(1/epsilon) log log(1/epsilon)). Using HashPRG, we show that if 1/root d <= epsilon <= 1/d(c) for an arbitrarily small constant c > 0, then we can obtain a 1 +/- epsilon approximate F-p estimation algorithm that uses the optimal O(epsilon(-2) log d) bits of space and has an update time of O(log d) in the Word RAM model, which is more than a quadratic improvement in the update time. We obtain similar improvements for entropy estimation. CountSketch, with the fine-grained error analysis of Minton and Price (SODA, 2014). For derandomization, they suggested a direct application of Nisan's generator, yielding a logarithmic multiplicative space overhead. With HashPRG we obtain an efficient derandomization yielding the same asym

关键词： Fast Update time Pseudorandom Generators streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Relative Error streaming Quantiles 21

Relative Error Streaming Quantiles

引用

40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Cormode, Graham Karnin, Zohar Liberty, Edo Thaler, Justin Vesely, Pavel Univ Warwick Coventry W Midlands England Amazon Seattle WA USA Pinecone San Mateo CA USA Georgetown Univ Washington DC USA Charles Univ Prague Comp Sci Inst Prague Czech Republic

ISBN: (纸本)9781450383813

Approximating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe u equipped with a total order, the task is to compute a sketch (data structure) of size poly(log(n), 1/epsilon). Given the sketch and a query item y is an element of u, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y. Most works to date focused on additive epsilon n error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This paper investigates multiplicative (1 +/- epsilon)-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O(log(epsilon(2)n)/epsilon(2)) or O(log(3)(epsilon n)/epsilon) universe items. This paper presents a randomized algorithm storing O(log(1.5)(epsilon n)/epsilon) items, which is within an O(root log(epsilon n)) factor of optimal. The algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.

关键词： quantiles streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：