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

An Experimental Study of New and Known online Packet Buffering algorithms

algorithmICA 2010年第4期57卷 725-746页

作者： Albers, Susanne Jacobs, Tobias Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.

关键词： Packet buffering Network switch online algorithm Performance analysis algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

online role mining for context-aware mobile service recommendation

引用

PERSONAL AND UBIQUITOUS COMPUTING 2014年第5期18卷 1029-1046页

作者： Wong, Raymond K. Chu, Victor W. Hao, Tianyong Univ New S Wales Sydney NSW Australia Columbia Univ New York NY USA

Finding and recommending suitable services for mobile devices are increasingly important due to the popularity of mobile Internet. While recent research has attempted to use role-based approaches to recommend services, role discovery is still an ongoing research topic. Using role-based approaches, popular mobile services can be recommended to other members in the same role group in a context- dependent manner. This paper proposes several role mining algorithms, to suit different application requirements, that automatically group users according to their interests and habits dynamically. Most importantly, we propose an online role mining algorithm that can discover role patterns efficiently and incrementally. Finally, we present a complete, question-based framework that can efficiently perform role mining for context-aware service recommendation in a mobile environment-where a device may not be always connected to the server and/or scalability of the role mining algorithm running on the server is critical.

关键词： Role mining online algorithm Incremental Dynamic context-aware Service recommendation Mobile devices

来源：评论

学校读者我要写书评

暂无评论

NF-based algorithms for online bin packing with buffer and bounded item size

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第2期30卷 360-369页

作者： Zheng, Feifeng Luo, Li Zhang, E. Donghua Univ Glorious Sun Sch Business & Management Shanghai 200092 Peoples R China Sichuan Univ Sch Business Chengdu 610064 Peoples R China Shanghai Univ Finance & Econ Sch Informat Management & Engn Shanghai 200433 Peoples R China

This paper studies a variation of online bin packing where there is a capacitated buffer to temporarily store items during packing, and item size is bounded within for some . The problem is motivated by surgery scheduling such that we regard the planned uniform available time interval in each day as a unit size bin and surgeries as items to be packed. Our focus is on the asymptotic performance of NF (Next Fit) and NF-based online algorithms. We show that the classical NF algorithm without use of the buffer has an asymptotic competitive ratio of . An NF-based algorithm which makes use of the buffer is further proposed, and proved to be asymptotic 13/9-competitive for any given buffer size not less than 1. We also present a lower bound of 4/3.

关键词： Bin packing online algorithm Asymptotic competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Auction of Cloud Resources in Support of the Internet of Things

引用

IEEE INTERNET OF THINGS JOURNAL 2017年第5期4卷 1583-1596页

作者： Gharaibeh, Ammar Khreishah, Abdallah Mohammadi, Mehdi Al-Fuqaha, Ala Khalil, Issa Rayes, Ammar German Jordanian Univ Dept Comp Engn Amman 11180 Jordan New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Western Michigan Univ Dept Comp Sci Kalamazoo MI 49008 USA Hamad Bin Khalifa Univ Qatar Comp Res Inst Doha Qatar Cisco Syst Inc San Jose CA 95134 USA

Internet of Things (IoT) applications can benefit greatly from cloud-hosted message broker services that utilize publish-subscribe communications. The operators of IoT cloud-hosted services are often interested in delivering services that maximize their revenue given quality of service guarantees. In this paper, we formulate the problem of maximizing the profit of the service provider given the prior knowledge of the request sequence as an integer linear program and prove that it is strongly NP-complete, and thus there is no fully polynomial-time approximation scheme for the problem, unless P = NP. Due to the above-mentioned problem and the difficulty of obtaining the request sequence in advance in real-world scenarios, we propose an auction-based online algorithm that does not require the prior knowledge of the request sequence. We prove that the competitive ratio of the online algorithm is O(log(N)), where N is the number of cloud zones that host the publish-subscribe services. Moreover, we show that no online algorithm can achieve a competitive ratio better than Omega(log(N)). Therefore, our online algorithm achieves the optimal competitive ratio in the asymptotic sense. Our simulations, based on real data traces, show that our algorithm achieves up to 83% more profit compared to a heuristic approach, while consuming 60% less resources.

