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

ACM Journal of Experimental algorithmics 2004年 9卷 1.6–es页

作者： Goh, Rick Siow Mong Thng, Ian Li-Jin Department of Electrical and Computer Engineering National University of Singapore Computer Communication Network Laboratory 3 Engineering Drive 3 E4A #05-06 Singapur 117576 Singapore

Priority queues are essential function blocks in numerous applications such as discrete event simulations. This paper describes and exemplifies the ease of obtaining high performance priority queues using a two-tier list-based structure. This new implementation, called the Twol structure, is amalgamated with three priority queues, namely, the Henriksen's queue, splay tree and skew heap, to enhance the efficiency of these basal priority queue structures. Using a model that combines traditional average case and amortized complexity analysis, Twol-amalgamated priority queues that maintain N active events are theoretically proven to offer O(1) expected amortized complexity under reasonable assumptions. They are also demonstrated empirically to offer stable near O(1) performance for widely varying priority increment distributions and for queue sizes ranging from 10 to 10 million. Extensive empirical results show that the Twol-amalgamated priority queues consistently outperform those basal structures (i.e., without the Twol structure) with an average speedup of about three to five times on widely different hardware architectures. These results provide testimony that the Twol-amalgamated priority queues are suitable for implementation in sizeable application scenarios such as, but not limited to, large-scale discrete event simulation. © 2005 ACM.

关键词： 1.6 [computing methodologies]: simulation and modeling algorithm analysis algorithms Calendar queue Design Discrete event simulation E.1 [data]: data structures Experimentation F.2 [theory of computation]: analysis of algorithms and problem complexity Future event list Henriksen's Pending event set Performance Priority queue Simulator Skew heap Splay tree Theory Tree Verification

来源：评论

学校读者我要写书评

暂无评论

Solving the pharaoh's golden staircase problem through dynamic programming

Journal of Computing Sciences in Colleges

引用

Journal of Computing Sciences in Colleges 2004年第1期20卷

作者： Daniel E. Nohl Benedictine University Lisle IL

The Pharaoh's Golden Staircase problem is an excellent example of a puzzle that is easily solved through dynamic programming. Puzzles that have dynamic programming solutions and are also interesting to students are very rare. This paper describes the problem, illustrates a solution, and analyzes the efficiency of that solution. This analysis uses discrete mathematics. Therefore, this puzzle not only is useful in the classroom as dynamic programming application but also provides the opportunity to apply mathematics from the course which is a standard in most computer science curricula.

关键词： algorithm analysis dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Digital filters in adaptive time-stepping

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2003年第1期29卷 1-26页

作者： Söderlind, G Lund Univ Ctr Math Sci SE-22100 Lund Sweden

Adaptive time-stepping based on linear digital control theory has several advantages: the algorithms can be analyzed in terms of stability and adaptivity, and they can be designed to produce smoother stepsize sequences resulting in significantly improved regularity and computational stability. Here, we extend this approach by viewing the closed-loop transfer map H-(φ) over cap: log (φ) over cap bar right arrow log h as a digital filter, processing the signal log (φ) over cap ( the principal error function) in the frequency domain, in order to produce a smooth stepsize sequence log h. The theory covers all previously considered control structures and offers new possibilities to construct stepsize selection algorithms in the asymptotic stepsize-error regime. Without incurring extra computational costs, the controllers can be designed for special purposes such as higher order of adaptivity ( for smooth ODE problems) or a stronger ability to suppress high-frequency error components (nonsmooth problems, stochastic ODEs). Simulations verify the controllers' ability to produce stepsize sequences resulting in improved regularity and computational stability.

关键词： algorithms theory adaptivity algorithm analysis control theory digital filters error control mathematical software stepsize control

来源：评论

学校读者我要写书评

暂无评论

A heuristic for mining association rules in polynomial time

引用

MATHEMATICAL AND COMPUTER MODELLING 2003年第1-2期37卷 219-233页

作者： Yilmaz, E Triantaphyllou, E Chen, J Liao, TW Louisiana State Univ Dept Ind & Mfg Syst Engn Baton Rouge LA 70803 USA Gen Elect Card Serv Inc Stamford CT 06927 USA

