S~*-tree: an improved S_-~+tree for coloured images~*

摘要

In this paper we propose and analyze a new spatial access method, namely the S_-~*-tree, for the efficient secondary memory encoding and manipulation of images containing multiple non-overlapping features (i.e., coloured images). We show that the S_-~*-tree is more space efficient than its precursor, namely the S_-~+-tree, which was explicitly designed for binary images, and whose straighforward extension to coloured images can lead to large space wastage. Moreover, we tested time efficiency of the S_-~*-tree in answering classical window queries, comparing it against a previous efficient access method, namely the HL-quadtree [7]. Our experiments show that the S_-~*-tree can reach up to a 30