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

High-dimensional, multiscale online changepoint detection

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY 2022年第1期84卷 234-266页

作者： Chen, Yudong Wang, Tengyao Samworth, Richard J. Univ Cambridge Cambridge England London Sch Econ & Polit Sci London England UCL London England

We introduce a new method for high-dimensional, online changepoint detection in settings where a p-variate Gaussian data stream may undergo a change in mean. The procedure works by performing likelihood ratio tests against simple alternatives of different scales in each coordinate, and then aggregating test statistics across scales and coordinates. The algorithm is online in the sense that both its storage requirements and worstcase computational complexity per new observation are independent of the number of previous observations;in practice, it may even be significantly faster than this. We prove that the patience, or average run length under the null, of our procedure is at least at the desired nominal level, and provide guarantees on its response delay under the alternative that depend on the sparsity of the vector of mean change. Simulations confirm the practical effectiveness of our proposal, which is implemented in the R package ocd, and we also demonstrate its utility on a seismology data set.

关键词： average run length detection delay high-dimensional changepoint detection online algorithm sequential method

来源：评论

学校读者我要写书评

暂无评论

Robust Load Balancing with Machine Learned Advice

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2023年第1期24卷 1-46页

作者： Ahmadian, Sara Esfandiari, Hossein Mirrokni, Vahab Peng, Binghui Google Res New York NY 10011 USA Columbia Univ New York NY 10027 USA

Motivated by the exploding growth of web-based services and the importance of efficiently managing the computational resources of such systems, we introduce and study a theoretical model for load balancing of very large databases such as commercial search engines. Our model is a more realistic version of the well-received balls-into-bins model with an additional constraint that limits the number of servers that carry each piece of the data. This additional constraint is necessary when, on one hand, the data is so large that we can not copy the whole data on each server. On the other hand, the query response time is so limited that we can not ignore the fact that the number of queries for each piece of the data changes over time, and hence we can not simply split the data over different machines. In this paper, we develop an almost optimal load balancing algorithm that works given an estimate of the load of each piece of the data. Our algorithm is almost perfectly robust to wrong estimates, to the extent that even when all of the loads are adversarially chosen the performance of our algorithm is 1 - 1/e, which is provably optimal. Along the way, we develop various techniques for analyzing the balls-into-bins process under certain correlations and build a novel connection with the multiplicative weights update scheme.

关键词： online algorithm learning augmented algorithm design machine learned prediction load balancing balls and bins

来源：评论

学校读者我要写书评

暂无评论

Reducing passenger waiting time in oversaturated metro lines with passenger flow control policy

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2023年 117卷

作者： Liang, Jinpeng Zang, Guangzhi Liu, Haitao Zheng, Jianfeng Gao, Ziyou Dalian Maritime Univ Sch Transportat Engn Dalian Peoples R China China Acad Railway Sci Corp Ltd Inst Comp Technol Beijing Peoples R China Sichuan Univ Business Sch Chengdu Peoples R China Beijing Jiaotong Univ Sch Traff & Transportat Beijing Peoples R China

Oversaturation during peak hours brings about severe challenges for metro operations management in megacities. It can deteriorate passengers' service level experience and increase the safety risk at congested platforms. This paper focuses on designing an online passenger flow control policy to manage passenger flow in each origin-destination (OD) pair so that the total passenger waiting time during the research horizon can be minimized. Suppose that the OD demand information reveals sequentially over time, we formulate the online passenger flow control problem as stochastic dynamic programming (DP). An efficient online adaptive policy is designed to guide the real-time flow control decisions at each stage. To evaluate the performance of our approach, we exploit the realistic transit data from the Beijing metro system to carry out a series of numerical experiments. The computational results show that our approach can significantly reduce the expected total passenger waiting time as well as alleviate metro station congestion compared with the first-come-first-serve (FCFS) policy. The benefits of our approach are obtained by exploiting the reusable nature of train capacity to transport more passengers during rush hours.(c) 2023 Elsevier Ltd. All rights reserved.

关键词： metro system oversaturation passenger flow control online algorithm stochastic dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Mechanism design for Mobility-as-a-Service platform considering travelers' strategic behavior and multidimensional requirements

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2023年第1期173卷 1-30页

作者： Ding, Xiaoshu Qi, Qi Jian, Sisi Yang, Hai Hong Kong Univ Sci & Technol Dept Civil & Environm Engn Kowloon Clear Water Bay Hong Kong Peoples R China Renmin Univ China Gaoling Sch Artificial Intelligence Beijing Key Lab Big Data Management & Anal Methods Beijing Peoples R China

