• Jens Frøkjær
  • Palle B. Hansen
  • Ivan V. S. Larsen
  • Tom Oddershede
4. term, Computer Science, Master (Master Programme)
'The number of modifications is typically orders of magnitude higher than the number of queries on a database that stores moving regions. However, the predominant index structure for moving regions is the R+-tree and this structure handles spatial queries better than modifications. To address this problem a new indexing technique, called Layered Shifted Space-filling curves (LSS), is presented. LSS is optimized for modifications. It uses shifted layers in order to assign only a single index value to each region. Shifting layers guarantees that moving regions of a certain size always fit on a particular layer. A problem with canonical use of space-filling curves is that it requires prior knowledge of the data to be indexed. A self maintenance method for the LSS technique is proposed which makes LSS work without a prior knowledge of the data, e.g, world size. A performance study using the Oracle DBMS compares LSS to Oracle’s R+-trees and existing space-filling curve approaches. This study shows that LSS, compared to Oracle’s R+-trees, is up to 35 times faster for modifications at the expense of being up to 11 times slower for queries. Synthetic data is often preferred for performance testing as it is easy to control the conditions. This paper also proposes both a data and workload generator for generating n-dimensional moving objects. The data generator uses statistical distributions for moving and resizing the objects. When testing an index it is often desired to test a mix of modifications and queries. Therefore, this paper also provides a workload generator which produces a mix of inserts, updates, deletes, and spatial queries. A performance study shows that STDW is able to produce 27,000 object snapshots per second on a standard PC. '
Publication dateJun 2006
ID: 61067960