Cache-Based Multi-Query Optimization for Data-Intensive Scalable Computing Frameworks

2021 | Information Systems Frontiers | Citations: 0

Authors: Michiardi, Pietro; Carra, Damiano; Migliorini, Sara

Abstract: In modern large-scale distributed systems, analytics jobs submitted by various u ... Expand

Abstract: In modern large-scale distributed systems, analytics jobs submitted by various users often share similar work, for example scanning and processing the same subset of data. Instead of optimizing jobs independently, which may result in redundant and wasteful processing, multi-query optimization techniques can be employed to save a considerable amount of cluster resources. In this work, we introduce a novel method combining in-memory cache primitives and multi-query optimization, to improve the efficiency of data-intensive, scalable computing frameworks. By careful selection and exploitation of common (sub)expressions, while satisfying memory constraints, our method transforms a batch of queries into a new, more efficient one which avoids unnecessary recomputations. To find feasible and efficient execution plans, our method uses a cost-based optimization formulation akin to the multiple-choice knapsack problem. Extensive experiments on a prototype implementation of our system show significant benefits of worksharing for both TPC-DS workloads and detailed micro-benchmarks. Collapse

Topics: Apache Spark distributed computing application programming interface database system operating system

Methods: experiment computational algorithm design artifact optimization model knapsack problem

Integrated Synthesis and Execution of Optimal Plans for Multi-Robot Systems in Logistics

2019 | Information Systems Frontiers | Citations: 0

Authors: Leofante, Francesco; Ábrahám, Erika; Niemueller, Tim; Lakemeyer, Gerhard; Tacchella, Armando

Abstract: Model-based synthesis allows to generate plans to achieve high-level tasks while ... Expand

Abstract: Model-based synthesis allows to generate plans to achieve high-level tasks while satisfying certain properties of interest. However, when such plans are executed on concrete systems, several modeling assumptions may be challenged, jeopardizing their real applicability. This paper presents an integrated system for generating, executing and monitoring optimal-by-construction plans for multi-robot systems. This system unites the power of Optimization Modulo Theories with the flexibility of an on-line executive, providing optimal solutions for high-level task planning, and runtime feedback on their feasibility. After presenting how our system orchestrates static and runtime components, we demonstrate its capabilities using the RoboCup Logistics League as testbed. We do not only present our final solution but also its chronological development, and draw some general observations for the development of OMT-based approaches. Collapse

Topics: robotic logistics management decision making problem solving Google+

Methods: synthesis simulation experiment combinatorial optimization optimization model

Decision support approaches for cyber security investment

2016 | Decision Support Systems | Citations: 21

Authors: Fielder, Andrew; Panaousis, Emmanouil; Malacaria, Pasquale; Hankin, Chris; Smeraldi, Fabrizio

Abstract: When investing in cyber security resources, information security managers have t ... Expand

Abstract: When investing in cyber security resources, information security managers have to follow effective decision-making strategies. We refer to this as the cyber security investment challenge.In this paper, we consider three possible decision support methodologies for security managers to tackle this challenge. We consider methods based on game theory, combinatorial optimisation, and a hybrid of the two. Our modelling starts by building a framework where we can investigate the effectiveness of a cyber security control regarding the protection of different assets seen as targets in presence of commodity threats. As game theory captures the interaction between the endogenous organisation's and attackers' decisions, we consider a 2-person control game between the security manager who has to choose among different implementation levels of a cyber security control, and a commodity attacker who chooses among different targets to attack. The pure game theoretical methodology consists of a large game including all controls and all threats. In the hybrid methodology the game solutions of individual control-games along with their direct costs (e.g. financial) are combined with a Knapsack algorithm to derive an optimal investment strategy. The combinatorial optimisation technique consists of a multi-objective multiple choice Knapsack based strategy. To compare these approaches we built a decision support tool and a case study regarding current government guidelines. The endeavour of this work is to highlight the weaknesses and strengths of different investment methodologies for cyber security, the benefit of their interaction, and the impact that indirect costs have on cyber security investment. Going a step further in validating our work, we have shown that our decision support tool provides the same advice with the one advocated by the UK government with regard to the requirements for basic technical protection from cyber attacks in SMEs. Collapse

