Использование префиксного дерева для хранения и поиска строк во внешней памяти
Аннотация
Поиск среди больших объёмов текстовых данных, хотя и изучается в computer science давно, не теряет своей актуальности. В работе представлена структура данных для поиска и эффективного хранения во внешней памяти массивов текстовых строк, реализованная для поддержки индексов в XML СУБД Sedna. Описываются алгоритмы для вставки, удаления и поиска строк переменной длинны в префиксных деревьях, хранимых на дисках. Мы также сравниваем нашу реализацию с существующей реализацией B-дерева. В работе показано, что в некоторых случаях предложенная структура данных занимает в несколько раз меньше места во внешней памяти при той же скорости поиска.
Список литературы
1. Andrey Fomichev and Maxim Grinev and Sergei D. Kuznetsov. Sedna: A Native XML DBMS. SOFSEM, pages 272-281, 2006.
2. Ilya Taranov et al. Sedna: native XML database management system (internals overview). SIGMOD Conference, pages 1037-1046, 2010.
3. Rudolf Bayer and Edward M. McCreight. Organization and Maintenance of Large Ordered Indices. Acta Inf., 1:173-189, 1972.
4. Rudolf Bayer and Karl Unterauer. Prefix B-Trees. ACM Trans. Database Syst., 2(1):11-26, 1977.
5. Nikolaus Walczuch and Herbert Hoeger. Using individual prefixes in B -trees. Journal of Systems and Software, 47(1):45-51, 1999.
6. Ratko Orlandic and Hosam M. Mahmoud. Storage Overhead of O-Trees, B-Trees and Prefix B-Trees: A Comparative Analysis. Int. J. Found. Comput. Sci., 7(3):209-226, 1996.
7. Douglas Comer. The Ubiquitous B-Tree. ACM Comput. Surv., 11(2):121-137, 1979.
8. Eugene Inseok Chong et al. A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B -trees. SIGMOD Record, 32(2):78-88, 2003.
9. Ricardo A. Baeza-Yates. An Adaptive Overflow Technique for B-trees. EDBT, pages 16-28, 1990.
10. B. Srinivasan. An Adaptive Overflow Technique to Defer Splitting in B-Trees. Comput. J., 34(5):397-405, 1991.
11. SQLLite File Format: B-Tree Structures. http://www.sqlite.org/fileformat.html#btree_structures
12. Walter A. Burkhard. Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst., 1(2):175-187, 1976.
13. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973.
14. Paolo Ferragina and Roberto Grossi. The String B-tree: A New Data Structure for String Search in External Memory and Its Applications. J. ACM, 46(2):236-280, 1999.
15. Wojciech Szpankowski. Patricia Tries Again Revisited. J. ACM, 37(4):691-711, 1990.
16. Joong Chae Na and Kunsoo Park. Simple Implementation of String B-Trees. SPIRE, pages 214-215, 2004.
17. Nikolas Askitis and Justin Zobel. B-tries for disk-based string management. VLDB J., 18(1):157-179, 2009.
18. Steffen Heinz and Justin Zobel and Hugh E. Williams. Burst tries: a fast, efficient data structure for string keys. ACM Trans. Inf. Syst., 20(2):192-223, 2002.
19. Neal Sample and Brian F. Cooper and Michael J. Franklin and Gsli R. Hjaltason and Moshe Shadmon and Levy Cohe. Managing Complex and Varied Data with the IndexFabric(tm). ICDE, pages 492-493, 2002.
20. Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.
21. Theodore Johnson and Dennis Shasha. B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half. J. Comput. Syst. Sci., 47(1):45-76, 1993.
22. Garcia-Molina, Hector and Ullman, Jeffrey D. and Widom, Jennifer. Database Systems: The Complete Book. Prentice Hall Press, Upper Saddle River, NJ, USA, 2 edition, 2008.
23. Michael Ley. Die Trierer Informatik-Bibliographie DBLP. GI Jahrestagung, pages 257-266, 1997.
24. N.A. Aznauryan, S.D. Kuznetsov, L.G. Novak, and M.N. Grinev. SLS: A numbering scheme for large XML documents, Programming and Computer Software, vol. 32, Jan. 2006, pp. 8-18.
25. Peter Pleshachkov and Petr Chardin and Sergei D. Kuznetsov. A DataGuide-Based Concurrency Control Protocol for Cooperation on XML Data. ADBIS 2005, Tallinn, Estonia, September 12-15, 2005, pp. 268-282
Рецензия
Для цитирования:
Таранов И.С. Использование префиксного дерева для хранения и поиска строк во внешней памяти. Труды Института системного программирования РАН. 2011;20.
For citation:
Taranov I. Using prefix trees for searching text strings with disk-based storage. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2011;20. (In Russ.)
Послать статью по эл. почте 