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

Approaching Optimal Duplicate Detection in a Sliding Window 1

26th International Computing and Combinatorics Conference (COCOON)

作者： Geraud-Stewart, Remi Lombard-Platet, Marius Naccache, David PSL Res Univ Dept Informat ENS CNRS Paris France Be Ys Grp Be Studys Chatelaine Switzerland

ISBN: (数字)9783030581503

ISBN: (纸本)9783030581503;9783030581497

Duplicate detection is the problem of identifying whether a given item has previously appeared in a (possibly infinite) stream of data, when only a limited amount of memory is available. Unfortunately the infinite stream setting is ill-posed, and error rates of duplicate detection filters turn out to be heavily constrained: consequently they appear to provide no advantage, asymptotically, over a biased coin toss [8]. In this paper we formalize the sliding window setting introduced by [12,15], and show that a perfect (zero error) solution can be used up to a maximal window size w(max). Above this threshold we show that some existing duplicate detection filters (designed for the non-windowed setting) perform better that those targeting the windowed problem. Finally, we introduce a "queuing construction" that improves on the performance of some duplicate detection filters in the windowed setting. We also analyse the security of our filters in an adversarial setting.

关键词： Duplicate detection streaming algorithms Sliding window

来源：评论

学校读者我要写书评

暂无评论

Listing Dense Subgraphs in Small Memory 9

Listing Dense Subgraphs in Small Memory

引用

9th Latin American Web Congress (LA-WEB)

作者： Pinto, Patricio Cruces, Nataly Hernandez, Cecilia Univ Concepcion Dept Comp Sci Concepcion Chile

ISBN: (纸本)9781479969531

Listing relevant patterns from graphs is becoming increasingly challenging as Web and social graphs are growing in size at a great rate. This scenario requires to process information more efficiently, including the need of processing data that cannot fit in main memory. Typical approaches for processing data using limited main memory include the streaming and external memory models. This paper addresses the problem of listing dense subgraphs from Web and social graphs using little memory. We propose an external memory algorithm based on K-way merge-sort for clustering and reordering input graphs. We also propose mining heuristics that work well with different stream orders such as URL, BFS, and cluster-based. Our experimental evaluation shows that on Web graphs, in comparison with the in-memory algorithm, the streaming mining heuristic is able to find between 70 and 96% of edges participating in dense subgraphs, uses only between 17 and 25% of the memory, and running times are between 34 and 65%. We further consider an application that uses these dense subgraphs for compressing Web graphs with a representation that enables querying the collection of subgraphs for pattern recovery and basic statistics without decompression.

关键词： Web Graphs Graph Pattern Listing streaming algorithms External Memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Two-Way Quantum and Classical Automata with Advice for Online Minimization Problems 3rd

Two-Way Quantum and Classical Automata with Advice for Onlin...

引用

3rd World Congress on Formal Methods (FM)

作者： Khadiev, Kamil Khadieva, Aliya Smart Quantum Technol Ltd Kazan Russia Kazan Fed Univ Kazan Russia Univ Latvia Riga Latvia

ISBN: (纸本)9783030549961;9783030549978

We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore two-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. We show that there are problems that can be solved more efficiently by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size) even if classical automata get advice bits.

关键词： Quantum computation Online algorithms streaming algorithms Online minimization problems Two-way automata Automata

来源：评论

学校读者我要写书评

暂无评论

Symmetric Norm Estimation and Regression on Sliding Windows 27th

Symmetric Norm Estimation and Regression on Sliding Windows

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Braverman, Vladimir Wei, Viska Zhou, Samson Johns Hopkins Univ Baltimore MD USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9783030895433;9783030895426

The sliding window model generalizes the standard streaming model and often performs better in applications where recent data is more important or more accurate than data that arrived prior to a certain time. We study the problem of approximating symmetric norms (a norm on R-n that is invariant under sign-flips and coordinate-wise permutations) in the sliding window model, where only the W most recent updates define the underlying frequency vector. Whereas standard norm estimation algorithms for sliding windows rely on the smooth histogram framework of Braverman and Ostrovsky (FOCS 2007), analyzing the smoothness of general symmetric norms seems to be a challenging obstacle. Instead, we observe that the symmetric norm streaming algorithm of Braverman et al. (STOC 2017) can be reduced to identifying and approximating the frequency of heavy-hitters in a number of substreams. We introduce a heavy-hitter algorithm that gives a (1 + epsilon)-approximation to each of the reported frequencies in the sliding window model, thus obtaining the first algorithm for general symmetric norm estimation in the sliding window model. Our algorithm is a universal sketch that simultaneously approximates all symmetric norms in a parametrizable class and also improves upon the smooth histogram framework for estimating L-p norms, for a range of large p. Finally, we consider the problem of overconstrained linear regression problem in the case that loss function that is an Orlicz norm, a symmetric norm that can be interpreted as a scale-invariant version of M-estimators. We give the first sublinear space algorithms that produce (1+ epsilon)-approximate solutions to the linear regression problem for loss functions that are Orlicz norms in both the streaming and sliding window models.

