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

Optimization in data cube system design

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS 2004年第1期23卷 17-45页

作者： Hung, E Cheung, DW Kao, B Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China

The design of an OLAP system for supporting real-time queries is one of the major research issues. One approach is to use data cubes, which are materialized precomputed multidimensional views of data in a data warehouse. We can derive a set of data cubes to answer each frequently asked query directly. However, there are two practical problems: ( 1) the maintenance cost of the data cubes, and ( 2) the query cost to answer those queries. Maintaining a data cube requires disk storage and CPU computation, so the maintenance cost is related to the total size as well as the total number of data cubes materialized. In most cases, materializing all data cubes is impractical. The maintenance cost may be reduced by merging some data cubes. However, the resulting larger data cubes will increase the query cost of answering some queries. If the bounds on the maintenance cost and the query cost are too strict, we help the user decide which queries to be sacrificed and not taken into consideration. We have defined an optimization problem in data cube system design. Given a maintenance-cost bound, a query-cost bound and a set of frequently asked queries, it is necessary to determine a set of data cubes such that the system can answer a largest subset of the queries without violating the two bounds. This is an NP-hard problem. We propose approximate Greedy algorithms GR, 2GM and 2GMM, which are shown to be both effective and efficient by experiments done on a census data set and a forest-cover-type data set.

关键词： data warehouse data cube system design OLAP optimization approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing the misinformation concern over social networks

引用

INFORMATION PROCESSING & MANAGEMENT 2024年第1期61卷

作者： Ni, Peikun Zhu, Jianming Gao, Yuxin Wang, Guoqing Univ Chinese Acad Sci Sch Engn Sci Beijing Peoples R China Univ Chinese Acad Sci Sch Emergency Management Sci & Engn Beijing Peoples R China

People's opinions are often affected by their social network, and the associated misinformation on the online social networks can easily mislead people's judgment and decision-making process, leading people to take unconventional or even radical behaviors. People's decision-making behavior is influenced by their concern to the misinformation they receive. Building on this, we explore the competitive concern minimization problem of leveraging agents who post correct information to minimize users' concern to misinformation. First, considering users' concern to misinformation, this paper constructs a concern-critical competitive model and introduces the Coulomb's law to quantify the dynamic evolution of users' concern in information diffusion. Second, we prove hardness results for the competitive concern minimization problem and discuss the modularity of the objective function. Then, to optimize the nonsubmodular objective function, a two-stage approximate projected subgradient algorithm with data-dependent approximation ratio is developed using Lovasz extension and convex envelope. Finally, the experimental simulations on three real networks highlight the efficiency of the approaches proposed in this paper, which is at least 9.71% better than other baselines in reducing misinformation concern.

关键词： Social network Misinformation concern Non-submodular optimization Lovasz extension approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Heuristic Strategies for Combining Solutions of the Three-Index Axial Assignment Problem

引用

AUTOMATION AND REMOTE CONTROL 2021年第10期82卷 1635-1640页

作者： Afraimovich, L. G. Emelin, M. D. Lobachevsky State Univ Nizhny Novgorod Nizhnii Novgorod 603022 Russia

We consider the NP-hard integer three-index axial assignment problem. Strategies for combining feasible solutions of the problem are investigated. Combining can be used as a supplement to heuristic or approximate solution algorithms instead of the generally accepted step of choosing the record among the feasible solutions found. The results of computational experiments are presented that demonstrate the promising nature of the approach proposed.

关键词： axial assignment problem multiindex problem approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

On the independent set problem in random graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2015年第11期92卷 2233-2242页

作者： Song, Yinglei Jiangsu Univ Sci & Technol Sch Comp Sci & Engn Zhanjiang 212003 Jiangsu Peoples R China

In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.

关键词： independent set random graphs exact algorithm parameterized algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Mining of Frequent Item Sets on Large Uncertain Databases

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2012年第12期24卷 2170-2183页

