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

30th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Gutschlag, Theodor Storandt, Sabine Univ Konstanz Constance Germany

ISBN: (纸本)9781450395298

Measuring the similarity of spatio-temporal trajectories in a sensible fashion is an important building block for applications such as trajectory clustering or movement pattern analysis. However, typically employed similarity measures only take the spatial components of the trajectory into account, or are complicated combinations of different measures. In this paper we introduce the so called Generalized Frechet distance, which extends the well-known Frechet distance. For two polygonal curves of length n and m in d-dimensional space, the Generalized Frechet distance enables an individual weighting of each dimension on the similarity value by using a convex function. This allows to integrate arbitrary data dimensions as e.g. temporal information in an elegant,flexible and application-aware manner. We study the Generalized Frechet Distance for both the discrete and the continuous version of the problem, prove useful properties, and present efficient algorithms to compute the decision and optimization problem. In particular, we prove that for d is an element of O(1) the asymptotic running times of the optimization problem for the continuous version are O(nm log(nm)) under realistic assumptions, and O(nm) for the discrete version for arbitrary weight functions. Therefore the theoretical running times match those of the classical Frechet distance. In our experimental evaluation, we demonstrate the usefulness of the Generalized Frechet distance and study the practical behaviour of our algorithms. On sets of real-world trajectories, we confirm that the weighting of the spatial and temporal dimensions heavily impacts the relative similarity, and hence the ability to tailor the measure to the application is a useful tool.

关键词： Trajectory similarity Frechet distance algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Search Trajectories Networks of Multiobjective Evolutionary algorithms 25th

Search Trajectories Networks of Multiobjective Evolutionary ...

引用

25th International Conference on the Applications of Evolutionary Computation (EvoApplications) Held as Part of EvoStar Conference

作者： Lavinas, Yuri Aranha, Claus Ochoa, Gabriela Univ Tsukuba Tsukuba Ibaraki Japan Univ Stirling Stirling Scotland

ISBN: (纸本)9783031024627;9783031024610

Understanding the search dynamics of multiobjective evolutionary algorithms (MOEAs) is still an open problem. This paper extends a recent network-based tool, search trajectory networks (STNs), to model the behavior of MOEAs. Our approach uses the idea of decomposition, where a multiobjective problem is transformed into several single-objective problems. We show that STNs can be used to model and distinguish the search behavior of two popular multiobjective algorithms, MOEA/D and NSGA-II, using 10 continuous benchmark problems with 2 and 3 objectives. Our findings suggest that we can improve our understanding of MOEAs using STNs for algorithm analysis.

关键词： algorithm analysis Search trajectories Continuous optimization Visualization Multi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

High-Speed Packet Classification: A Case for Approximate Sorting

High-Speed Packet Classification: A Case for Approximate Sor...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Narasimhan, Aditya Radhakrishnan, Sridhar Atiquzzaman, Mohammad Subramanian, C. R. Univ Oklahoma Sch Comp Sci Norman OK 73019 USA HBNI Inst Math Sci Chennai 600113 Tamil Nadu India

ISBN: (纸本)9781665435406

Buffer capacities at routers are ever-increasing to accommodate the extreme-scale increase in the volume of incoming traffic. Sophisticated packet classification is being adopted to address challenges in meeting application demands. With the number of rules for classification and packets arriving at routers per second reaching 100's of thousands to millions, special hardware is also being built for packet classification to increase throughput at routers. Sorting packets (based on various conditions) in the buffers offers a significant advantage for the packet classification process. The sorting step is a time-consuming step given the large volume of packets in the incoming buffers. We propose a technique to approximately sort the packets by capping the maximum number of comparisons that can be made. We show that the performance of well-known decision tree-based packet classification methods such as HyperCuts, EffiCuts, and SmartSplits can be improved by more than 32% with approximate sorting for when the number of packets is less than 10K at any given time. If the number of packets in the arriving buffer is greater than 10K, we can divide them into smaller portions to achieve similar gains.

关键词： Buffer Management Packet Classification Approximate Sorting algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Robust algorithm for Signal Digital Detection on the Background of Non-Gaussian Passive Interferences

Robust Algorithm for Signal Digital Detection on the Backgro...

引用

Workshop on Microwave Theory and Techniques in Wireless Communications (MTTW)

作者： Yanovsky, Felix Prokopenko, Igor Rhee, Huinam Pitertsev, Alexander Dmytruk, Anastasiia Natl Aviat Univ Dept Elect Robot Monitoring & IoT Technol ERMIT Kiev Ukraine Delft Univ Technol Dept Geosci & Remote Sensing Atmospher Remote Sensing Delft Netherlands Natl Aviat Univ Dept Aeronav Radio Elect & Telecomun Kiev Ukraine Sunchon Natl Univ Dept Aerosp Engn Aerosp Res Ctr Sunchon South Korea Natl Aviat Univ Dept Elect Robot Monitoring & IoT Technol Kiev Ukraine

