O-trees: A constraint-based index structure

Abstract

Constraint search trees are a generic approach to search trees where all operations are defined in terms of constraints. This abstract viewpoint makes clear the fundamental operations of search trees and immediately points to new possibilities for search trees. In this paper we present height-balanced constraint search trees (HCSTs), a general approach to building height-balanced index structures, and exemplify the approach with a new spatial index structure, the O-tree. An object in an O-tree is represented by constraints of the form axi+bxj≤d where {a,b}⊆{-1,0,1} and x1,...,xn are the dimensions of the spatial data. We define the basic operations to build and search HCSTs, as well as const..