Mining association rules from databases has attracted great interest because of its potentially very practical applications, Given a database, the problem of interest is how to mine association rules (which could describe patterns of consumers' behaviors) in an efficient and effective way, The databases involved in today's business environments can be very large. Thus, fast and effective algorithms are needed to mine association rules out of large databases, Previous approaches may cause an exponential computing resource consumption. A combinatorial explosion occurs because existing approaches exhaustively mine all the rules. The proposed algorithm takes a previously developed approach, called the Randomized algorithm 1 (or RA1), and adapts it to mine association rules out of a database in an efficient way. The original RA1 approach was primarily developed for inferring logical clauses (i.e., a Boolean function) from examples. Numerous computational results suggest that the new approach is very promising. (C) 2003 Elsevier Science Ltd. All rights reserved.

关键词： data mining association rules algorithm analysis one clause at a time (OCAT) approach randomized algorithms heuristics boolean functions

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for an electronic commerce money distribution system

引用

algorithmICA 2002年第3期33卷 287-299页

作者： Kawazoe, H Shibuya, T Tokuyama, T IBM Japan Ltd Ind eApplicat Sales eBusiness Solut Chuo Ku Tokyo 1038510 Japan Tokyo Res Lab IBM Res Div Yamato Kanagawa 2428502 Japan Tohoku Univ Grad Sch Informat Sci Aoba Ku Sendai Miyagi 9808577 Japan

We consider the money distribution problem for a micro-payment scheme using a distributed server system: in particular, for an automatic charging scheme named PayPerClick that allows Internet users to view Web pages for which access charges are levied without tedious payment procedures. A major bottleneck in the scheme is the network traffic caused by the distribution of electronic money to many different servers. We propose a simple online algorithm for distributing electronic money to servers, so that the network traffic is minimized. The algorithm achieves the optimal online competitive ratio. We also consider a weighted version, for which we give an asymptotically optimal online algorithm within a constant factor.

关键词： online algorithm algorithm analysis electronic commerce money distribution system PayPerClick

来源：评论

学校读者我要写书评

暂无评论

Indexing techniques for file sharing in scalable peer-to-peer networks

Indexing techniques for file sharing in scalable peer-to-pee...

引用

11th International Conference on Computer Communications and Networks

作者： Annexstein, FS Berman, KA Jovanovic, MA Ponnavaikko, K Univ Cincinnati Dept ECECS Cincinnati OH 45221 USA

ISBN: (纸本)078037553X

File sharing is a very popular service provided by peer-to-peer (P2P) networks. In a P2P file-sharing network, users share files and issue queries to the network to find the locations of the riles residing at other peer nodes. Due to factors such as large user base and use of query broadcast protocols, each node in the network receives many search queries every second. Recently network developers have incorporated proxy-enabled peers, or supernodes, which are designed to enhance scalability by providing indexing services to nodes on slower network connections. Typically, supernodes build a vector or multi-index of all the filenames of the shared files stored on other (slower) peers nodes connected to them. In this paper we consider a new model whereby the index tables of the individual nodes are merged into a single data structure stored by the supermode. We analyze this new model in relation to the standard vectorized data structure. We compare the performance of these supernode indexing algorithms and provide a theoretical analysis that is asymptotic and probabilistic in nature. However, there are several significant constant factors that the theory does not account for, and which in practice are important for designing an optimal system solution. We report herein on a series of simulation experiments which provide 1) verification of the asymptotic analysis of the formal framework, and 2) tools to determine the magnitude of the constant factors involved in the performance analysis. Our general conclusion is that when the query rate exceeds the rate of data updates, the new merged model is preferable to the vector model. However, the details of our analysis allow us to consider combinations of several parameters, and thereby enable the design of optimal indexing schemes via the incorporation of measurements of the parameters of particular applications.

关键词： peer-to-peer computing text indexing file sharing algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Teaching students to use genetic algorithms to solve optimization problems

Journal of Computing Sciences in Colleges

引用

Journal of Computing Sciences in Colleges 2001年第3期16卷

作者： John G. Meinke Michelle Moore Univ. of System of Maryland Texas A&M University Corpus Christi Corpus Christi TX

Genetic algorithms have been used to solve a wide variety of problems. They have proven to be of notable usefulness in solving optimization problems of all kinds. Because of this, I believe that Genetic algorithms should be taught routinely in algorithms and algorithm analysis classes. My experience has shown that adding instruction about the implementation of Genetic algorithms enhances student understanding of approximation algorithms and does not take an unreasonable amount of time away from the other *** workstations supplied by National Science Foundation DUE-ILI grant #9651290 provided the computing environment used for the work reported here.

关键词： algorithm analysis genetic algorithms optimization problems teaching algorithm concepts

来源：评论

学校读者我要写书评

暂无评论

Bias error analysis of the generalised Hough transform

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2000年第1期12卷 25-42页

作者： Aguado, AS Montiel, E Nixon, MS INRIA Rhone Alpes Grenoble France IMAGIS GRAVIR IMAG F-38041 Grenoble 9 France Univ Southampton Southampton SO9 5NH Hants England

The generalised Hough transform (GHT) extends the Hough transform (HT) to the extraction of arbitrary shapes. In practice, the performance of both techniques differs considerably. The literature suggests that, whilst the HT can provide accurate results with significant levels of noise and occlusion, the performance of the GHT is in fact much more sensitive to noise. In this paper we extend previous error analyses by considering the possible causes of bias errors of the GHT. Our analysis considers both formulation and implementation issues. First, we compare the formulation of the GHT against the general formulation of the standard HT. This shows that, in fact, the GHT definition increases the robustness of the standard HT formulation. Then, in order to explain this paradoxical situation we consider four possible sources of errors that are introduced due to the implementation of the GHT: (i) errors in the computation of gradient direction;(ii) errors due to false evidence attributed to the range of values defined by the point spread function;(iii) errors due to the contribution of false evidence by background points;and (iv) errors due to the non-analytic (i.e., tabular) representation used to store the properties of the model. After considering the effects of each source of error we conclude that: (i) in theory, the GHT is actually more robust than the standard HT;(ii) that clutter and occlusion have a reduced effect in the GHT with respect to the HT;and (iii) that a significant source of error can be due to the use of a non-analytic representation. A non-analytic representation defines a discrete point spread function that is mapped into a discrete accumulator array. The discrete point spread function is scaled and rotated in the gathering process, increasing the amount of inaccurate evidence. Experimental results demonstrate that the analysis of errors is congruent with practical implementation issues. Our results demonstrate that the GHT is more robust than the H

关键词： algorithm analysis error analysis object detection shape extraction Hough transform generalised Hough transform

来源：评论

学校读者我要写书评

暂无评论

On the variance of the internal path length of generalized digital trees - The Mellin convolution approach

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期242卷 143-168页

作者： Hubalek, F Univ Vienna Inst Stat A-1210 Vienna Austria

This paper studies a generalization of the internal path length of a random digital search tree to bucket trees, which are capable of storing up to b records per node. We show that under the assumption of the symmetric Bernoulli probabilistic model the expected path length of a tree built from N records is asymptotically Nlog(2)N + (A + delta(1)(log(2)N))N and the variance is (C + epsilon(1)(log(2)N))N, where A and C depend on b only. The continuous functions delta(1) and epsilon(1) are periodic with mean 0 and period 1. The proof's are analytical and make use of generating functions, harmonic sums and the Mellin integral transform. An important and very general tool for the analysis is Mellin's convolution integral. These results and techniques are motivated by a paper by Flajolet and Richmond and by Kirschenhofer, Prodinger, and Szpankowski. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： digital search trees algorithm analysis mellin transform

来源：评论

学校读者我要写书评

暂无评论

The application of genetic algorithms to knowledge discovery and data mining

Journal of Computing Sciences in Colleges

引用

Journal of Computing Sciences in Colleges 2000年第3期15卷

作者： James W. Newsorn Timothy P. Donovan Midwestern State University Wichita Falls Texas

Knowledge discovery is a new discipline that applies machine learning techniques to large real-world databases to extract knowledge from the data. This knowledge is often expressed as rules modeling the data. Genetic algorithms (GA) are a unique method for evolving high quality solutions from a potentially huge search space of possible solutions. This technique uses a simulated process of natural selection rather than a simulated reasoning process. Genetic algorithms are uniquely suited to data mining problems due to the inductive nature of the problem. This paper describes two GA-based data mining systems, GA-MINIR, a pure GA technique, and DOGMA, a hybrid technique, using GAs to improve on rules generated by another classifier. It also discusses the difficulty of formally analyzing a genetic algorithm in order to compare it with more conventional methods of solving the same problem.

关键词： algorithm analysis data mining genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：