作者： Wang, Liang Cheung, David Wai-Lok Cheng, Reynold Lee, Sau Dan Yang, Xuan S. Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The data handled in emerging applications like location-based services, sensor monitoring systems, and data integration, are often inexact in nature. In this paper, we study the important problem of extracting frequent item sets from a large uncertain database, interpreted under the Possible World Semantics (PWS). This issue is technically challenging, since an uncertain database contains an exponential number of possible worlds. By observing that the mining process can be modeled as a Poisson binomial distribution, we develop an approximate algorithm, which can efficiently and accurately discover frequent item sets in a large uncertain database. We also study the important issue of maintaining the mining result for a database that is evolving (e. g., by inserting a tuple). Specifically, we propose incremental mining algorithms, which enable Probabilistic Frequent Item set (PFI) results to be refreshed. This reduces the need of re-executing the whole mining algorithm on the new database, which is often more expensive and unnecessary. We examine how an existing algorithm that extracts exact item sets, as well as our approximate algorithm, can support incremental mining. All our approaches support both tuple and attribute uncertainty, which are two common uncertain database models. We also perform extensive evaluation on real and synthetic data sets to validate our approaches.

关键词： Frequent item sets uncertain data set approximate algorithm incremental mining

来源：评论

学校读者我要写书评

暂无评论

Adaptive and Extensible Energy Supply Mechanism for UAVs-Aided Wireless-Powered Internet of Things

引用

IEEE INTERNET OF THINGS JOURNAL 2020年第9期7卷 9201-9213页

作者： Wu, Pengfei Xiao, Fu Huang, Haiping Sha, Chao Yu, Shui Nanjing Univ Posts & Telecommun Sch Comp Nanjing 210013 Peoples R China Nanjing Univ Posts & Telecommun Jiangsu High Technol Res Key Lab Wireless Sensor Nanjing 210013 Peoples R China Univ Technol Sydney Sch Software Sydney NSW 2007 Australia

This article studies multiple unmanned aerial vehicles (multi-UAVs)-enabled wireless-powered Internet of Things (IoT), where a group of UAVs is dispatched as mobile power sources to charge a set of ground IoT devices. Different from the conventional radio-frequency (RF) wireless power transfer (WPT) systems, magnetic resonance-coupled (MRC) WPT systems can guarantee high power transfer efficiency without the complete alignment, which is remarkable. In this article, we extend the charging range by the wired connection between the energy receiving systems and IoT devices. Due to the restriction of carriable energy on the UAVs, designing the shortest possible trajectory for each UAV is necessary. We formulate it as a multidepots multi-UAVs trajectory optimization problem, jointly with constraints of the UAV's energy capacity and the area of the target region, to maximize the resource utilization of UAVs. To tackle this nonconvex problem, we decompose it into two subproblems, i.e., hovering locations selection and multi-UAVs trajectory optimization. For the first subproblem, we propose two approximation algorithms to obtain the near-optimal solution in the sparse networks. Then, we adopt a heuristic algorithm, a memetic algorithm-based variable neighborhood search (MAVNS), to achieve the quasioptimal trajectory rapidly. Finally, extensive numerical results are provided to evaluate the performance of the proposed algorithms. New insights are investigated on the estimation of feasibility that whether the given UAVs with energy capacity constraint can fully charge ground IoT devices within open areas.

关键词： Trajectory Internet of Things Wireless communication Wireless power transfer Approximation algorithms Unmanned aerial vehicles Task analysis approximate algorithm multiple depots unmanned aerial vehicle (UAV) wireless power sensor networks wireless power transfer (WPT)

来源：评论

学校读者我要写书评

暂无评论

A Hopeful CNF-SAT─algorithm Its High Efficiency, Industrial Application and Limitation

引用

Journal of Computer Science & Technology 1998年第1期13卷 9-12页

作者：黄文奇李未 DepartmentofComputerScience HuazhongUniversityofScience＆TechnologyWuhan430074P.R.China DepartmentofC

From the SAT physical model, a physical hypothesis named PHHY is proposed. By PHHY, it is proved that there is a universally efficient algorithm for solving SAT problem. Then, by square packing problem, the authors show that there are interesting industrial NP-complete problems which can be solved through SAT algorithms, but each way of solving like this will be much worse than that of a certain direct solving.

关键词： NP-complete problem CNF-SAT satisfiability potential function approximate algorithm probability complexity.

来源：评论

学校读者我要写书评

暂无评论

Decoupling joint probabilistic data association algorithm for multiple target tracking

引用

IEE PROCEEDINGS-RADAR SONAR AND NAVIGATION 1999年第5期146卷 251-254页

作者： Ding, Z Leung, H Hong, L Raytheon Syst Canada Ltd Adv Syst Dev Waterloo ON N2J 4K6 Canada Univ Calgary Dept Elect & Comp Engn Calgary AB T2N 1N4 Canada Wright State Univ Dept Elect Engn Dayton OH 45435 USA

