Back to Index

AppString > AppStringDoc

  1. LBAK-Tree
    1. Introduction
    2. Overview
      1. Fixed-Level (FL)
      2. Variable-Level (VL)
      3. Variable-Level Exploiting Keyword Frequencies (VLF)
    3. Contributors
    4. References



This module provides location-based approximate keyword search.

For example, it can answer queries such as find Alkatras near San Fransisco. Notice that Alkatras is misspelled but the LBAK-Tree can still find useful answers. In short, the LBAK-Tree answers queries with a spatial component and a keyword component, where the keywords don't need to match exactly but approximately.


The LBAK-Tree is based on a hierarchical spatial index that is enhanced with inverted indexes for approximate string lookups. In our implementation we use an R*-Tree as spatial index and use the FilterTreeDoc module (part of Flamingo) to implement the inverted indexes for approximate string lookups.

Our paper Supporting Location-Based Approximate-Keyword Queries describes three variants of the LBAK-Tree which differ in where they place inverted indexes in the spatial index. This module contains all their implementations:

Fixed-Level (FL)

Illustration of FL algorithm

Variable-Level (VL)

Illustration of VL algorithm

Variable-Level Exploiting Keyword Frequencies (VLF)

Illustration of VLF algorithm

Please have a look at in the lbaktree/src folder to get started!