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

Direktlänk
BETA
Bengtsson, Fredrik
Publikationer (10 of 12) Visa alla publikationer
Bengtsson, F. (2007). Algorithms for aggregate information extraction from sequences (ed.). (Doctoral dissertation). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>Algorithms for aggregate information extraction from sequences
2007 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

In this thesis, we propose efficient algorithms for aggregate information extraction from sequences and multidimensional arrays. The algorithms proposed are applicable in several important areas, including large databases and DNA sequence segmentation. We first study the problem of efficiently computing, for a given range, the range-sum in a multidimensional array as well as computing the k maximum values, called the top-k values. We design two efficient data structures for these problems. For the range-sum problem, our structure supports fast update while preserving low complexity of range-sum query. The proposed top-k structure provides fast query computation in linear time proportional to the sum of the sizes of a two-dimensional query region. We also study the k maximum sum subsequences problem and develop several efficient algorithms. In this problem, the k subsegments of consecutive elements with largest sum are to be found. The segments can potentially overlap, which allows for a large number of possible candidate segments. Moreover, we design an optimal algorithm for ranking the k maximum sum subsequences. Our solution does not require the value of k to be known a priori. Furthermore, an optimal linear-time algorithm is developed for the maximum cover problem of finding k subsequences of consecutive elements of maximum total element sum.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2007. s. 125
Serie
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2007:25
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-16818 (URN)02c53e60-0d09-11dc-8745-000ea68e967b (Lokalt ID)02c53e60-0d09-11dc-8745-000ea68e967b (Arkivnummer)02c53e60-0d09-11dc-8745-000ea68e967b (OAI)
Anmärkning
Godkänd; 2007; 20070528 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2007). Computing maximum-scoring segments optimally (ed.). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>Computing maximum-scoring segments optimally
2007 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Given a sequence of length n, the problem studied in this report is to find a set of k disjoint subsequences of consecutive elements such that the total sum of all elements in the set is maximized. This problem arises in the analysis of DNA sequences. The previous best known algorithm requires time proportional to n times the inverse Ackermann function of (n,n), in the worst case. We present a linear-time algorithm, which is optimal, for this problem.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2007. s. 10
Serie
Forskningsrapport / Luleå tekniska universitet, ISSN 1402-1528 ; 2007:3
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-22852 (URN)48a93dc0-5d75-11dc-8151-000ea68e967b (Lokalt ID)48a93dc0-5d75-11dc-8151-000ea68e967b (Arkivnummer)48a93dc0-5d75-11dc-8151-000ea68e967b (OAI)
Anmärkning
Godkänd; 2007; 20070907 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2007). Ranking k maximum sums (ed.). Paper presented at . Theoretical Computer Science, 377(1-3), 229-237
Öppna denna publikation i ny flik eller fönster >>Ranking k maximum sums
2007 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 377, nr 1-3, s. 229-237Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Given a sequence of n real numbers and an integer parameter k, the problem studied in this paper is to compute k subsequences of consecutive elements with the sums of their elements being the largest, the second largest, and the kth largest among all possible range sums of the input sequence. For any value of k, 1 <= k <= n (n + 1)/2, we design a fast algorithm that takes O (n + k log n) time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for k = O (n) by providing a matching lower bound.Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined).Furthermore, given the fact that we have computed the fth largest sums, our algorithm retrieves the (l + 1)th largest sum in O (log n) time, after O (n) time of preprocessing.

Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-2927 (URN)10.1016/j.tcs.2007.03.011 (DOI)000247279200017 ()2-s2.0-34247634994 (Scopus ID)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (Lokalt ID)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (Arkivnummer)0a9d4820-5ac1-11dc-8a1d-000ea68e967b (OAI)
Anmärkning
Validerad; 2007; 20070904 (pafi)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-07-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2006). Computing maximum-scoring segments in almost linear time (ed.). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>Computing maximum-scoring segments in almost linear time
2006 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires n log n time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(n a(n, n) ) time in the worst case, where a(n,n) is the inverse Ackermann function.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2006. s. 21
Serie
Forskningsrapport / Luleå tekniska universitet, ISSN 1402-1528 ; 2006:14
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-25447 (URN)f3c6bb30-b210-11db-bf9d-000ea68e967b (Lokalt ID)f3c6bb30-b210-11db-bf9d-000ea68e967b (Arkivnummer)f3c6bb30-b210-11db-bf9d-000ea68e967b (OAI)
Anmärkning
Godkänd; 2006; 20070201 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2006). Computing maximum-scoring segments in almost linear time (ed.). In: (Ed.), Danny Z. Chen (Ed.), Computing and Combinatorics: 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings. Paper presented at Annual International Computing and Combinatorics Conference : 15/08/2006 - 18/08/2006 (pp. 255-264). : Encyclopedia of Global Archaeology/Springer Verlag
Öppna denna publikation i ny flik eller fönster >>Computing maximum-scoring segments in almost linear time
2006 (Engelska)Ingår i: Computing and Combinatorics: 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings / [ed] Danny Z. Chen, Encyclopedia of Global Archaeology/Springer Verlag, 2006, s. 255-264Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.