关键词： Auction Internet of Things (IoT) online algorithm publish-subscribe communications

来源：评论

学校读者我要写书评

暂无评论

online log parsing using evolving research tree

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2024年第2期66卷 1231-1255页

作者： Vervaet, Arthur Callau-Zori, Mar Chabchoub, Yousra Chiky, Raja 3DS OUTSCALE F-92210 St Cloud France ISEP Inst Super Elect Paris F-92130 Issy Les Moulineaux France

Logs are a reliable source of information for development and maintenance purposes. They record information at runtime regarding the state of a system and are commonly used to analyze its behavior. Parsing operations on logs structure the information embedded within the log message and are a crucial step for many log mining applications. In such use cases, parsing effectiveness can impact performance. For systems that require real-time performance, parsing efficiency is also an important factor. In this paper, we present USTEP, an online log parser that uses an evolving tree structure to encode and discover new parsing rules on the fly. Our evaluation of 14 datasets from different logging environments highlights the superiority of our method in terms of robustness and effectiveness compared to the state of the art. Our analysis of space and time complexity shows that USTEP is the only considered method capable of processing logs in constant time regardless of their length. We also propose here USTEP-UP, a way of running multiple USTEP instances in parallel.

关键词： Log parsing online algorithm Distributed algorithm Log mining

来源：评论

学校读者我要写书评

暂无评论

online Sparse Gaussian Process Regression and Its Applications

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2011年第2期20卷 391-404页

作者： Ranganathan, Ananth Yang, Ming-Hsuan Ho, Jeffrey Honda Res Inst Mountain View CA 94041 USA Univ Calif Dept Elect Engn & Comp Sci Merced CA 95344 USA Univ Florida Dept Comp Informat Sci & Engn Gainesville FL 32607 USA

We present a new Gaussian process (GP) inference algorithm, called online sparse matrix Gaussian processes (OSMGP), and demonstrate its merits by applying it to the problems of head pose estimation and visual tracking. The OSMGP is based upon the observation that for kernels with local support, the Gram matrix is typically sparse. Maintaining and updating the sparse Cholesky factor of the Gram matrix can be done efficiently using Givens rotations. This leads to an exact, online algorithm whose update time scales linearly with the size of the Gram matrix. Further, we provide a method for constant time operation of the OSMGP using matrix downdates. The downdates maintain the Cholesky factor at a constant size by removing certain rows and columns corresponding to discarded training examples. We demonstrate that, using these matrix downdates, online hyperparameter estimation can be included at cost linear in the number of total training examples. We describe a robust appearance-based head pose estimation system based upon the OSMGP. Numerous experiments and comparisons with existing methods using a large dataset system demonstrate the efficiency and accuracy of our system. Further, to showcase the applicability of OSMGP to a wide variety of problems, we also describe a regression-based visual tracking method. Experiments show that our OSMGP algorithm generalizes well using online learning.

关键词： Gaussian process matrix algebra online algorithm pose estimation visual tracking

来源：评论

学校读者我要写书评

暂无评论

online mining of frequent sets in data streams with error guarantee

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2008年第2期16卷 245-258页

作者： Dang, Xuan Hong Ng, Wee-Keong Ong, Kok-Leong Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Deakin Univ Sch Engn & IT Waurn Ponds Vic 3217 Australia

For most data stream applications, the volume of data is too huge to be stored in permanent devices or to be thoroughly scanned more than once. It is hence recognized that approximate answers are usually sufficient, where a good approximation obtained in a timely manner is often better than the exact answer that is delayed beyond the window of opportunity. Unfortunately, this is not the case for mining frequent patterns over data streams where algorithms capable of online processing data streams do not conform strictly to a precise error guarantee. Since the quality of approximate answers is as important as their timely delivery, it is necessary to design algorithms to meet both criteria at the same time. In this paper, we propose an algorithm that allows online processing of streaming data and yet guaranteeing the support error of frequent patterns strictly within a user-specified threshold. Our theoretical and experimental studies show that our algorithm is an effective and reliable method for finding frequent sets in data stream environments when both constraints need to be satisfied.