The authors present a decoupling joint probabilistic data association (DJPDA) algorithm by decoupling the JPDA algorithm into separate PDA algorithms. To demonstrate the decoupling idea, they derive a set of complete decoupling PDA equations for two and three targets. Since these equations are impractical for real-time systems and are unavailable for an arbitrary number of targets, an approximate algorithm is given. The proposed decoupling algorithm is evaluated using computer simulation. It is shown that the performance of the DJPDA algorithm is close to that of the JPDA. algorithm but it needs much less computation.

关键词： decoupling algorithm approximate algorithm decoupling joint probabilistic data association algorithm PDA algorithms target tracking JPDA algorithm covariance matrices Signal processing and detection multiple target tracking Other topics in statistics probability computer simulation

来源：评论

学校读者我要写书评

暂无评论

A hybrid algorithm combining glowworm swarm optimization andcomplete 2-opt algorithm for spherical travelling salesman problems

引用

APPLIED SOFT COMPUTING 2017年 58卷 104-114页

作者： Chen, Xin Zhou, Yongquan Tang, Zhonghua Luo, Qifang Guangxi High Sch Key Lab Complex Syst & Computat Nanning 530006 Peoples R China Guangxi Univ Nationalities Coll Informat Sci & Engn Nanning 530006 Peoples R China Dalian Univ Technol Shcool Software Dalian 116024 Peoples R China

The Travelling Salesman Problem (TSP) is one of the most well-known combinatorial optimization problems and has attracted a lot of interests from researchers. Many studies have proposed various methods for solving the two-dimensional TSP. In this study, we extend the two-dimensional TSP to the three-dimensional TSP, namely the spherical TSP in which all points (cities) and paths (solutions) are on the surface of a sphere. A hybrid algorithm based on the glowworm swarm optimization (GSO) and the complete 2-opt algorithm is proposed, in which the carriers of the luciferin are transformed from glowworms to edges between cities, and the probabilistic formula and the luciferin updating formula are modified. In addition, the complete 2-opt algorithm is performed to optimize the selected optimal routes every few iterations. Numerical experimental results show that the proposed algorithm has a better performance than the basic GSO in solving the spherical TSP. Meanwhile, the complete 2-opt algorithm can speed up the convergence rate. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Travelling salesman problem Glowworm swarm optimization Complete 2-opt algorithm Spherical TSP approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Bunkering policies for a fuel bunker management problem for liner shipping networks

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第3期289卷 927-939页

作者： De, Arijit Choudhary, Alok Turkay, Metin Tiwari, Manoj K. Newcastle Univ Business Sch Newcastle Upon Tyne NE1 4SE Tyne & Wear England Loughborough Univ Sch Business & Econ Loughborough LE11 3TU Leics England Koc Univ Dept Ind Engn Rumelifeneri Yolu TR-34450 Istanbul Turkey Indian Inst Technol Kharagpur Dept Ind & Syst Engn Kharagpur 721302 W Bengal India

This paper investigates the problem of bunker fuel management for liner shipping networks under different fuel pricing scenarios and taking into consideration different fuel bunkering policies. The fuel consumption of a vessel on a sailing leg may fluctuate as the real vessel speed deviates from the planned vessel speed. Furthermore, fluctuation of fuel prices at various ports increases the complexity of bunkering decisions related to the selection of the bunkering ports and the estimation of bunkered fuel cost. We have developed a mixed integer non-linear programming model to minimize the total expected cost consisting of inventory cost related to container transportation, operating cost associated with ship hiring, as well as bunkering cost and fuel consumption cost at the port. The novelty of our research lies in its consideration of stochastic fuel consumption for different sailing legs, stochastic fuel prices at each port and different fuel bunkering policies to determine optimal bunker fuel management strategies for the selection of bunkering ports and for the estimation of the amount of bunkered fuel required. We have proposed a novel approximate algorithm based on mathematical formulation and the fuel bunkering policies to calculate the total expected cost;the fuel inventory while arriving at and departing from the port;the number of vessels hired for weekly service;the arrival and departure time of the ship;and the amount of fuel bunkered at a port. We have performed extensive computational experiments on the practical routes to demonstrate the applicability, efficacy and robustness of the proposed novel methodology. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Heuristics Liner shipping Bunker fuel management Bunkering policies approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：