mdh.sePublikationer
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
BETA
Publikationer (10 of 12) Visa alla publikationer
Källberg, L. (2019). Minimum Enclosing Balls and Ellipsoids in General Dimensions. (Doctoral dissertation). Västerås: Mälardalen University
Öppna denna publikation i ny flik eller fönster >>Minimum Enclosing Balls and Ellipsoids in General Dimensions
2019 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

In this doctoral thesis, we study the problem of computing the ball of smallest radius enclosing a given set of points in any number of dimensions. Variations of this problem arise in several branches of computer science, such as computer graphics, artificial intelligence, and operations research. Applications range from collision detection for three-dimensional models in video games and computer-aided design, to high-dimensional clustering and classification in machine learning and data mining. We also consider the related and more challenging problem of finding the enclosing ellipsoid of minimum volume. Such ellipsoids can provide more descriptive data representations in the aforementioned applications, and they find further utility in, for example, optimal design of experiments and trimming of outliers in statistics.

The contributions of this thesis consist of practical methods for the efficient solution of these two problems, with a primary focus on problem instances involving a large number of points. We introduce new algorithms to compute arbitrarily fine approximations of the minimum enclosing ball or ellipsoid in general dimensions. In our experimental evaluations, these algorithms exhibit running times that are highly competitive with, and often markedly superior to, those of earlier algorithms from the literature. Moreover, we present a new out-of-core algorithm to compute the exact minimum enclosing ball for massive, low-dimensional point sets residing in secondary storage. In addition to these solution methods, we develop acceleration techniques that can further improve their performance, either by using pruning heuristics to reduce the amount of work performed in each iteration, or by utilizing parallel hardware features of modern processors and graphics processing units. These techniques are also applicable to several existing algorithms.

Ort, förlag, år, upplaga, sidor
Västerås: Mälardalen University, 2019
Serie
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 300
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datavetenskap
Identifikatorer
urn:nbn:se:mdh:diva-45863 (URN)978-91-7485-448-0 (ISBN)
Disputation
2020-01-10, Beta, Mälardalens högskola, Västerås, 13:15
Opponent
Tillgänglig från: 2019-11-07 Skapad: 2019-10-29 Senast uppdaterad: 2019-11-21Bibliografiskt granskad
Källberg, L., Shellshear, E. & Larsson, T. B. (2016). An external memory algorithm for the minimum enclosing ball problem. In: VISIGRAPP 2016 - Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications: . Paper presented at 11th International Conference on Computer Graphics Theory and Application, GRAPP 2016; Part of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, VISIGRAPP 2016, 27 February 2016 through 29 February 2016 (pp. 83-90).
Öppna denna publikation i ny flik eller fönster >>An external memory algorithm for the minimum enclosing ball problem
2016 (Engelska)Ingår i: VISIGRAPP 2016 - Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, 2016, s. 83-90Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

In this article we present an external memory algorithm for computing the exact minimum enclosing ball of a massive set of points in any dimension. We test the performance of the algorithm on real-life three-dimensional data sets and demonstrate for the first time the practical efficiency of exact out-of-core algorithms. By use of simple heuristics, we achieve near-optimal I/O in all our test cases.

