User Defined Indexing

David Vaz, Vítor Santos Costa and Michel Ferreira

July 2009

---

Abstract

Logic programming provides an ideal framework for tackling complex data, such as the multi-dimensional vector-based data used to represent spatial databases. Unfortunately, the usefulness of logic programming systems if often hampered by the fact that most of these systems have to rely on a single unification-based mechanism as the only way to search in the database. While unification can usually take effective advantage of hash-based indexing, it is often the case that queries over more complex and structured data, such as the vectorial terms stored in spatial databases, cannot.
We propose a new extension to Prolog indexing: User Defined Indexing (UDI). In this mechanism, the programmer may add extra information to Prolog indices so that only interesting fragments of the database will be selected. UDI provides a general extension of indexing, and can be used for both instantiated and constrained variables. As a test case, we demonstrate how UDI can be combined with a constraint system to provide an elegant and efficient mechanism to generate and execute range queries and spatial queries. Experimental evaluation shows that this mechanism can achieve orders of magnitude speedups on non-trivial datasets.

Bibtex

@InProceedings{vaz-iclp09,
  author =    {D. Vaz and V. Santos Costa and M. Ferreira},
  title =     {{User Defined Indexing}},
  booktitle = {Proceedings of the 25th International Conference on Logic Programming (ICLP 2009)},
  pages =     {372--386},
  number =    {5649},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {P. Hill and D. S. Warren},
  month =     {July},
  year =      {2009},
  address =   {Pasadena, California, USA},
}

Download Paper

PDF file
Springer