Mobility-as-a-Service (MaaS) is an emerging transport model which provides access to a combination of travel modes through a single platform. A MaaS operator sits between travelers and transport service providers (TSPs), acting as a broker who purchases mobility resources from individual TSPs, constructs seamless transport services, and then sells them to travelers in response to their demand. To ensure the sustainability of such platforms, the key challenge lies in matching travelers to TSPs so that travelers' individual needs are satisfied, TSPs gain nonnegative profits and system efficiency is achieved. To solve this matching and pricing problem, travelers' truthful valuations and travel requirements are needed, while such information is usually unknown to operators beforehand. In this study, we develop an auction-based online mobility resource allocation and pricing mechanism to solve this problem, taking into account travelers' strategic behavior. We first propose an offline (static) mechanism using a Vickrey-Clarke-Groves (VCG) based pricing scheme to ensure incentive compatibility, individual rationality, and system efficiency. We then develop an online mechanism based on the dynamic learning algorithm to obtain the near-optimal solution and compare it to a customized greedy based algorithm. We compare both online mechanisms to the offline VCG based mechanism and theoretically prove the competitive ratios. The efficiency and performance of the proposed mechanisms are demonstrated through a numerical study.

关键词： Mobility-as-a-Service (MaaS) Mechanism design Auction Resource allocation online algorithm

来源：评论

学校读者我要写书评

暂无评论

Random Access Protocol for Massive Internet of Things Connectivity in Space–Air–Ground-Integrated Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2023年第23期10卷 20442-20457页

作者： Park, Joohan Youn, Jiseung Oh, Joohyun Im, Jeongju Ahn, Seyoung Kim, Soohyeong Cho, Sunghyun Hanyang Univ Dept Comp Sci & Engn Ansan 15588 South Korea Hanyang Univ Dept Comp Sci & Engn Bio Artificial Intelligence Ansan 15588 South Korea Hanyang Univ Dept Appl Artificial Intelligence Bioartificial Intelligence Ansan 15588 South Korea

Space-air-ground-integrated networks (SAGINs) are receiving a lot of attention as a candidate for an extension to nonterrestrial networks beyond the limit of terrestrial networks. SAGIN can be a means to satisfy various Quality of Service (QoS) by providing several communication links in different characteristics. To fully utilize the advantage of SAGIN, a protocol for informing user equipment (UE) of an appropriate base station layer of SAGIN is needed according to QoS requirements. In addition, the development of the protocol should consider the characteristics of the UE. In particular, when the UE is a machine-type communication device (MTCD) constituting a massive Internet of Things network, random access congestion issue should be considered. To solve the problems, we propose a random access protocol. We propose an indicator named the virtual deadline indicator (VDI) to inform MTCD which layer to try for random access. MTCD attempts random access to one layer of SAGIN by comparing the remaining deadlines of traffic and the point of the VDI. To minimize the deadline expiration rate, we propose an algorithm to shift the VDI position. The base station estimates the number of MTCDs and remaining deadline distribution by using the number of idle preambles to find the VDI location. Finally, we compare the performance of the protocol through simulation with three benchmark schemes. We confirm that the proposed protocol reduces the deadline expiration rate without compromising the Age of Information and energy efficiency.

关键词： Congestion control massive Internet of Things (IoT) online algorithm random access space-air-ground-integrated network (SAGIN)

来源：评论

学校读者我要写书评

暂无评论

An online multi-source summarization algorithm for text readability in topic-based search

引用

COMPUTER SPEECH AND LANGUAGE 2021年 66卷 101143-101143页

作者： Curiel, Arturo Gutierrez-Soto, Claudio Rojano-Caceres, Jose-Rafael Univ Veracruzana CONACYT Xalapa Veracruz Mexico Univ Veracruzana Fac Estadist & Informat Xalapa Veracruz Mexico Univ Bio Bio Dept Sistemas Informac Concepcion Chile

Web search users are likely to face problems related to the availability of large amounts of data. As the quantity of online content grows, the risk of missing relevant information during search can only increase. Moreover, external variables such as the users' reading proficiency level can further complicate the task. This article proposes an online multi-document summarization algorithm for text readability, as a means to simplify web search. The algorithm is designed to work over collections of topic-related documents, such as the ones returned as the results to a web query. Contrary to most modern approaches, no preliminary training for the algorithm is required. The algorithm was tested in both English and Spanish language documents, using different metrics of term and sentence relevance. The results were compared against summaries created by both human summarizers and third-party Automatic Text Summarization (ATS) systems in terms of two variables: readability and information content. In both variables, the results show generalized gains with respect to both the human summarizers and the third-party ATS systems. Furthermore, the algorithm achieved these results with a time complexity strictly lower than O(n(2));well below traditional machine learning approaches. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Automatic text summarization Text readability online algorithm Information retrieval

来源：评论

学校读者我要写书评

暂无评论

TaOPT: Tool-Agnostic Optimization of Parallelized Automated Mobile UI Testing 25

TaOPT: Tool-Agnostic Optimization of Parallelized Automated ...

引用

30th International Conference on Architectural Support for Programming Languages and Operating Systems-ASPLOS

作者： Ran, Dezhi Song, Zihe Wang, Wenyu Yang, Wei Xie, Tao MOE Key Lab HCST PKU Beijing Peoples R China Peking Univ SCS Beijing Peoples R China Univ Texas Dallas Richardson TX USA Univ Illinois Champaign IL USA