Nyckelord
Big Data, External Memory Algorithm, Minimum Enclosing Ball, Smallest Bounding Sphere, Computation theory, Computer graphics, Computer vision, External memory algorithms, Near-optimal, Out-of-core algorithms, Simple heuristics, Test case, Three dimensional data sets, Algorithms
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
urn:nbn:se:mdh:diva-31792 (URN)2-s2.0-84968830542 (Scopus ID)9789897581755 (ISBN)
Konferens
11th International Conference on Computer Graphics Theory and Application, GRAPP 2016; Part of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, VISIGRAPP 2016, 27 February 2016 through 29 February 2016
Tillgänglig från: 2016-06-09 Skapad: 2016-06-09 Senast uppdaterad: 2018-02-22Bibliografiskt granskad
Larsson, T. B., Capannini, G. & Källberg, L. (2016). Parallel computation of optimal enclosing balls by iterative orthant scan. Computers & graphics, 56, 1-10
Öppna denna publikation i ny flik eller fönster >>Parallel computation of optimal enclosing balls by iterative orthant scan
2016 (Engelska)Ingår i: Computers & graphics, ISSN 0097-8493, E-ISSN 1873-7684, Vol. 56, s. 1-10Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We propose an algorithm for computing the exact minimum enclosing ball of large point sets in general dimensions. It aims to reduce the number of passes by retrieving a well-balanced set of outliers in each linear search through the input by decomposing the space into orthants. The experimental evidence indicates that the convergence rate in terms of the required number of linear passes is superior compared to previous exact methods, and substantially faster execution times are observed in dimensions d≤16. In the important three-dimensional case, the execution times indicate real-time performance. Furthermore, we show how the algorithm can be adapted for parallel execution on both CPU and GPU architectures using OpenMP, AVX, and CUDA. For large datasets, our CUDA solution is superior. For example, the benchmark results show that optimal bounding spheres for inputs with tens of millions of points can be computed in just a few milliseconds.

Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:mdh:diva-31461 (URN)10.1016/j.cag.2016.01.003 (DOI)000375813900001 ()2-s2.0-84962520463 (Scopus ID)
Tillgänglig från: 2016-04-22 Skapad: 2016-04-22 Senast uppdaterad: 2018-02-23Bibliografiskt granskad
Holsti, N., Gustafsson, J., Källberg, L. & Lisper, B. (2015). Analysing switch-case code with abstract execution. In: OpenAccess Series in Informatics: . Paper presented at 15th International Workshop on Worst-Case Execution Time Analysis, WCET 2015, 7 July 2015 (pp. 85-94).
Öppna denna publikation i ny flik eller fönster >>Analysing switch-case code with abstract execution
2015 (Engelska)Ingår i: OpenAccess Series in Informatics, 2015, s. 85-94Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Constructing the control-flow graph (CFG) of machine code is made difficult by dynamic transfers of control (DTC), where the address of the next instruction is computed at run-time. Switchcase statements make compilers generate a large variety of machine-code forms with DTC. Two analysis approaches are commonly used: pattern-matching methods identify predefined instruction patterns to extract the target addresses, while analytical methods try to compute the set of target addresses using a general value-Analysis. We tested the abstract execution method of the SWEET tool as a value analysis for switch-case code. SWEET is here used as a plugin to the Bound-T tool: thus our work can also be seen as an experiment in modular tool design, where a general value-Analysis tool is used to aid the CFG construction in a WCET analysis tool. We find that the abstract-execution analysis works at least as well as the switch-case analyses in Bound-T itself, which are mostly based on pattern-matching. However, there are still some weaknesses: the abstract domains available in SWEET are not well suited to representing sets of DTC target addresses, which are small but sparse and irregular. Also, in some cases the abstract-execution analysis fails because the used domain is not relational, that is, does not model arithmetic relationships between the values of different variables. Future work will be directed towards the design of abstract domains eliminating these weaknesses.

Nyckelord
Dynamic control flow, Indexed branch, Machine-code analysis, WCET analysis, Data flow analysis, Embedded systems, Flow graphs, Pattern matching, Value engineering, Abstract executions, Analysis approach, Analytical method, Control flow graphs, Dynamic controls, Machine codes, Codes (symbols)
Nationell ämneskategori
Elektroteknik och elektronik
Identifikatorer
urn:nbn:se:mdh:diva-28721 (URN)10.4230/OASIcs.WCET.2015.85 (DOI)2-s2.0-84938521325 (Scopus ID)9783939897958 (ISBN)
Konferens
15th International Workshop on Worst-Case Execution Time Analysis, WCET 2015, 7 July 2015
Tillgänglig från: 2015-08-21 Skapad: 2015-08-21 Senast uppdaterad: 2015-08-21Bibliografiskt granskad
Källberg, L. & Larsson, T. B. (2015). Faster Approximation of Minimum Enclosing Balls by Distance Filtering and GPU Parallelization. Journal of Graphics Tools, 17(3), 67-84
Öppna denna publikation i ny flik eller fönster >>Faster Approximation of Minimum Enclosing Balls by Distance Filtering and GPU Parallelization
2015 (Engelska)Ingår i: Journal of Graphics Tools, ISSN 2165-3488, Vol. 17, nr 3, s. 67-84Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Furthermore, auto-tunable GPU solutions using CUDA are developed for both low- and high-dimensional cases. Empirical tests apply these techniques to two recent algorithms and demonstrate substantial speedups of the ball computations. Our results also indicate that a combination of the approaches has the potential to give further performance improvements.

