SP-GiST Home - Department of Computer Science - Purdue University Skip to main content
SP GIST logo


A General Index Framework for Space Partitioning Trees

Emerging database applications require the use of new indexing structures beyond B-trees and R-trees. Examples are the k-d tree, the trie, the quadtree, and their variants. They are often proposed as supporting structures in data mining, GIS, CAD/CAM and biological database applications. A common feature of all these indexes is that they recursively divide the space into partitions.

SP-GiST Version 2 is an indexing tool that works under PostgreSQL. It allows the creation of non-traditional disk-based indexes that belong to the class of space-partitioning trees to serve the needs of emerging database applications.. Examples of indexes one can instantiate in PostgreSQL using SP-GiST are disk-based versions of the trie and its variants (e.g., patricia tries), quad-trees and their variants (e.g., the point quad-tree, the PMR quad-tree, and the oct-tree), and k-d trees. 

Last Updated: Jun 1, 2017 12:29 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone: (765) 494-6010 • Fax: (765) 494-0739

Copyright © 2024 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.