dissertation · Repository of the University of Ljubljana (University of Ljubljana) · 2015

Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov

Lipnik, Izak

Cited by 0Open access

Abstract

We introduce a new text-indexing data structure, the String B-Tree, intended to search in unstructured data.We will focus on comparing string searching algorithm in String B-trees with algorithm ERA of Suffix Trees and algorithm COSD of Cache-Oblivious String Dictionarys.More specifically we focused on efficiency use of the memory hierarchies.The results we obtained are very interesting.Between all three algorithms, the String B-tree provides the fastest search in unstructured data, and has the most efficiency use of the memory hierarchies.At the same time we've got a proof, how important is efficiency use of the memory hierarchies.If the results of the String B-tree and the Suffix Tree were very similar, the results of the String Dictionary was much worse.It turns out that due to the large number of cache misses, which occurred in the structure of the String Dictionary, the String Dictionary spent more time just to transfer data in cache memory than the other two structures used for the entire search.At the beginning, we'll start with problem overview of searching in strings, then we'll learn about the memory hierarchy of today's computers, to help us understand the course of algorithms for searching in strings.In the next part, we'll introduce several examples of other text-indexing data strucuters.In the main part we'll get to know the String B-Tree in detail.In short phrase, it is a text-indexing data structure, that is a combination of classic B-trees and Patricia tries.In this part we'll also get to know the algorithm of searching strings in String B-trees, and implementation of the String B-tree. KAZALOIn the last part, we'll compare searching in strings in practice, between String B-trees, Suffix Trees and Cache-Oblivious String Dictionarys.We'll compare time and space complexity between algorithms for searching in strings.

Cite this paper

APA 7

Lipnik, I. (2015). Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov. Repository of the University of Ljubljana (University of Ljubljana).

MLA 9

Lipnik, Izak. “Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov.” Repository of the University of Ljubljana (University of Ljubljana), 2015.

Chicago

Lipnik, Izak. 2015. “Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov.” Repository of the University of Ljubljana (University of Ljubljana).

Harvard

Lipnik, I. (2015) ‘Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov’, Repository of the University of Ljubljana (University of Ljubljana).

BibTeX

@phdthesis{lipnik2015iskanje,
  title = {{Iskanje v nestrukturiranih podatkih z uporabo B-dreves nizov}},
  author = {Lipnik, Izak},
  school = {Repository of the University of Ljubljana (University of Ljubljana)},
  year = {2015}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.