Topics: IT security decision support system IT security threat decision support data security

Methods: case study knapsack problem computational algorithm optimization model combinatorial optimization

Theories: game theory

A DSS for bicriteria location problems

2014 | Decision Support Systems | Citations: 2

Authors: Fernandes, Sérgio; Captivo, M. Eugénia; Clímaco, João

Abstract: In this paper, we present a new interactive decision support system (DSS) – name ... Expand

Abstract: In this paper, we present a new interactive decision support system (DSS) – named SABILOC – in action. The DSS is aimed at supporting decision-making concerning bicriteria location models and it was specially designed to deal with problems in which the facilities to be located have environmental impacts. We point out three advantages of SABILOC when compared with other DSS for location problems available in the literature. Firstly, an interactive procedure is used allowing the decision-maker to obtain non-dominated solutions for bicriteria location models. Secondly, a multiattribute analysis module allows the decision-maker to proceed with a more detailed analysis of a subset of solutions selected from the first interactive phase. Finally, the embedment of a Geographic Information System into SABILOC makes the system much more useful in real world location problems. In order to better describe and validate the potentialities and functionalities of SABILOC, we present a case study of a real world problem applied to waste transfer station siting. Collapse

Topics: decision support system decision making application programming interface geographic information system spreadsheet

Methods: case study combinatorial optimization integer programming optimization model literature study

A Profit-Maximizing Method for the Partitioning of Embedded Software Features in Motor Vehicles

2009 | Americas Conference on Information Systems | Citations: 0

Authors: Baecker, Oliver; Weppner, Harald; Strube, Jochen

Abstract: As the system design of in-car embedded systems becomes more and more modular an ... Expand

Abstract: As the system design of in-car embedded systems becomes more and more modular and motor vehicles get increasingly connected to enterprise systems based on Car-2-X technology, the integration of additional embedded software features becomes technically feasible throughout the product lifecycle. For car manufacturers, this opens up the opportunity to sell additional embedded software features to their customers at a later time, thus generating subsequent revenue in addition to the initial sale. However, due to the competitive environment and customer preferences, it is impossible to apply this concept to the complete feature set. In order to support the decision, which features should be included in a shipped product and which features should be retained to generate subsequent revenue, we propose a profit-maximizing method that identifies two complementary feature bundles. To illustrate our approach, we present a numerical example, which illustrates the partitioning of embedded software features in motor vehicles. Collapse

Topics: embedded system enterprise information system mobile system

Methods: knapsack problem optimization model usage data combinatorial optimization computational algorithm

A container packing support system for determining and visualizing container packing patterns

2004 | Decision Support Systems | Citations: 0

Authors: Chien, Chen-Fu; Deng, Jing-Feng

Abstract: Relatively few approaches have been developed to solve the container-packing pro ... Expand

Abstract: Relatively few approaches have been developed to solve the container-packing problem despite its important industrial and commercial applications. This study constructs a container packing support system capable of incorporating the computational algorithm, graphic user interface (GUI) input/output interface, and a simulation program for illustrating the container packing process in steps. A numerical example is used to illustrate the proposed container packing support system. We use real data to compare the solutions derived by the proposed algorithm with those of a greedy algorithm and the original solutions of a local transportation company. The results demonstrate the effectiveness and practical viability of this approach. Collapse

Topics: programming language competitive advantage user interface usability decision support

Methods: computational algorithm simulation longitudinal research mathematical model combinatorial optimization

Multiple Criteria Combinatorial Auction: A B2B Allocation Mechanism for Substitute Goods

2000 | Americas Conference on Information Systems | Citations: 0

Authors: Jones, Joni L; Koehler, Gary J

Abstract: We present business-to-business electronic auction mechanism as an alternative t ... Expand

