Using prefix trees for searching text strings with disk-based storage
Abstract
Searching and storing large amounts of text data is a common problem in computer science, though it have been discussed for a long time. We introduce data structure for searching a set of string values and storing it on disk efficiently which is used for indexing XML data in Sedna XML DBMS. This paper describes algorithms for insertion, deletion and searching of variable-length strings in disk-resident trie structures. We also compare our implementation with existent B-tree implementation and show that proposed data structure in some cases occupies several times less disk space than B-tree does with the same search efficiency.
References
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
Review
For citations:
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.)
Email this article 