ISBN: (纸本)9798400710797

The emergence of modern testing clouds, equipped with a vast array of real testing devices and high-fidelity emulators, has significantly increased the need for parallel automated mobile testing to optimally utilize the resources of testing clouds. Parallel testing aligns perfectly with the characteristic of rapid iteration cycles for mobile app development, where testing time is limited. While numerous tools have been proposed for optimizing the testing effectiveness on a single testing device, it remains an open problem to optimize the parallelization of automated mobile UI testing in terms of resource and time utilization. To optimize the parallelization of automated mobile UI testing, in this paper, we propose TaOPT, a fully automated, tool-agnostic approach, which improves the parallelization effectiveness of any given testing tool without modifying the tool's internal workflow. In particular, TaOPT conducts online analysis to infer loosely coupled UI subspaces in the App Under Test (AUT). TaOPT then manages access to these subspaces across various testing devices, guiding automated UI testing toward distinct subspaces on different devices without knowing the testing tool's internal workflow. We apply TaOPT on 18 highly popular mobile apps with three state-of-the-art automated UI testing tools for Android. Evaluation results show that TaOPT helps the tools reach comparable code coverage using 60% less testing duration and 62% less machine time than the baseline on average. In addition, TaOPT consistently enhances automated UI testing tools to detect 1.2 to 2.1 times more unique crashes given the same testing resources.

关键词： UI Testing Mobile Testing Parallel Testing Android Parallelization Graph Partition online algorithm

来源：评论

学校读者我要写书评

暂无评论

online Single-Processor Scheduling with an Unexpected Breakdown

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2024年第1期41卷

作者： Guo, Sainan Chen, Yannan Mao, Yaping Zhang, Xiaoyan Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China South China Normal Univ Sch Math Sci Guangzhou 510631 Peoples R China Qinghai Normal Univ Dept Math & Stat Xining 810008 Qinghai Peoples R China Acad Plateau Sci & Sustainabil Xining 810008 Qinghai Peoples R China

In this paper, we consider two single-processor online scheduling problems with an unexpected breakdown. Speaking specifically, there is a group of nonresumable jobs being processed on the single processor. Note that the breakdown will emerge on the processor suddenly, which signifies that its beginning time and its length are unknown in advance. In this study, we are interested in scheduling the jobs so as to minimize the maximum weighted completion time. Most noticeably, when all jobs respect an agreeable condition, i.e., for each two jobs J(a) and J(b), w(a) >= w(b) means that p(a) >= p(b), we design an optimal online algorithm. In addition, for the general version, we propose an online algorithm with a competitive ratio of at most 2.

关键词： Scheduling online algorithm single processor unexpected breakdown

来源：评论

学校读者我要写书评

暂无评论

online Semi-matching Problem with Two Heterogeneous Sensors in a Metric Space 28th

Online Semi-matching Problem with Two Heterogeneous Sensors ...

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Man Li, Weidong Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

ISBN: (纸本)9783031221040;9783031221057

In this paper, we consider the online semi-matching problem with two heterogeneous sensors s(1) and s(2) in a metric space (X, d), where d(center dot, center dot) is a distance function. If a request r is assigned to sensor s(1), then the matching cost is d(r, s(1));otherwise, the matching cost is d(r,s2)/w, where w >= 1 is the weight of sensor s(2). The goal is to minimize the total cost of matching all requests. We design an optimal online algorithm with a competitive ratio of 1 + w + root w/w for 1 < w <= alpha, and an optimal online algorithm with a competitive ratio of w for w > alpha, where alpha approximate to 3.382.

关键词： online semi-matching Two heterogeneous sensors online algorithm Metric space

来源：评论

学校读者我要写书评

暂无评论

CUSTOMIZABLE END-TO-END OPTIMIZATION OF online NEURAL NETWORK-SUPPORTED DEREVERBERATION FOR HEARING DEVICES 47

CUSTOMIZABLE END-TO-END OPTIMIZATION OF ONLINE NEURAL NETWOR...

引用

47th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Lemercier, Jean-Marie Thiemann, Joachim Koning, Raphael Gerkmann, Timo Univ Hamburg Signal Proc SP Hamburg Germany Adv Bion Hannover Germany

ISBN: (纸本)9781665405409

This work focuses on online dereverberation for hearing devices using the weighted prediction error (WPE) algorithm. WPE filtering requires an estimate of the target speech power spectral density (PSD). Recently deep neural networks (DNNs) have been used for this task. However, these approaches optimize the PSD estimate which only indirectly affects the WPE output, thus potentially resulting in limited dereverberation. In this paper, we propose an end-to-end approach specialized for online processing, that directly optimizes the dereverberated output signal. In addition, we propose to adapt it to the needs of different types of hearing-device users by modifying the optimization target as well as the WPE algorithm characteristics used in training. We show that the proposed end-to-end approach outperforms the traditional and conventional DNN-supported WPEs on a noise-free version of the WHAMR! dataset.

关键词： online algorithm dereverberation neural network end-to-end learning hearing devices

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：