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

Simple algorithms for the on-line multidimensional dictionary and related problems

ALGORITHMICA 2000年第2期28卷 255-267页

作者： Gonzalez, TF Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

The on-line multidimensional dictionary problem consists of executing on-line any sequence of the following operations: INSERT(p), DELETE(p), and MEMBERSHIP(p), where p is any (ordered) d-tuple (Or String with d elements, or points in d-space where the dimensions have been ordered). We introduce a clean structure based on balanced binary search trees, which we call multidimensional balanced binary search trees, to represent the set of d-tuples. We present algorithms for each of the above operations that take O(d + log n) time, where n is the current number of d-tuples in the set, and each INSERT and DELETE operation requires no more than a constant number of rotations. Our structure requires dn words to represent the input, plus O(n) pointers and data indicating the first component where pairs of d-tuples differ. This information, which can be easily updated, enables us to test for MEMBERSHIP efficiently. Other operations that can be performed efficiently in our multidimensional balanced binary search trees are: print in lexicographic order(O (dn) time), find the (lexicographically) smallest or largest d-tuple (O(log n) time), and concatenation (O (d + log n) time). Finding the (lexicographically) kth smallest or largest d-tuple can also be implemented efficiently (O(log n) time), at the expense of adding an integer value at each node.

关键词： multidimensional dictionary on-line algorithms data structures

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line stream merging algorithms for media-on-demand

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第1期48卷 59-90页

作者： Bar-Noy, A Ladner, RE CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We consider the problem of minimizing the bandwidth needed by media-on-demand servers that use stream merging. We consider the on-line case where client requests are not known ahead of time. To facilitate stream merging, clients have the ability to receive data from two streams simultaneously and can buffer up to half of a full stream. We present a new family of on-line stream merging algorithms called dynamic tree algorithms. The bandwidth requirements of the best of these, the dynamic Fibonacci tree algorithms, are within a factor of the minimum between log(phi)(n) + 0(l) and log(phi)(1/(2D)) + 0(l) from the off-line optimal, where n is the number of requests, D is the guaranteed maximum start-up delay measured as a fraction of the time for a full stream, and phi = (I + root5)/2. The new on-line algorithms use a dynamic Fibonacci tree to control how new arrivals should merge with existing streams. Empirical studies show that the dynamic Fibonacci tree algorithms perform much better than indicated by the analysis. (C) 2003 Elsevier Inc. All rights reserved.

关键词： video-on-demand stream merging on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line stream merging algorithms for media-on-demand

Competitive on-line stream merging algorithms for media-on-d...

引用

12th Annual ACM-SIAM Symposium on Discrete algorithms

作者： Bar-Noy, A Ladner, RE CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

ISBN: (纸本)0898714907

关键词： video-on-demand stream merging on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Randomized algorithms for the on-line minimum matching problem on Euclidean space

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1995年第1-2期58卷 19-32页

作者： Tsai, YT Tang, CY Chen, YY NATL TSING HUA UNIV DEPT COMP SCIHSINCHU 300TAIWAN

Suppose we are given two sets R and B, each of n points in the plane. Define the cost of a matching to be the teal distance of the edges in the, matching. The minimum matching problem on Euclidean space is to find a complete bipartite matching which has the minimum cost on Euclidean space. In this paper, we are interested in the on-line minimum matching problem on Euclidean space. We assume the set R is known, but the points of set B are revealed one by one. When a point of set B arrives, we must decide what match to make involving the point. None of the matches can be changed after they are made. The on-line minimum matching problem on Euclidean space tries to minimize the cost of the complete bipartite matching that we find. This paper proposes a family of randomized algorithms, Algorithm RM(m) (1 less than or equal to m less than or equal to n), for solving this problem. When a point in the set B arrived, Algorithm RM(m) randomly chooses at most m unmatched points in the set R, and adds the minimum edge between the arriving point and the chosen points to the matching. In each decision step, the algorithm only runs in O(m) time, which is superior to the known non-randomized algorithms for this problem. In this paper, we show that Algorithm RM(m) is not a competitive on-line algorithm for 1 less than or equal to m less than or equal to n-1. However, we further show that if 2n is large, the average cost incurred by Algorithm RM(m) (1 less than or equal to m less than or equal to n) is bounded by O(root n) times the average cost of the optimal Euclidean minimum matching.

关键词： analysis of algorithms on-line algorithms randomized algorithms the on-line minimum matching problem competitive analysis average case analysis

来源：评论

学校读者我要写书评

暂无评论

Bounded space on-line bin packing: Best is better than first

引用

ALGORITHMICA 2001年第2期31卷 115-138页

作者： Csirik, J Johnson, DS Univ Szeged Dept Comp Sci Szeged Hungary AT&T Labs Res Florham Park NJ 07932 USA

