000 04628nam a22005175i 4500
001 978-3-031-01885-5
003 DE-He213
005 20240730163742.0
007 cr nn 008mamaa
008 220601s2012 sz | s |||| 0|eng d
020 _a9783031018855
_9978-3-031-01885-5
024 7 _a10.1007/978-3-031-01885-5
_2doi
050 4 _aTK5105.5-5105.9
072 7 _aUKN
_2bicssc
072 7 _aCOM043000
_2bisacsh
072 7 _aUKN
_2thema
082 0 4 _a004.6
_223
100 1 _aBarsky, Marina.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980371
245 1 0 _aFull-Text (Substring) Indexes in External Memory
_h[electronic resource] /
_cby Marina Barsky, Alex Thomo, Ulrike Stege.
250 _a1st ed. 2012.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2012.
300 _aXV, 76 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aSynthesis Lectures on Data Management,
_x2153-5426
505 0 _aStructures for Indexing Substrings -- External Construction of Suffix Trees -- Scaling Up: When the Input Exceeds the Main Memory -- Queries for Disk-based Indexes -- Conclusions and Open Problems.
520 _aNowadays, textual databases are among the most rapidly growing collections of data. Some of these collections contain a new type of data that differs from classical numerical or textual data. These are long sequences of symbols, not divided into well-separated small tokens (words). The most prominent among such collections are databases of biological sequences, which are experiencing today an unprecedented growth rate. Starting in 2008, the "1000 Genomes Project" has been launched with the ultimate goal of collecting sequences of additional 1,500 Human genomes, 500 each of European, African, and East Asian origin. This will produce an extensive catalog of Human genetic variations. The size of just the raw sequences in this catalog would be about 5 terabytes. Querying strings without well-separated tokens poses a different set of challenges, typically addressed by building full-text indexes, which provide effective structures to index all the substrings of the given strings. Since full-text indexes occupy more space than the raw data, it is often necessary to use disk space for their construction. However, until recently, the construction of full-text indexes in secondary storage was considered impractical due to excessive I/O costs. Despite this, algorithms developed in the last decade demonstrated that efficient external construction of full-text indexes is indeed possible. This book is about large-scale construction and usage of full-text indexes. We focus mainly on suffix trees, and show efficient algorithms that can convert suffix trees to other kinds of full-text indexes and vice versa. There are four parts in this book. They are a mix of string searching theory with the reality of external memory constraints. The first part introduces general concepts of full-text indexes and shows the relationships between them. The second part presents the first series of external-memory construction algorithms that can handle the construction of full-text indexes for moderately large strings in the order of few gigabytes. The third part presents algorithms that scale for very large strings. The final part examines queries that can be facilitated by disk-resident full-text indexes. Table of Contents: Structures for Indexing Substrings / External Construction of Suffix Trees / Scaling Up: When the Input Exceeds the Main Memory / Queries for Disk-based Indexes / Conclusions and Open Problems.
650 0 _aComputer networks .
_931572
650 0 _aData structures (Computer science).
_98188
650 0 _aInformation theory.
_914256
650 1 4 _aComputer Communication Networks.
_980372
650 2 4 _aData Structures and Information Theory.
_931923
700 1 _aThomo, Alex.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980373
700 1 _aStege, Ulrike.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980374
710 2 _aSpringerLink (Online service)
_980375
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783031007576
776 0 8 _iPrinted edition:
_z9783031030130
830 0 _aSynthesis Lectures on Data Management,
_x2153-5426
_980376
856 4 0 _uhttps://doi.org/10.1007/978-3-031-01885-5
912 _aZDB-2-SXSC
942 _cEBK
999 _c84948
_d84948