Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 2007:25
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-16818Local ID: 02c53e60-0d09-11dc-8745-000ea68e967bOAI: oai:DiVA.org:ltu-16818DiVA: diva2:989805
Note
Godkänd; 2007; 20070528 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2017-11-24Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Bengtsson, Fredrik
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 108 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 235 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf