Статья

Название статьи ПРИМЕНЕНИЕ RADIX ДЕРЕВЬЕВ ДЛЯ ИНДЕКСАЦИИ СЛАБОСТРУКТУРИРОВАННЫХ ДАННЫХ
Автор А.В. Чернов, В.И. Янц, Е.В. Карпенко
Рубрика РАЗДЕЛ II. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
Месяц, год 02, 2015
Индекс УДК 004.652
DOI
Аннотация В системах управления слабоструктурированными данными остро стоит проблема осуществления поиска в больших наборах данных. При осуществлении поиска выполняется значительно число дисковых операций, т.к. для работы с любыми видами данных требуется извлечь их из постоянного хранилища, при этом, на сегодняшний день, дисковая подсистема является самым медленным элементом компьютера. Как следствие, рост количества дисковых операций неминуемо приводит к быстрому исчерпанию вычислительных ресурсов СУБД. Для решения данной проблемы предлагается использовать Radix деревья с модифицированной многослойной структурой для построения поискового индекса. Каждый слой в такой структуре представляет собой дополнительное Radix дерево. Внутри слоя, ветви дерева помещены в структуры соответствующие размеру дискового блока. Переход между блоками осуществляется при помощи двух видов ссылок – маркированных и немаркированных. Ссылки связывают слои и позволяют переходить либо к конкретному, результирующему элементу в слое, либо к блоку данных содержащему ссылку на результирующий элемент дерева в следующем слое. Такая структура позволит выполнять не более 1-й дисковой операции на каждый слой индекса. При этом количество слоев в полученной структуре будет зависеть от объема данных и степени разнородности и лишь в редких случаях превысит число 3. Данная многоуровневая структура легко поддается кэшированию и позволяет сократить количество дисковых операций до одной на один поисковый запрос. Полученная структура позволяет нивелировать недостатки несбалансированных Radix деревьев и получить быстрый и компактный поисковый индекс для применения в широком круге систем управления слабоструктурированными данными, обеспечивая высокую скорость работы с наборами неоднородных, длинных и сложных строк.

Скачать в PDF

Ключевые слова Слабоструктурированные данные; индекс; поиск; базы данных, нагруженные деревья, radix деревья, сжатие данных; системы управления базами данных.
Библиографический список 1. Бутакова М.А., Климанская Е.В., Янц В.И. Мера информационного подобия для анализа слабоструктурированной информации // Современные проблемы науки и образования. – Пенза, 2013.
2. Климанская Е.В., Чернов А.В., Янц В.И. Методы обработки слабоструктурированных данных в автоматизированных системах на железнодорожном транспорте // Известия высших учебных заведений. Северо-Кавказский регион. Серия технические науки.
– 2013.
3. Abiteboul S. Querying semi-structured data // In Proc. ICDT, 2001.
4. Bertino E. Index configuration in object-oriented databases // VLDB Journal. – 1994. – № 3 (3). – P. 355-399.
5. Buneman P. et al. A query language and optimization techniques for unstructured data // In Proc. SIGMOD, 1996.
6. Chamberlain D., Robie J. and Florescu D. Quilt: An XML query language for heterogeneous data sources // In Proc. WebDB Workshop, 2000.
7. Comer D. The ubiquitous B-tree // Computing Surveys. – 1979. – № 11 (2). – P. 121-137.
8. Cooper B. and Shadmon M. The Index Fabric: A mechanism for indexing and querying the same data in many different ways. Technical Report, 2000. DBLP Computer Science Bibliography.
9. Deutsch A., Fernandez M. and Suciu D. Storing semistructured data with STORED // In Proc. SIGMOD, 1999.
10. Florescu D. and Kossmann D. A performance evaluation of alternative mapping schemes for storing XML data in a relational database. INRIA Technical Report 3684, 1999.
11. Alon Itai. The JS Data Structure. Technical report, 1999.
12. Lee W.C. and Lee D.L. Path Dictionary: A New Approach to Query Processing in Object-Oriented Databases // IEEE TKDE. – May/June 2004. – № 10(3). – P. 371-388.
13. Jason McHugh and Jennifer Widom. Query Optimization for XML // In Proc. 25th VLDB, 1999.
14. McHugh J. et al. Lore: A Database Management System for Semistructured Data // SIGMOD Record. – 1997. – № 26 (3). – P. 54-66,
15. Oracle Corp. Oracle 9i database. http://www.oracle.-com/ip/deploy/database/9i/index.html.
16. Shanmugasundaram J. et al. Relational databases for querying XML documents: Limitations and opportunities // In Proc. 25th VLDB, 2003.
17. Software AG. Tamino XML database. http://www.-softwareag.com/tamino/.
18. XYZFind. XML Database. http://www.xyzfind.com.
19. Кузнецов С. Транзакционные параллельные СУБД: новая волна // Труды Института системного программирования РАН. – М.: Институт системного программирования РАН, 2011. – Т. 20.
20. Zargayouna H. Context and semantic of semi-structured documents indexing // In First Cоnference in Information Retrieval and Applications (CORIA'O4), March 2004.

Comments are closed.