Ort, förlag, år, upplaga, sidor
United States: Taylor & Francis, 2015
Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:mdh:diva-29243 (URN)10.1080/2165347X.2015.1037471 (DOI)
Projekt
RALF3 - Software for Embedded High Performance Architectures
Tillgänglig från: 2015-10-06 Skapad: 2015-09-29 Senast uppdaterad: 2018-02-23Bibliografiskt granskad
Källberg, L. & Larsson, T. B. (2014). Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering. In: Proceedings of SIGRAD 2014 SIGRAD 2014: . Paper presented at SIGRAD 2014 SIGRAD 2014, 12 Jun 2014, Gothenburg, Sweden.
Öppna denna publikation i ny flik eller fönster >>Accelerated Computation of Minimum Enclosing Balls by GPU Parallelization and Distance Filtering
2014 (Engelska)Ingår i: Proceedings of SIGRAD 2014 SIGRAD 2014, 2014Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Parallel GPU solutions using CUDA are developed for both low- and high-dimensional cases. Furthermore, two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Empirical tests show encouraging results. Compared to a sequential CPU version of the algorithm, the GPU parallelization runs up to 11 times faster. When applying the distance filtering techniques, further speedups are observed.

Nationell ämneskategori
Elektroteknik och elektronik
Identifikatorer
urn:nbn:se:mdh:diva-26452 (URN)
Konferens
SIGRAD 2014 SIGRAD 2014, 12 Jun 2014, Gothenburg, Sweden
Projekt
RALF3 - Software for Embedded High Performance Architectures
Tillgänglig från: 2014-10-31 Skapad: 2014-10-31 Senast uppdaterad: 2018-02-22Bibliografiskt granskad
Holsti, N., Gustafsson, J., Källberg, L. & Lisper, B. (2014). Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs. Västerås, Sweden: Mälardalen Real-Time Research Centre, Mälardalen University
Öppna denna publikation i ny flik eller fönster >>Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs
2014 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

The first step in the static analysis of a machine-code subprogram is to construct the control-flow graph. The typical method is to start from the known entry-point address of the subprogram, retrieve and decode the instruction at that point, insert it in the control-flow graph, determine the address(es) of the successor instruction(s) from the known semantics of the instruction set, and repeat the process for the successor instructions until all reachable instructions and control flows are discovered and entered in the control-flow graph. This procedure is straight-forward as long as the successors of each instruction are statically defined. However, most instruction sets allow for dynamically determined successors, usually by allowing the target address of a branch to be set by the run-time, dynamically computed value of a register. We call such instructions dynamic branches. To construct the control-flow graph, a static analyser must somehow discover the possible values of the target address, in other words, it must perform a value-analysis of the program. This is problematic for two reasons. Firstly, the value-analysis must be applied to an incomplete control-flow graph, which means that the value-analysis will also be incomplete, and may be an under-estimate of the value-set for the complete subprogram. Second, value-analyses typically over-estimate the value-set, which means that the set of possible target addresses of the dynamic branch may be over-estimated, which leads to an over-estimate of the control- flow graph. The over-estimated graph may include instructions and control flows that do not really belong to the subprogram under analysis. This report describes how we connected two analysis tools, Bound-T from Tidorum Ltd and SWEET from Mälardalen University, so that the powerful "abstract execution" analysis in SWEET can be invoked from Bound-T to resolve dynamic branches that Bound-T finds in the machine-code program under analysis. The program-representation language ALF, defined by the SWEET group, is used as an interface language between Bound-T and SWEET. We evaluate the combined analysis on example programs, including both synthetic and real ones, and conclude that the approach is promising but not yet a great improvement. Bound-T contains several special-case analyses for dynamic branches, which currently perform slightly better than SWEET's more general analyses. However, planned improvements to SWEET may result in an analysis which is at least as powerful but more robust than the analyses in Bound-T alone.