We present a sequence of new linear-time, bounded-space, on-line bin packing algorithms, the K-Bounded Best Fit algorithms (BBFK). They are based on the Theta (n log n) Best Fit algorithm in much the same way as the Next-K Fit algorithms are based on the Theta (n log n) First Fit algorithm. Unlike the Next-K Fit algorithms, whose asymptotic worst-case ratios approach the limiting value of 17 from above as K --> infinity but never reach it, these new algorithms have worst-case ratio 17/10 for all K greater than or equal to 2. They also have substantially better average performance than their bounded-space competition, as we have determined based on extensive experimental results summarized here for instances with item sizes drawn independently and uniformly from intervals of the form (0, u], 0 < u 1. Indeed, for each u < 1, it appears that there exists a fixed memory bound K(u) such that BBFK(u) obtains significantly better packings on average than does the First Fit algorithm, even though the latter requires unbounded storage and has a significantly greater running time. For u = 1, BBFK can still outperform First Fit (and essentially equal Best Fit) if K is allowed to grow slowly. We provide both theoretical and experimental results concerning the growth rates required.

关键词： bin packing on-line algorithms first fit best fit

来源：评论

学校读者我要写书评

暂无评论

New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 2003年第3期21卷 270-313页

作者： Estan, C Varghese, G Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive ( using SRAM) or slow ( using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow), which count periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift by concentrating the measurement process on large flows only - those above some threshold such as 0.1% of the link capacity. We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/M;by contrast, the error of an algorithm based on classical sampling is proportional to 1/rootM, thus providing much less accuracy for the same amount of memory. We also describe optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

关键词： algorithms measurement network traffic measurement usage based accounting scalability on-line algorithms identifying large flows

来源：评论

学校读者我要写书评

暂无评论

Greedy online frequency allocation in cellular networks

引用

INFORMATION PROCESSING LETTERS 2007年第2-3期102卷 55-61页

作者： Chan, Joseph Wun-Tat Chin, Francis Y. L. Ye, Deshi Zhang, Yong Zhu, Hong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Kings Coll London Dept Comp Sci London WC2R 2LS England

The online frequency allocation problem for cellular networks has been well studied in these years. Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are served by assigning frequencies to them, and no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online setting that the calls arrive one by one, the problem is to minimize the span of the frequencies used. In this paper, we study the greedy approach for the online frequency allocation problem, which assigns the minimal available frequency to a new call so that the call does not interfere with calls of the same cell or neighboring cells. If the calls have infinite duration, the competitive ratio of greedy algorithm has a tight upper bound of 17/7, which closes the gap of [17/7, 2.5) in [I. Caragiannis, C. Kaklamanis, E. Papaioannou, Efficient on-line frequency allocation and call control in cellular networks, Theory Comput. Syst. 35 (5) (2002) 521-543. A preliminary version of the paper appeared in SPAA 2000]. If the calls have finite duration, i.e., each call may be terminated at some time, the competitive ratio of the greedy algorithm has a tight upper bound of 3. (c) 2006 Elsevier B.V. All rights reserved.

关键词： on-line algorithms frequency allocation competitive analysis greedy algorithm cellular network

来源：评论

学校读者我要写书评

暂无评论

Average case analyses of list update algorithms, with applications to data compression

引用

ALGORITHMICA 1998年第3期21卷 312-318页

作者： Albers, S Mitzenmacher, M Max Planck Inst Informat D-66123 Saarbrucken Germany Digital Equipment Corp Syst Res Ctr Palo Alto CA 94301 USA

We study the performance of the Timestamp (0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such sources, and determine performance ratios for TS(0) against the optimal off-line and static adversaries in this situation. Previous work on such sources compared on-line algorithms only with static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(0) in place of Move-to-front in schemes that use the latter should improve compression. Tests using implementations on a standard corpus of test documents demonstrate that TS(0) leads to improved compression.

关键词： on-line algorithms competitive analysis list update problem probability distribution data compression entropy

来源：评论

学校读者我要写书评

暂无评论

OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 22-40页

作者： Brodal, Gerth Stolting Moruz, Gabriel Negoescu, Andrei Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8200 Aarhus N Denmark Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

关键词： on-line algorithms Competitive analysis Paging Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An average case analysis of a greedy algorithm for the on-line Steiner tree problem

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1996年第11期31卷 121-131页

作者： Tsai, YT Tang, CY Chen, YY Department of Computer Science National Tsing Hua University Hsinchu 300 Taiwan R.O.C.

This paper gives the average distance analysis for the Euclidean tree constructed by a simple greedy but efficient algorithm of the on-line Steiner tree problem. The algorithm accepts the data one by one following the order of input sequence. When a point arrives, the algorithm adds the shortest edge, between the new point and the points arriving already, to the previously constructed tree to form a new tree. We first show that, given n points uniformly on a unit disk in the plane, the expected Euclidean distance between a point and its j(th) (1 less than or equal to j less than or equal to n - 1) nearest neighbor is less than or equal to (5/3)root/j/n when n is large. Based upon this result, we show that the expected length of the tree constructed by the on-line algorithm is not greater than 4.34 times the expected length of the minimum Steiner tree when the number of input points is large.

关键词： analysis of algorithms on-line algorithms average case analysis on-line Steiner tree problems Euclidean space

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：