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

arXiv 2017年

作者： Freksen, Casper Benjamin Larsen, Kasper Green A Center of Danish National Research Foundation Center for Massive Data Algorithmics Aarhus University Villum Young Investigator Grant An Auff Starting Grant and Madalgo

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N vectors X-Rn, there exists a mapping f : X ! Rm such that f(X) preserves all pairwise distances between vectors in X to within (1 ± ") if m = O("-2 lgN). Much effort has gone into developing fast embedding algorithms, with the Fast Johnson-Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal m = O("-2 lgN) dimensions has an embedding time of O(n lg n + "-2 lg3 N). An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random m×n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(n lgm) time. The big question is of course whether m = O("-2 lgN) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that m = O("-2 lg2 N) dimensions suffices. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exists a set of N vectors requiring m = ("-2 lg2 N) for the Toeplitz approach to work. Copyright © 2017, The Authors. All rights reserved.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

Instance-optimal geometric algorithms

Instance-optimal geometric algorithms

引用

作者： madalgo, Peyman Afshani Barbay, Jérémy Chan, Timothy M. MADALGO Center for Massive Data Algorithmics Department of Computer Science Aarhus University The IT-park Åbogade 34 Aarhus NDK-8200 Denmark Universidad de Chile Avenida Beauchef 851 Santiago837-0456 Chile Department of Computer Science University of Illinois at Urbana-Champaign 201 N. Goodwin Ave. UrbanaIL61801 United States

We prove the existence of an algorithm Afor computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A′ in a certain class A, the running time of A on input σ is at most a constant factor times the running time of A′ on the worst possible permutation of σ for A′. In fact, we can establish a stronger property: for every sequence σ of points and every algorithm A′, the running time of A on σ is at most a constant factor times the average running time of A′ over all permutations of σ. We call algorithms satisfying these properties instance optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L8-close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example,

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Maintaining Contour Trees of Dynamic Terrains 31

Maintaining Contour Trees of Dynamic Terrains

引用

31st International Symposium on Computational Geometry, SoCG 2015

作者： Agarwal, Pankaj K. Mølhave, Thomas Revsbæk, Morten Safa, Issam Wang, Yusu Yang, Jungwoo Department of Computer Science Duke University United States Scalable Algorithmics SCALGO United States MADALGO Center for Massive Data Algorithmics Aarhus University Denmark Computational Lithography Group Intel Corporation United States Department of Computer Science and Engineering Ohio State University United States

ISBN: (纸本)9783939897835

We study the problem of maintaining the contour tree T of a terrain σ, represented as a triangulated xy-monotone surface, as the heights of its vertices vary continuously with time. We characterize the combinatorial changes in T and how they relate to topological changes in. We present a kinetic data structure (KDS) for maintaining T efficiently. It maintains certificates that fail, i.e., an event occurs, only when the heights of two adjacent vertices become equal or two saddle vertices appear on the same contour. Assuming that the heights of two vertices of κ become equal only O(1) times and these instances can be computed in O(1) time, the KDS processes O(κ + n) events, where n is the number of vertices in σ and κ;is the number of events at which the combinatorial structure of T changes, and processes each event in O(log n) time. The KDS can be extended to maintain an augmented contour tree and a join/split tree.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Approximate Range Emptiness in Constant Time and Optimal Space 15

Approximate Range Emptiness in Constant Time and Optimal Spa...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Mayank Goswami Allan Gronlund Kasper Green Larsen Rasmus Pagh Max-Planck Institute for Informatics Aarhus University Supported by MADALGO - Center for Massive Data Algorithmics a Center of the Danish National Research Foundation IT University of Copenhagen

ISBN: (纸本)9781510813311

This paper studies the ε-approximate range emptiness problem, where the task is to represent a set S of n points from {0,..., U - 1} and answer emptiness queries of the form "[a; b] ∩ S ≠ 0?" with a probability of false positives allowed. This generalizes the functionality of Bloom filters from single point queries to any interval length L. Setting the false positive rate to ε/L and performing L queries, Bloom filters yield a solution to this problem with space O(n lg(L/ε)) bits, false positive probability bounded by ε for intervals of length up to L, using query time O(L lg(L/ε)). Our first contribution is to show that the space/error trade-off cannot be improved asymptotically: Any data structure for answering approximate range emptiness queries on intervals of length up to L with false positive probability ε, must use space Ω(n lg(L/ε))-O(n) bits. On the positive side we show that the query time can be improved greatly, to constant time, while matching our space lower bound up to a lower order additive term. This result is achieved through a succinct data structure for (non-approximate 1d) range emptiness/reporting queries, which may be of independent interest.

关键词： False-positives search time signal to noise ratios Drill bits bloom single turnout Probability data structures Approximate

来源：评论

学校读者我要写书评

暂无评论

Simplifying massive planar subdivisions 16

Simplifying massive planar subdivisions

引用

16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014

作者： Arge, Lars Truelsen, Jakob Yang, Jungwoo MADALGO Center for Massive Data Algorithmics Department of Computer Science Aarhus University Denmark

ISBN: (纸本)9781611973198

We present the first I/O- and practically-efficient algorithm for simplifying a planar subdivision, such that no point is moved more than a given distance Εxyand such that neighbor relations between faces (homotopy) are preserved. Under some practically realistic assumptions, our algorithm uses O(SORT(N)) I/Os, where N is the size of the decomposition and SORT(N) is the number of I/Os need to sort in the standard externalmemory model of computation. Previously, such an algorithm was only known for the special case of contour map simplification. Our algorithm is simple enough to be of practical interest. In fact, although more general, it is significantly simpler than the previous contour map simplification algorithm. We have implemented our algorithm and present results of experimenting with it on massive reallife data. The experiments confirm that the algorithm is efficient in practice. For example, for the contour map simplification problem it is significantly faster than the previous algorithm, while obtaining approximately the same simplification factor. Copyright © 2014. by the Society for Industrial and Applied Mathematics.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Near-optimal labeling schemes for nearest common ancestors

Near-optimal labeling schemes for nearest common ancestors

引用

25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

作者： Alstrup, Stephen Bistrup Halvorsen, Esben Larsen, Kasper Green Department of Computer Science University of Copenhagen Denmark Department of Computer Science MADALGO - Center for Massive Data Algorithmics Aarhus University Denmark

ISBN: (纸本)9781611973389

We consider NCA labeling schemes: given a rooted tree T, label the nodes of T with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the label of their nearest common ancestor. For trees with n nodes we present upper and lower bounds establishing that labels of size (2 ± Ε)logn, Ε

关键词： Binary trees

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Range Reporting Structures for Categorical data 13

Near-Optimal Range Reporting Structures for Categorical Data

引用

Symposium on Discrete Algorithms

作者： Kasper Green Larsen Freek van Walderveen MADALGO Center for Massive Data Algorithmics Department of Computer Science Aarhus University Denmark.

ISBN: (纸本)9781627484855

Range reporting on categorical (or colored) data is a well-studied generalization of the classical range reporting problem in which each of the N input points has an associated color (category). A query then asks to report the set of colors of the points in a given rectangular query range, which may be far smaller than the set of all points in the query range. We study two-dimensional categorical range reporting in both the word-RAM and I/O-model. For the I/O-model, we present two alternative data structures for three-sided queries. The first answers queries in optimal O(lg_B N + K/B) I/Os using O (N lg* N) space, where K is the number of distinct colors in the output, B is the disk block size, and lg* N is the iterated logarithm of N. Our second data structure uses linear space and answers queries in O(lg_B N + lg~((h)) N + K/B) I/Os for any constant integer h ≥ 1. ***~((1)) N = lg N and lg~(h) N = lg(lg~(h-1)) N) when h > 1. Both solutions use only comparisons on the coordinates. We also show that the lgB N terms in the query costs can be reduced to optimal lglg_B U when the input points lie on a U × U grid and we allow word-level manipulations of the coordinates. We further reduce the query time to just O(1) if the points are given on an N × N grid. Both solutions also lead to improved data structures for four-sided queries. For the word-RAM, we obtain optimal data structures for three-sided range reporting, as well as improved upper bounds for four-sided range reporting. Finally, we show a tight lower bound on one-dimensional categorical range counting using an elegant reduction from (standard) two-dimensional range counting.