ISBN: (数字)9781665464390

ISBN: (纸本)9781665464390

This paper proposes generalized mathematical model of different passive interferences and develops an effective algorithm of digital signal processing for detection on the background of them. Models of interferences as random process of K-distribution is used with parametrization for the unwanted reflections from atmosphere, land, and sea. Robust algorithm for signal detection on the background of such interferences, in particular in case of non-gaussian distribution, is developed. Its effectiveness is researched and confirmed.

关键词： digital signal processing radar detection clutter algorithm design algorithm analysis ranking

来源：评论

学校读者我要写书评

暂无评论

Further results on an abstract model for branching and its application to mixed integer programming

引用

MATHEMATICAL PROGRAMMING 2021年第1-2期190卷 811-841页

作者： Anderson, Daniel Le Bodic, Pierre Morgan, Kerri Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA Monash Univ Fac Informat Technol Caulfield Australia Deakin Univ Fac Sci Engn & Built Environm Sch Informat Technol Geelong Vic Australia

A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection can affect the size of the resulting search trees by orders of magnitude. A recent article by Le Bodic and Nemhauser (Math Program 166(1-2):369-405, 2017) investigated variable selection rules by developing a theoretical model of B&B trees from which they developed some new, effective scoring functions for MIP solvers. In their work, Le Bodic and Nemhauser left several open theoretical problems, solutions to which could guide the future design of variable selection rules. In this article, we first solve many of these open theoretical problems. We then implement an improved version of the model-based branching rules in SCIP 6.0, a state-of-the-art academic MIP solver, in which we observe an 11% geometric average time and node reduction on instances of the MIPLIB 2017 Benchmark Set that require large B&B trees.

关键词： Branch and bound Mixed-integer programming algorithm analysis Branching rules

来源：评论

学校读者我要写书评

暂无评论

Extremal behavior of the Greedy algorithm for a triangle scheduling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 169卷

作者： Balogh, Janos Bekesi, Jozsef Buki, Nora Dosa, Gyorgy Tuza, Zsolt Univ Szeged Fac Sci & Informat Dept Computat Optimizat Arpad Sqr 2 H-6720 Szeged Hungary Univ Szeged Fac Sci & Informat Dept Comp Algorithms & Artificial Intelligence Arpad sqr 2 H-6720 Szeged Hungary Univ Pannonia Fac Informat Technol Dept Math Egyet str 10 H-8200 Veszprem Hungary HUN REN Alfred Reny Inst Math Realtanoda str 13-15 H-1053 Budapest Hungary Univ Pannonia Fac Informat Technol Dept Comp Sci & Syst Technol Egyet str 10 H-8200 Veszprem Hungary

We study the mixed-criticality scheduling problem, where the goal is to schedule jobs with different criticality levels on a single machine. As shown by D & uuml;rr et al. (2018), the problem can be treated as a specific 1dimensional triangle scheduling problem. In that paper a new Greedy algorithm was defined, and the authors proved that its approximation ratio lies between 1.05 and 3/2. In this paper we present a quadratic integer programming model, which can be used to computationally analyze the algorithm for inputs with small sizes. The model simulates the behavior of the algorithm and it compares the makespan with the optimal one. Using this model, we found sequences extendable to longer series, giving a lower bound of 1.27 for the Greedy algorithm. Also, the optimum on problem instances consisting of intervals of natural numbers is analyzed and a closed formula is determined. In this way, we detected two input classes where, in one of them, Greedy is far from optimal (we think that this could be the worst case), and in the other one it is optimal.

关键词： Mixed-criticality scheduling algorithm analysis Triangle scheduling

来源：评论

学校读者我要写书评

暂无评论

Monte Carlo analysis of Local Cross-Correlation ST-TBD algorithm 19th

Monte Carlo Analysis of Local Cross-Correlation ST-TBD Algor...

引用

19th Annual International Conference on Computational Science (ICCS)

作者： Mazurek, Przemyslaw Krupinski, Robert West Pomeranian Univ Technol Szczecin Dept Signal Proc & Multimedia Engn Szczecin Poland

ISBN: (纸本)9783030227340;9783030227333

The Track-Before-Detect (TBD) algorithms allow the estimation of the state of an object, even if the signal is hidden in the background noise. The application of local cross-correlation for the modified Information Update formula improves this estimation for extended objects (tens of cells in the measurement space) compared to the direct application of the Spatio-Temporal TBD (ST-TBD) algorithm. The Monte Carlo test was applied to evaluate algorithms by using a variable standard deviation of the additive Gaussian noise. The proposed solution does not require prior knowledge of the size or measured values of the object. Mean Absolute Error for the proposed algorithm is much lower, close to zero to about 0.8 standard deviation, which is not achieved for the ST-TBD.

