Constraint Search Trees
Peter J. Stuckey · The MIT Press eBooks · 1997
This paper defines constraint search trees, a general tree data structure for storing and accessing items with constraints as keys. Constraint search trees can mimic binary search trees, radix search trees, k-d trees, R-trees and many other kinds of search trees. The unifying framework of constraint search trees immediately suggests new kinds of spatial data indexing techniques, as well as showing how to generalize intersection queries in spatial data structures for arbitrary shapes defined by constraints. Constraint search trees provide a data structure for storing sets (or disjunctions) of constraints. Hence they provide a useful data structure for implementing constraint databases. We define efficient algorithms for constraint database operations such as constraint selection, join and subsumption applied to constraint search trees.