关键词： Categorical data all points query range Nominal or categorical data data structures nitrogen search time Coordinates

来源：评论

学校读者我要写书评

暂无评论

Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs 13

Multiway Simple Cycle Separators and I/O-Efficient Algorithm...

引用

Symposium on Discrete Algorithms

作者： Lars Arge Freek van Walderveen Norbert Zeh MADALGO Center for Massive Data Algorithmics Department of Computer Science Aarhus University Denmark. MADALGO Center for Massive Data Algorithmics Department of Computer Science Aarhus -University Denmark. Faculty of Computer Science Dalhousie University Halifax Canada.

ISBN: (纸本)9781627484855

We revisit I/O-efficient solutions to a number of fundamental problems on planar graphs: single-source shortest paths, topological sorting, and computing strongly connected components. Existing I/O-efficient solutions to these problems pay for I/O efficiency using excessive computation time in internal memory, thereby completely negating the performance gain achieved by minimizing the number of disk accesses. In this paper, we show how to make these algorithms simultaneously efficient in internal and external memory so they achieve I/O complexity O(sort(N)) and take O(N log N) time in internal memory, where sort(N) is the number of I/Os needed to sort N items in external memory. The key, and the main technical contribution of this paper, is a multiway version of. Miller's simple cycle separator theorem. We show how to compute these separators in linear time in internal memory, and using O(sort(NV)) I/Os and O(N log N) (internal-memory computation) time in external memory.

