Change search
ReferencesLink to record
Permanent link

Direct link
Algorithms for aggregate information extraction from sequences
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2007. , 125 p.
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2007:25
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-16818Local ID: 02c53e60-0d09-11dc-8745-000ea68e967bOAI: diva2:989805
Godkänd; 2007; 20070528 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(973 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 973 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bengtsson, Fredrik
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link