关键词： streaming algorithms Symmetric norms Sliding window model Linear regression

来源：评论

学校读者我要写书评

暂无评论

Efficient Episode Mining of Dynamic Event Streams

Efficient Episode Mining of Dynamic Event Streams

引用

12th IEEE International Conference on Data Mining (ICDM)

作者： Patnaik, Debprakash Laxman, Srivatsan Chandramouli, Badrish Ramakrishnan, Naren Amazon Com Seattle WA 98109 USA Microsoft Res Bangalore 560080 Karnataka India Microsoft Res Redmond WA 98052 USA Dept Comp Sci Virginia Tech Blacksburg VA 24061 USA

ISBN: (纸本)9781467346498;9780769549057

Discovering frequent episodes over event sequences is an important data mining problem. Existing methods typically require multiple passes over the data, rendering them unsuitable for streaming contexts. We present the first streaming algorithm for mining frequent episodes over a window of recent events in the stream. We derive approximation guarantees for our algorithm in terms of: (i) the separation of frequent episodes from infrequent ones, and (ii) the rate of change of stream characteristics. Our parameterization of the problem provides a new sweet spot in the tradeoff between making distributional assumptions over the stream and algorithmic efficiencies of mining. We illustrate how this yields significant benefits when mining practical streams from neuroscience and telecommunications logs.

关键词： Event Sequences Data Streams Frequent Episodes Pattern Discovery streaming algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Factorial Lower Bounds for (Almost) Random Order Streams 63

Factorial Lower Bounds for (Almost) Random Order Streams

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Chiplunkar, Ashish Kallaugher, John Kapralov, Michael Price, Eric IIT Delhi Delhi India Sandia Natl Labs Albuquerque NM 87185 USA Ecole Polytech Fed Lausanne Lausanne Switzerland UT Austin Austin TX USA

ISBN: (纸本)9781665455190

In this paper we introduce and study the streamingCYCLES problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph G, comprising n/l disjoint length-l cycles on n vertices, are partitioned randomly among n players. Every edge is annotated with an independent uniformly random bit, and the players' task is to output, for some cycle in G, the sum (modulo 2) of the bits on its edges, after one round of sequential communication. Our main result is an l(Omega(l)) lower bound on the communication complexity of streamingCYCLES, which is tight up to constant factors in the exponent. Applications of our lower bound for streamingCYCLES include an essentially tight lower bound for component collection in (almost) random order graph streams, making progress towards a conjecture of Peng and Sohler [SODA'18] and the first exponential space lower bounds for random walk generation.

关键词： streaming algorithms graph algorithms fourier analysis communication complexity

来源：评论

学校读者我要写书评

暂无评论

On MAP Inference of Ferromagnetic Potts Models and Nonsymmetric Determinantal Point Processes

On MAP Inference of Ferromagnetic Potts Models and Nonsymmet...

引用

作者： Talla, Aravind Reddy Northwestern University

学位级别：Ph.D., Doctor of Philosophy

In the Maximum-a-Posteriori (MAP) Inference problem, for any given probability distribution, the goal is to find the point in the support of that distribution with the highest probability. Potts models and Determinantal Point Processes (DPPs) are probabilistic models that were introduced in the context of statistical physics several decades ago. They have been extensively used in several computer science applications like computer vision, recommender systems, and document summarization. Exact MAP Inference in these models correspond to NP-hard combinatorial optimization problems and so approximate inference algorithms have been extensively studied. For MAP Inference in Ferromagnetic Potts models, we provide a strong justification for the excellent performance of a linear programming relaxation approach by going beyond worst-case analysis. For MAP Inference in Nonsymmetric Determinantal Point Processes, we provide the first one-pass streaming and online algorithms.