关键词： Planar Graphs fundamental problems these problems Memory planning drawings external memory Separators Simple Cycle computational time MULTICHANNEL Disk Access IO

来源：评论

学校读者我要写书评

暂无评论

The Space Complexity of 2-Dimensional Approximate Range Counting 13

The Space Complexity of 2-Dimensional Approximate Range Coun...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Zhewei Wei Ke Yi Center for Massive Data Algorithmics (MADALGO) Aarhus University Department of Computer Science and Engineering The Hong Kong University of Science and Technology

ISBN: (纸本)9781611972511

We study the problem of 2-dimensional orthogonal range counting with additive error. Given a set P of n points drawn from an n×n grid and an error parameter ε, the goal is to build a data structure, such that for any orthogonal range R, the data structure can return the number of points in P ∩ R with additive error εn. A well-known solution for this problem is the ε-approximation. Informally speaking, an ε-approximation of P is a subset A {is contained in} P that allows us to estimate the number of points in P ∩ R by counting the number of points in A ∩ R. It is known that an ε-approximation of size O(1/ε log~(2.5) 1/ε) exists for any P with respect to orthogonal ranges, and the best lower bound is Ω(1/ε log 1/ε).

关键词： Phosphorus data structures space complexities ROENTGEN Orthogonal error parameter

来源：评论

学校读者我要写书评

暂无评论

Morphing Planar Graph Drawings with a Polynomial Number of Steps 13

Morphing Planar Graph Drawings with a Polynomial Number of S...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Soroush Alamdari Patrizio Angelini Timothy M. Chan Giuseppe Di Battista Fabrizio Frati Anna Lubiw Maurizio Patrignani Vincenzo Roselli Sahil Singla Bryan T. Wilkinson David R. Cheriton School of Computer Science University of Waterloo Dipartimento di Informatica e Automazione Roma Tre University School of Information Technologies The University of Sydney MADALGO Center for Massive Data Algorithmics a Center of the Danish National Research Foundation Department of Computer Science Aarhus University

ISBN: (纸本)9781611972511

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n~2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n~4) steps.

关键词： Morphing Planar Graph Drawings Polynomial Number drawings Straight line planning drawings Steps image morphing fixed speed triangulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：