Abstract: We present business-to-business electronic auction mechanism as an alternative to sales usually accomplished through negotiation. The mechanism allows bids that are incompletely specified yet provide an evaluative framework to facilitate the allocation of complementary goods when substitutes are available. The auction form allows the consumer to create a unique combination of goods upon which to place a multiple criteria bid. Bidders are given the flexibility to change and or modify their bids and bundles until a stopping criterion has been reached. The allocation to bidders requires solving a complex combinatorial problem in realtime. Since the proposed integer program model may become computationally intractable as the number of bidders increase, we present simplifying heuristics to make the problem manageable on a large scale. Collapse

Topics: online auction business-to-business advertising management

Methods: constraint programming linear optimization experiment combinatorial optimization integer programming

Theories: theory of bounded rationality

A Neural-Net Gaussian Machine for Optimal Local Access Network Design

1998 | Americas Conference on Information Systems | Citations: 0

Authors: Han, Bernard; Raja, V

Abstract: Local access network design often involves the solution of a capacitated concent ... Expand

Abstract: Local access network design often involves the solution of a capacitated concentrator location problem (CCLP). In contrast to the conventional single-capacitated CCLP, this paper presents a generalized CCLP (GCCLP) in which n given end-user nodes are to be connected to concentrators located at m available sites, and each concentrator is subject to two capacity constraints - its effective data processing rate (Kbits/sec) and the available number of circuit ports. The objective of GCCLP is to ensure that each end-user node is connected to exactly one concentrator such that neither of its capacity constraints is violated while the total communication costs are minimized. Since GCCLP is combinatorially explosive, large problems may not be practically solved by an exact method. In this paper, rather, an artificial intelligence solution engine, a Gaussian Machine, is developed for solving GCCLP. Our preliminary computational results indicate that this AI-based solution algorithm is a feasible alternative for solving GCCLP. Collapse

Topics: artificial intelligence Fortran

Methods: computational algorithm mathematical model combinatorial optimization

Decision support for siting problems

1998 | Decision Support Systems | Citations: 5

Authors: Maniezzo, V.; Mendes, I.; Paruccini, M.

Abstract: Despite the development of mathematics of location theory and its obvious econom ... Expand

Abstract: Despite the development of mathematics of location theory and its obvious economic impact, few applications have been developed and are actually in use to support decision makers in siting decisions. The obstacles that hinder a more widespread exploitation of mathematical results are twofold: the intrinsic difficulties of the relevant problems and the tradeoff to be balanced between the different objectives. The article presents the results obtained in the implementation of a Decision Support system applied to the problem of locating installations for industrial waste management. This DSS is based on multicriteria decision analysis for the best siting of plants, minimizing costs and environmental impacts. The proposed approach identifies a hierarchy of objectives, where at the top level we solve a 0/1 fixed cost transportation problem (FCTP). This is an NP-hard combinatorial optimization problem that can only be solved heuristically for real world problem sizes. A number of good solutions of the single objective problem are combined to produce efficient alternatives, to be further evaluated by means of multicriteria methods. Computational results both of the FCTP and of the whole systems are provided. Collapse

Topics: data management usability user interface decision support system decision support

Methods: multiple criteria decision making trade-off analysis method combinatorial optimization knapsack problem case study

Logic decisions under constraints

1994 | Decision Support Systems | Citations: 0

Authors: Monfroglio, Angelo

Abstract: A fundamental issue in the decision process and automated reasoning is how to ef ... Expand

Abstract: A fundamental issue in the decision process and automated reasoning is how to efficiently obtain logic decisions under constraints. Logic Constraints Catisfaction problems are in general NP-hard and a general deterministic polynomial time algorithm is not known. The present paper illustrates two different approaches: the first based on Constrained Heuristic Search and the second based on Integer and Linear Programming. Both algorithms compare favourable with the best known techniques to solve decisions problems under logic constraints. Complexity of the algorithms and results of significant tests are reported. Collapse

Topics: Tableau software resource allocation logic programming language

Methods: computational algorithm linear optimization exploratory data analysis design artifact constraint programming