关键词： Determinantal Point Process Linear programming MAP Inference Online algorithms Potts model streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

streaming Communication Protocols

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2018年第4期10卷 19-19页

作者： Boczkowski, Lucas Kerenidis, Iordanis Magniez, Frederic Univ Paris Diderot IRIF CNRS Paris 7 Case 7014 F-75205 Paris 13 France

We define the streaming Communication model that combines the main aspects of communication complexity and streaming. Input arrives as a stream, spread between several agents across a network. Each agent has a bounded memory, which can be updated upon receiving a new bit, or a message from another agent. We provide tight tradeoffs between the necessary resources, i.e., communication between agents and memory, for some of the canonical problems from communication complexity by proving a strong general lower bound technique. Second, we analyze the Approximate Matching problem and show that the complexity of this problem (i.e., the achievable approximation ratio) in the one-way variant of our model is strictly different both from the streaming complexity and the one-way communication complexity thereof.

关键词： Communication complexity streaming algorithms networks approximate matching

来源：评论

学校读者我要写书评

暂无评论

EHDSktch: A Generic Low Power Architecture for Sketching in Energy Harvesting Devices 21

<i>EHDSktch</i>: A Generic Low Power Architecture for Sketch...

引用

26th Asia and South Pacific Design Automation Conference (ASP-DAC)

作者： Singla, Priyanka Goodchild, Chandran Sarangi, Smruti R. Indian Inst Technol Delhi New Delhi India Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450379991

Energy harvesting devices (EHDs) are becoming extremely prevalent in remote and hazardous environments. They sense the ambient parameters and compute some statistics on them, which are then sent to a remote server. Due to the resource-constrained nature of EHDs, it is challenging to perform exact computations on streaming data;however, if we are willing to tolerate a slight amount of inaccuracy, we can leverage the power of sketching algorithms to provide quick answers with significantly lower energy consumption. In this paper, we propose a novel hardware architecture called EHDSktch - a set of IP blocks that can be used to implement most of the popular sketching algorithms. We demonstrate an energy savings of 4-10X and a speedup of more than 10X over state-of-the-art software implementations. Leveraging the temporal locality further provides us a performance gain of 3-20% in energy and time and reduces the on-chip memory requirement by at least 50-75%.

关键词： streaming algorithms Hardware for sketching Approximate computing

来源：评论

学校读者我要写书评

暂无评论

Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size 22

Estimation of the Size of Union of Delphic Sets: Achieving I...

引用

41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Meel, Kuldeep S. Chakraborty, Sourav Vinodchandran, N. V. Natl Univ Singapore Singapore Singapore Indian Stat Inst Kolkata India Univ Nebraska Lincoln NE USA

ISBN: (纸本)9781450392600

Given a family of sets {S-1, S-2, ... S-M} over a universe Omega, estimating the size of their union in the data streaming model is a fundamental computational problem with a wide variety of applications. The holy grail in the field of streaming is to seek design of algorithms that achieve (epsilon,delta)-approximation with poly(log |Omega|, epsilon(-1), log delta(-1)) space and update time complexity. Earlier investigations achieve algorithms with desired space and update time complexity for restricted cases such as singletons (Distinct Elements problem), one-dimensional ranges, arithmetic progressions, and sub-cubes. However, techniques used in these works fail for many other simple structured sets. A prominent example is that of Klee's Measure Problem (KMP), wherein every set S-i is represented by an axis-parallel rectangle in d-dimensional spaces. Despite extensive priorwork, the best-known streaming algorithms for many of these cases depend on the size of the stream, and therefore the problem of whether there exists a streaming algorithm for estimations of size of the union of sets with poly(log |Omega|, epsilon(-1), log delta(-1)) space and update time complexity has remained open. In this work, we focus on certain general families of sets called Delphic families (which allows efficient membership, sampling, and cardinality queries). Such families of sets capture several well-known problems, including KMP, test coverage, and hypervolume estimation. The primary contribution of our work is to resolve the above mentioned open problem for streams over Delphic families. In particular, we design the first streaming algorithm for estimating fifi D |(sic)(M)(i) =1 S-i| with poly(log |Omega|, epsilon(-1), log delta(-1)) space and update time complexity (independent of M, the length of the stream) when each S-i is a member from a Delphic family of sets. We further generalize our results to larger families of sets, called approximate-Delphic families, for which the size

关键词： probabilistic computations streaming algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：