Ort, förlag, år, upplaga, sidor
Encyclopedia of Global Archaeology/Springer Verlag, 2006
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4112
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-31459 (URN)10.1007/11809678_28 (DOI)5a2a9d00-7bed-11dc-a72d-000ea68e967b (Lokalt ID)978-3-540-36925-7 (ISBN)5a2a9d00-7bed-11dc-a72d-000ea68e967b (Arkivnummer)5a2a9d00-7bed-11dc-a72d-000ea68e967b (OAI)
Konferens
Annual International Computing and Combinatorics Conference : 15/08/2006 - 18/08/2006
Anmärkning
Validerad; 2006; 20071016 (bson)Tillgänglig från: 2016-09-30 Skapad: 2016-09-30 Senast uppdaterad: 2018-01-14Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2006). Efficient algorithms for k maximum sums (ed.). Paper presented at . Algorithmica, 46(1), 27-41
Öppna denna publikation i ny flik eller fönster >>Efficient algorithms for k maximum sums
2006 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, nr 1, s. 27-41Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers {x1,x2,...,xn} and an integer parameter k, 1 ≤ k ≤ 1/2n(n-1),the problem involves finding the k largest values of ∑ℓ=ijxℓ for 1 ≤ i ≤ j ≤ n.The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a Θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in O(min {k+nlog2n,n√k} ) time in the worst case. Our algorithm is optimal for k = Ω(n log 2 n) and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well

Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-15460 (URN)10.1007/s00453-006-0076-x (DOI)000240060500004 ()2-s2.0-33747888787 (Scopus ID)ef8af840-7bed-11dc-a72d-000ea68e967b (Lokalt ID)ef8af840-7bed-11dc-a72d-000ea68e967b (Arkivnummer)ef8af840-7bed-11dc-a72d-000ea68e967b (OAI)
Anmärkning
Validerad; 2006; 20071016 (bson)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-07-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2005). A note on ranking k maximum sums (ed.). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>A note on ranking k maximum sums
2005 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

In this paper, we design a fast algorithm for ranking the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem is to compute k subsequences of consecutive elements with the sums of their elements being the largest, second largest, ..., and the k:th largest among all possible range sums. For any value of k, 1 <= k <= n(n+1)/2, our algorithm takes O(n + k log n) time in the worst case to rank all such subsequences. Our algorithm is optimal for k <= n.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2005. s. 9
Serie
Forskningsrapport / Luleå tekniska universitet, ISSN 1402-1528 ; 2005:08
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-23826 (URN)894036c0-b2a0-11db-bf9d-000ea68e967b (Lokalt ID)894036c0-b2a0-11db-bf9d-000ea68e967b (Arkivnummer)894036c0-b2a0-11db-bf9d-000ea68e967b (OAI)
Anmärkning
Godkänd; 2005; 20070202 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2004). Computing the k maximum subarrays fast (ed.). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>Computing the k maximum subarrays fast
2004 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