关键词： Track-Before-Detect Tracking algorithm analysis Monte Carlo Cross-correlation

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for learning sparse parities in the presence of noise

引用

THEORETICAL COMPUTER SCIENCE 2021年 873卷 76-86页

作者： Yan, Di Yu, Yu Liu, Hanlin Zhao, Shuoyao Zhang, Jiang Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

We revisit the Learning Sparse Parities with Noise (LSPN) problem on k out of n variables for k << n, and present the following findings. 1. For true parity size k = n(u) for any 0 < u < 1, and noise rate eta < 1/2, the first algorithm solves the (n,k,eta)-LSPN problem with constant probability and time/sample complexity n((1-u+o(1))k)/(1/2-eta)(2). 2. For any 1/2 < c(1) < 1, k = o(eta n/logn), and eta <= n (-c1)/4, our second algorithm solves the (n,k,eta)-LSPN problem with constant probability and time/sample complexity n(2(1-c1+o(1))k). 3. We show a "win-win" result about reducing the number of samples. If there is an algorithm that solves (n, k, eta)-LSPN problem with probability Omega(1), time/sample complexity n(O(k)) for k = o(n(1-c)), any noise rate eta = n(1-2C)/3 and 1/2 <= c < 1. Then, either there exists an algorithm that solves the (n, k, mu)-LSPN problem under lower noise rate mu = n(-c)/3 using only 2n samples, or there exists an algorithm that solves the (n, k ', mu)-LSPN problem for a much larger k ' = n(1-c) with probability n(-O(k))/poly(n), and time complexity poly(n) center dot n(O(k)), using only n samples. Our algorithms are simple in concept by combining a few basic techniques such as majority voting, reduction from the LSPN problem to its decisional variant, Goldreich-Levin list decoding, and computational sample amplification. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Learning theory algorithm analysis Learning parity with noise Learning sparse parity with noise Sample amplification

来源：评论

学校读者我要写书评

暂无评论

Empirical and statistical comparison of intermediate steps of AES-128 and RSA in terms of time consumption

引用

SOFT COMPUTING 2021年第21期25卷 13127-13145页

作者： Pranav, Prashant Dutta, Sandip Chakraborty, Soubhik Birla Inst Technol Dept Comp Sci & Engn Ranchi 835215 Bihar India Birla Inst Technol Dept Math Ranchi 835215 Bihar India

Cryptographic algorithms are composed of many complex mathematical functions. When analyzing the complexity of these algorithms, one fixes priory the overall complexity of the algorithm as the complexity of the most dominating operations for a group of operations. Generally, it is the count of this operation which determines the complexity of the algorithm in case of compounding operations. We have instead used the weight factor to determine the complexity of an algorithm with many operating functions working simultaneously and have taken time of the operation as a measure of the weight factor. We statistically analyze the two most used operations in RSA, namely "power" and "mod," through a method of revised difference to compare whether these are statistically similar or dissimilar. We have also calculated the empirical computational complexity of these two operations through the fundamental theorem of finite differences to verify whether these operations are statistically dissimilar and if so then which of the two is dominant. We have also analyzed empirically the complexity of each of the four sub-steps involved in the encryption and decryption of AES-128, to determine which operation dominates the most and consumes most of the time in an overall run time of AES-128.

关键词： Cryptography algorithm analysis Empirical complexity Revised difference RSA AES-128

来源：评论

学校读者我要写书评

暂无评论

Distributed Composite Optimization Over Relay-Assisted Networks

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2021年第10期51卷 6587-6598页

作者： Shi, Chong-Xiao Yang, Guang-Hong Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Peoples R China Northeastern Univ Key Lab Integrated Automat Proc Ind Minist Educ Shenyang 110819 Peoples R China

This article studies the distributed composite optimization problem over relay-assisted networks (DCOP-RNs). By combining the local primal-dual updates with a data fusion strategy, an effective distributed algorithm is developed to solve the DCOP-RN. Compared with the existing linearized alternating direction method of multipliers (ADMMs), this article provides a novel interpretation of the proposed algorithm. More specifically, it is shown that the proposed algorithm can be interpreted as a simplified proximal augmented Lagrangian method. Within this framework, a simplified convergence analysis of the algorithm is conducted, based on which the convergence to an optimal solution to the DCOP-RN is proved. Further, taking into account the limited bandwidth in real networks, this article proposes a quantized distributed algorithm to solve the DCOP-RN. Especially, a relationship between the quantization resolution and the convergence accuracy of the algorithm is established. Finally, simulation examples verify the theoretical results.

关键词： Optimization Convergence Signal processing algorithms Bandwidth Protocols Distributed algorithms Convex functions algorithm analysis distributed optimization primal-dual methods relay-assisted networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：