Skip to main content
Top

2015 | OriginalPaper | Chapter

Encodings of Range Maximum-Sum Segment Queries and Applications

Authors : Paweł Gawrychowski, Patrick K. Nicholson

Published in: Combinatorial Pattern Matching

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Given an array \(A\) containing arbitrary (positive and negative) numbers, we consider the problem of supporting range maximum-sum segment queries on \(A\): i.e., given an arbitrary range \([i,j]\), return the subrange \([i',j'] \subseteq [i,j]\) such that the sum \(\sum _{k=i'}^{j'} A[k]\) is maximized. (We use the terms segment and subrange interchangeably, but only use segment when referring to the name of the problem, for consistency with prior work.) Chen and Chao [Disc. App. Math. 2007] presented a data structure for this problem that occupies \(\varTheta (n)\) words, can be constructed in \(\varTheta (n)\) time, and supports queries in \(\varTheta (1)\) time. Our first result is that if only the indices \([i',j']\) are desired (rather than the maximum sum achieved in that subrange), then it is possible to reduce the space to \(\varTheta (n)\) bits, regardless the numbers stored in \(A\), while retaining the same construction and query time. Our second result is to improve the trivial space lower bound for any encoding data structure that supports range maximum-sum segment queries from \(n\) bits to \(1.89113n - \varTheta (\lg n)\), for sufficiently large values of \(n\). Finally, we also provide a new application of this data structure which simplifies a previously known linear time algorithm for finding \(k\)-covers: given an array \(A\) of \(n\) numbers and a number \(k\), find \(k\) disjoint subranges \([i_1 ,j_1 ],...,[i_k ,j_k]\), such that the total sum of all the numbers in the subranges is maximized. As observed by Csürös [IEEE/ACM TCBB 2004], \(k\)-covers can be used to identify regions in genomes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
In this paper we assume the word-RAM model with word size \(\varTheta (\log n)\) bits.
 
2
Alternatively, we can return the leftmost such range by symmetry.
 
3
Since \(G\) may be a multigraph the value of \(i\) may be arbitrary among all possible values that satisfy the equation. This is more general than we require, as we will not execute this type of query on a multigraph, so the answer will always be unique.
 
Literature
1.
go back to reference Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000) CrossRef Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000) CrossRef
2.
go back to reference Bengtsson, F., Chen, J.: Computing maximum-scoring segments in almost linear time. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 255–264. Springer, Heidelberg (2006) CrossRef Bengtsson, F., Chen, J.: Computing maximum-scoring segments in almost linear time. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 255–264. Springer, Heidelberg (2006) CrossRef
3.
go back to reference Bengtsson, F., Chen, J.: Computing maximum-scoring segments optimally. Technical report, Research Report, Luleå University of Technology (2007) Bengtsson, F., Chen, J.: Computing maximum-scoring segments optimally. Technical report, Research Report, Luleå University of Technology (2007)
4.
go back to reference Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448–461 (1972)MathSciNetCrossRef Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448–461 (1972)MathSciNetCrossRef
6.
go back to reference Csürös, M.: Maximum-scoring segment sets. IEEE/ACM Trans. Comput. Biol. Bioinform. 1(4), 139–150 (2004)CrossRef Csürös, M.: Maximum-scoring segment sets. IEEE/ACM Trans. Comput. Biol. Bioinform. 1(4), 139–150 (2004)CrossRef
7.
go back to reference Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 48–60. Springer, Heidelberg (2013) CrossRef Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 48–60. Springer, Heidelberg (2013) CrossRef
8.
go back to reference Fischer, J.: Data structures for efficient string algorithms. Ph.D. thesis, Ludwig-Maximilians-Universität München, October 2007 Fischer, J.: Data structures for efficient string algorithms. Ph.D. thesis, Ludwig-Maximilians-Universität München, October 2007
9.
go back to reference Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)MATHMathSciNetCrossRef Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)MATHMathSciNetCrossRef
10.
go back to reference Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci. 368(3), 231–246 (2006)MATHMathSciNetCrossRef Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci. 368(3), 231–246 (2006)MATHMathSciNetCrossRef
11.
go back to reference Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 549–554. IEEE Computer Society, Washington, DC (1989) Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 549–554. IEEE Computer Society, Washington, DC (1989)
12.
go back to reference Liu, H.F., Chao, K.M.: Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence. Theor. Comput. Sci. 407(1–3), 349–358 (2008)MATHMathSciNetCrossRef Liu, H.F., Chao, K.M.: Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence. Theor. Comput. Sci. 407(1–3), 349–358 (2008)MATHMathSciNetCrossRef
13.
14.
go back to reference Navarro, G.: Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 52 (2013) Navarro, G.: Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 52 (2013)
16.
17.
go back to reference Ruzzo, W.L., Tompa, M.: A linear time algorithm for finding all maximal scoring subsequences. In: Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, pp. 234–241. AAAI Press (1999) Ruzzo, W.L., Tompa, M.: A linear time algorithm for finding all maximal scoring subsequences. In: Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, pp. 234–241. AAAI Press (1999)
18.
go back to reference Skala, M.: Array range queries. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 333–350. Springer, Heidelberg (2013) CrossRef Skala, M.: Array range queries. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 333–350. Springer, Heidelberg (2013) CrossRef
Metadata
Title
Encodings of Range Maximum-Sum Segment Queries and Applications
Authors
Paweł Gawrychowski
Patrick K. Nicholson
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-19929-0_17

Premium Partner