We study the problem of computing the k maximum sum subarrays. Given an array of real numbers and an integer, k, the problem involves finding the k largest values of the sum from i to j of the array, for any i and j. The problem for fixed k=1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. In this paper, we develop an algorithm requiring time proportional to n times square root of k for an array of length n. Moreover, for two-dimensional version of the problem, which computes the k largest sums over all rectangular subregions of an m times n array of real numbers, we show that it can be solved efficiently in the worst case as well.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2004. s. 7
Serie
Forskningsrapport / Luleå tekniska universitet, ISSN 1402-1528 ; 2004:07
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-25205 (URN)e2ef04f0-ece6-11db-bc0c-000ea68e967b (Lokalt ID)e2ef04f0-ece6-11db-bc0c-000ea68e967b (Arkivnummer)e2ef04f0-ece6-11db-bc0c-000ea68e967b (OAI)
Anmärkning
Godkänd; 2004; 20070417 (ysko)Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. (2004). Efficient aggregate queries on data cubes (ed.). (Licentiate dissertation). Paper presented at . Luleå: Luleå tekniska universitet
Öppna denna publikation i ny flik eller fönster >>Efficient aggregate queries on data cubes
2004 (Engelska)Licentiatavhandling, monografi (Övrigt vetenskapligt)
Abstract [en]

As computers are developing rapidly and become more available to the modern information society, the possibility and ability to handle large data sets in database applications increases. The demand for efficient algorithmic solutions to process huge amounts of information increases as the data sets become larger. In this thesis, we study the efficient implementation of aggregate operations on the data cube, a modern and flexible model for data warehouses. In particular, the problem of computing the k largest sum subsequences of a given sequence is investigated. An efficient algorithm for the problem is developed. Our algorithm is optimal for large values of the user-specified parameter k. Moreover, a fast in-place algorithm with good trade-off between update- and query-time, for the multidimensional orthogonal range sum problem, is presented. The problem studied is to compute the sum of the data over an orthogonal range in a multidimensional data cube. Furthermore, a fast algorithmic solution to the problem of maintaining a data structure for computing the k largest values in a requested orthogonal range of the data cube is also proposed.

Ort, förlag, år, upplaga, sidor
Luleå: Luleå tekniska universitet, 2004. s. 63
Serie
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757 ; 2004:53
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-18506 (URN)8f0bbaa0-b167-11db-bf9d-000ea68e967b (Lokalt ID)8f0bbaa0-b167-11db-bf9d-000ea68e967b (Arkivnummer)8f0bbaa0-b167-11db-bf9d-000ea68e967b (OAI)
Anmärkning

Godkänd; 2004; 20070131 (ysko)

Tillgänglig från: 2016-09-29 Skapad: 2016-09-29 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Bengtsson, F. & Chen, J. (2004). Efficient algorithms for k maximum sums (ed.). In: (Ed.), Rudolf Fleischer; Gerhard Trippen (Ed.), Algorithms and Computation: 15th International Symposium, ISAAC 2004. Paper presented at International Symposium on Algorithms and Computation : 20/12/2004 - 22/12/2004 (pp. 137-148). Berlin: Encyclopedia of Global Archaeology/Springer Verlag
Öppna denna publikation i ny flik eller fönster >>Efficient algorithms for k maximum sums
2004 (Engelska)Ingår i: Algorithms and Computation: 15th International Symposium, ISAAC 2004 / [ed] Rudolf Fleischer; Gerhard Trippen, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2004, s. 137-148Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers (x1,x2,⋯,xn) and an integer parameter k, l ≤ k ≤ 1/2n(n -1), the problem involves finding the k largest values of Σl=ij xl for 1 ≤ i ≤ j ≤ n. The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper, we design efficient algorithms that solve the above problem in O (min{k + n log2 n, n √k}) time in the worst case. Our algorithm is optimal for k ≥ n log2 n and improves over the previously best known result for any value of the user-defined parameter k. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well

Ort, förlag, år, upplaga, sidor
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2004
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3341
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
urn:nbn:se:ltu:diva-35524 (URN)10.1007/b104582 (DOI)a13f3f40-7beb-11dc-a72d-000ea68e967b (Lokalt ID)978-3-540-24131-7 (ISBN)a13f3f40-7beb-11dc-a72d-000ea68e967b (Arkivnummer)a13f3f40-7beb-11dc-a72d-000ea68e967b (OAI)
Konferens
International Symposium on Algorithms and Computation : 20/12/2004 - 22/12/2004
Anmärkning
Validerad; 2004; 20071016 (bson)Tillgänglig från: 2016-09-30 Skapad: 2016-09-30 Senast uppdaterad: 2018-01-14Bibliografiskt granskad
Organisationer

Sök vidare i DiVA

Visa alla publikationer