关键词： data mining frequent set mining data stream online algorithm error guarantee

来源：评论

学校读者我要写书评

暂无评论

online knapsack of unknown capacity How to optimize energy consumption in smartphones

引用

THEORETICAL COMPUTER SCIENCE 2017年 697卷 98-109页

作者： Navarra, Alfredo Pinotti, Cristina M. Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 I-06123 Perugia Italy

We propose a new variant Of the standard online knapsack problem where the only information missing to the provided instances is the capacity B of the knapsack. We refer to this problem as the online Knapsack of Unknown Capacity (KUC) problem. Any algorithm solving the KUC problem must provide a strategy for filling online the knapsack until its capacity is revealed. When the knapsack capacity is revealed, no other item can be inserted and also the last inserted item is discarded if it does not completely fit in the knapsack. Apart for the interest in a new version of the fundamental knapsack problem, the motivations that lead to define this new variant come from energy consumption constraints in smartphones communications. We provide lower and upper bounds to the problem for various cases. In general, we design an optimal algorithm admitting a :1/2-competitive ratio. When all items admit uniform ratio of profit over size, our algorithm provides a 49/86 = .569 ... competitive ratio that leaves some gap with the provided bound of 1/phi =.618 ..., the inverse of the golden number. We then conduct experimental analysis for the competitive ratio guaranteed algorithms compared to the optimum and to various heuristics. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Knapsack online algorithm Competitive ratio Energy optimization Smartphone

来源：评论

学校读者我要写书评

暂无评论

A good balance for an online scheduling problem considering both learning and deteriorating effects in the handicraft process

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2024年第7期75卷 1294-1307页

作者： Ma, Ran Yang, Xiaohua Han, Wenwen Liu, Aijun Qingdao Univ Technol Sch Management Engn Qingdao Peoples R China Xidian Univ Sch Econ & Management Dept Management Engn Xian Peoples R China Qingdao Univ Technol Sch Management Engn Qingdao 266520 Peoples R China

The paper considers an online scheduling problem with the effects of both learning and deterioration to minimize the total completion time. More specifically, we assume that the actual processing length of job J(j) is p(jr) = p(j)r(b) thorn at, where p(j) is the initial processing time of J(j), t is the starting time of J(j), r is the seating arrangement position of J(j), b is the learning factor and a is the deterioration factor, respectively. For this problem, we show that the performance ratio of any deterministic online algorithm is not <2 and provide a best possible online algorithm DSBPT with a competitive ratio of 2. Furthermore, we also present a concise computational simulation study to verify the effectiveness and efficiency of the proposed algorithm DSBPT, as well as the management implications provided for decisionmakers to production optimization.

关键词： Scheduling online algorithm learning effects deteriorating effects handicraft

来源：评论

学校读者我要写书评

暂无评论

online scheduling in a parallel batch processing system to minimize makespan using restarts

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期374卷 196-202页

作者： Fu, Ruyan Tian, Ji Yuan, Jinjiang Lin, Yixun Zhengzhou Univ Dept Math Zhengzhou 450052 Peoples R China

We consider an online scheduling problem in a parallel batch processing system with jobs in a batch being allowed to restart. online means that jobs arrive over time, and all jobs' characteristics are unknown before their arrival times. A parallel batch processing machine can handle up to several jobs simultaneously. All jobs in a batch start and complete at the same time. The processing time of a batch is equal to the longest processing time of jobs in the batch. We are allowed to restart a batch, that is, a running batch may be interrupted, losing all the work done on it. Jobs in the interrupted batch are released and become independently unscheduled jobs. We deal with an unbounded model where each batch's capacity is sufficiently large. We provide a linear online algorithm with competitive ratio 3/2 for the problem. We also show that the considered problem has no online algorithm using restarts with competitive ratio less than (5 - root 5)/2. (C) 2007 Elsevier B.V. All rights reserved.

关键词： single machine scheduling parallel batch online algorithm restart competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：