O-trees: A constraint-based index structure

I. Sitzmann, P. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)


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 constraint joins. We illustrate these algorithms using O-trees showing how the algorithms can make use of the more accurate information in the O-tree nodes. Experiments compare the IO-performance of the 2-dimensional O-tree with the R-tree.

Original languageEnglish
Title of host publicationProceedings - 11th Australasian Database Conference, ADC 2000
EditorsMaria E. Orlowska
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages8
ISBN (Electronic)0769505287, 9780769505282
Publication statusPublished - 1 Jan 2000
Externally publishedYes
EventAustralasian Database Conference 2000 - Canberra, Australia
Duration: 31 Jan 20003 Feb 2000
Conference number: 11th
https://dl.acm.org/doi/proceedings/10.5555/520939 (Proceedings)

Publication series

NameProceedings - 11th Australasian Database Conference, ADC 2000


ConferenceAustralasian Database Conference 2000
Abbreviated titleADC 2000
Internet address

Cite this