نمایه‌های تمام‌متن (زیررشته‌ای) در حافظه خارجی ۲۰۲۲
Full-Text (Substring) Indexes in External Memory 2022

امروزه، پایگاه‌های داده متنی در میان مجموعه‌های داده‌ای هستند که با سرعت بسیار زیادی در حال رشد می‌باشند. برخی از این مجموعه‌ها، شامل نوع جدیدی از داده‌ها هستند که با داده‌های عددی یا متنی کلاسیک متفاوت است. این داده‌ها، توالی‌های طولانی از نمادها هستند که به نشانه‌های کوچک (کلمات) مجزا تقسیم نشده‌اند. برجسته‌ترین این مجموعه‌ها، پایگاه‌های داده توالی‌های بیولوژیکی هستند که امروزه نرخ رشد بی‌سابقه‌ای را تجربه می‌کنند. از سال 2008، “پروژه 1000 ژنوم” با هدف نهایی جمع‌آوری توالی‌های 1500 ژنوم انسانی دیگر، 500 ژنوم از هر یک از نژادهای اروپایی، آفریقایی و آسیای شرقی، آغاز شده است. این پروژه، یک فهرست گسترده از تغییرات ژنتیکی انسان را تولید خواهد کرد. حجم تنها توالی‌های خام در این فهرست، حدود 5 ترابایت خواهد بود. پرس‌و‌جو در رشته‌های بدون نشانه‌های مجزا، مجموعه‌ای متفاوت از چالش‌ها را ایجاد می‌کند که معمولاً با ساختن فهرست‌های تمام‌متن (Full-Text Indexes) به آن‌ها پرداخته می‌شود. این فهرست‌ها، ساختارهای مؤثری برای فهرست‌بندی تمام زیررشته‌های رشته‌های داده‌شده فراهم می‌کنند. از آنجایی که فهرست‌های تمام‌متن فضای بیشتری نسبت به داده‌های خام اشغال می‌کنند، اغلب لازم است از فضای دیسک برای ساخت آن‌ها استفاده شود. با این حال، تا همین اواخر، ساخت فهرست‌های تمام‌متن در حافظه ثانویه به دلیل هزینه‌های بیش از حد ورودی/خروجی، غیرعملی تلقی می‌شد. با وجود این، الگوریتم‌های توسعه‌یافته در دهه گذشته نشان داده‌اند که ساخت خارجی کارآمد فهرست‌های تمام‌متن در واقع امکان‌پذیر است. این کتاب درباره ساخت و استفاده در مقیاس بزرگ از فهرست‌های تمام‌متن است. ما عمدتاً بر روی درخت‌های پسوندی (Suffix Trees) تمرکز می‌کنیم و الگوریتم‌های کارآمدی را نشان می‌دهیم که می‌توانند درخت‌های پسوندی را به انواع دیگر فهرست‌های تمام‌متن تبدیل کنند و بالعکس. این کتاب از چهار بخش تشکیل شده است. این بخش‌ها ترکیبی از تئوری جستجوی رشته با واقعیت محدودیت‌های حافظه خارجی هستند. بخش اول، مفاهیم کلی فهرست‌های تمام‌متن را معرفی می‌کند و روابط بین آن‌ها را نشان می‌دهد. بخش دوم، اولین مجموعه از الگوریتم‌های ساخت حافظه خارجی را ارائه می‌کند که می‌توانند ساخت فهرست‌های تمام‌متن را برای رشته‌های نسبتاً بزرگ در حدود چند گیگابایت انجام دهند. بخش سوم، الگوریتم‌هایی را ارائه می‌کند که برای رشته‌های بسیار بزرگ مقیاس‌پذیر هستند. بخش آخر، پرس‌و‌جوهایی را بررسی می‌کند که می‌توانند توسط فهرست‌های تمام‌متن مقیم دیسک تسهیل شوند.

فهرست مطالب: ساختارها برای فهرست‌بندی زیررشته‌ها / ساخت خارجی درخت‌های پسوندی / مقیاس‌بندی: زمانی که ورودی از حافظه اصلی فراتر رود / پرس‌و‌جوها برای فهرست‌های مبتنی بر دیسک / نتیجه‌گیری‌ها و مسائل حل‌نشده

Nowadays, 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