Korotkov

Spatial data storage and spatial queries processing are crucial tasks for modern databases. Efficiency of the spatial queries processing depends on index structure described below. R-tree is one of the most famous index structures, designed for spatial data storage. There are different versions of R-tree and their main distinctive feature is an algorithm of node splitting. Some algorithms of node splitting for two- and more dimensional R-trees contain one-dimensional node splitting as a composant. The problem of node splitting in one-dimensional R-tree may mistakenly seems trivial to consider it separately, because one-dimensional intervals can be divided, basing on their sorting. But existing algorithms fail to operate properly when dealing with different difficult cases. New algorithm of node splitting based on two sorts for one-dimensional case was proposed in this article. This algorithm tends to work better with those difficult problems. Algorithm of node splitting for two- and more dimensional R-trees based on that one-dimensional algorithm was also proposed in this article. Benchmark problems displayed that proposed algorithms worked better than existing ones in case of highly intersected data.

This work presents generalized search tree application for approximate string search. The task is to find all the strings from data domain which have distance to given string less than given threshold. Levenshtein metric is used in the capacity of string distance measure. Some subclass of regular expressions is used in the capacity of tree keys. The analysis of test results was performed and fields of further research is presented.