Ort, förlag, år, upplaga, sidor
Västerås, Sweden: Mälardalen Real-Time Research Centre, Mälardalen University, 2014
Serie
MRTC Reports, ISSN 1404-3041
Nyckelord
Worst-case execution-time analysis, WCET, dynamic control flow, indexed branch
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-28123 (URN)MDH-MRTC-299/2014-1-SE (ISRN)
Projekt
WCET - Worst-Case Execution Time analysisAPARTS - Advanced Program Analysis for Real-Time Systems
Tillgänglig från: 2015-06-08 Skapad: 2015-06-08 Senast uppdaterad: 2015-06-08Bibliografiskt granskad
Källberg, L. & Larsson, T. B. (2014). Improved pruning of large data sets for the minimum enclosing ball problem. Graphical Models, 76(6), 609-619
Öppna denna publikation i ny flik eller fönster >>Improved pruning of large data sets for the minimum enclosing ball problem
2014 (Engelska)Ingår i: Graphical Models, ISSN 1524-0703, E-ISSN 1524-0711, Vol. 76, nr 6, s. 609-619Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Minimum enclosing ball algorithms are studied extensively as a tool in approximation and classification of multidimensional data. We present pruning techniques that can accelerate several existing algorithms by continuously removing interior points from the input. By recognizing a key property shared by these algorithms, we derive tighter bounds than have previously been presented, resulting in twice the effect on performance. Furthermore, only minor modifications are required to incorporate the pruning procedure. The presented bounds are independent of the dimension, and empirical evidence shows that the pruning procedure remains effective in dimensions up to at least 200. In some cases, performance improvements of two orders of magnitude are observed for large data sets. © 2014 Elsevier Inc. All rights reserved.

Nyckelord
Acceleration techniques, Bounding spheres, Culling, Minimum enclosing balls, Pruning
Nationell ämneskategori
Data- och informationsvetenskap Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:mdh:diva-25799 (URN)10.1016/j.gmod.2014.06.003 (DOI)000347018500050 ()2-s2.0-84905501009 (Scopus ID)
Tillgänglig från: 2014-08-20 Skapad: 2014-08-20 Senast uppdaterad: 2018-02-23Bibliografiskt granskad
Larsson, T. B. & Källberg, L. (2013). Fast and robust approximation of smallest enclosing balls in arbitrary dimensions. Computer graphics forum (Print), 32(5), 93-101
Öppna denna publikation i ny flik eller fönster >>Fast and robust approximation of smallest enclosing balls in arbitrary dimensions
2013 (Engelska)Ingår i: Computer graphics forum (Print), ISSN 0167-7055, E-ISSN 1467-8659, Vol. 32, nr 5, s. 93-101Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1.001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets. 

Nyckelord
Arbitrary dimension, Empirical evaluations, General class, High dimensions, Large problems, Reliable results, Robust approximations, Theoretical arguments, Computer graphics, Approximation algorithms
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-21268 (URN)10.1111/cgf.12176 (DOI)000323204000010 ()2-s2.0-84882797817 (Scopus ID)
Tillgänglig från: 2013-09-06 Skapad: 2013-09-06 Senast uppdaterad: 2018-02-23Bibliografiskt granskad
Larsson, T. & Källberg, L. (2011). Fast Computation of Tight-Fitting Oriented Bounding Boxes. In: Game Engine Gems 2: (pp. 3-19). A K Peters/CRC Press
Öppna denna publikation i ny flik eller fönster >>Fast Computation of Tight-Fitting Oriented Bounding Boxes
2011 (Engelska)Ingår i: Game Engine Gems 2, A K Peters/CRC Press , 2011, s. 3-19Kapitel i bok, del av antologi (Övrigt vetenskapligt)
Abstract [en]

Figure 1.1. Computed boxes for a simple cube mesh (12 triangles) and star mesh (16 triangles). The first column shows the AABB, the second column shows the OBB computed by PCA, and the last column shows the OBB computed by DiTO. The meshes were randomly rotated before the computation. 

Ort, förlag, år, upplaga, sidor
A K Peters/CRC Press, 2011
Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:mdh:diva-10903 (URN)2-s2.0-85059364694 (Scopus ID)9781568814377 (ISBN)
Tillgänglig från: 2010-11-10 Skapad: 2010-11-10 Senast uppdaterad: 2019-01-10Bibliografiskt granskad
Organisationer
Identifikatorer
ORCID-id: ORCID iD iconorcid.org/0000-0002-6969-6793

Sök vidare i DiVA

Visa alla publikationer