Augmented keyword search on spatial entity databases

Publication Type

Journal Article

Publication Date

4-2018

Abstract

In this paper, we propose a new type of query that augments the spatial keyword search with an additional boolean expression constraint. The query is issued against a corpus of structured or semi-structured spatial entities and is very useful in applications like mobile search and targeted location-aware advertising. We devise three types of indexing and filtering strategies. First, we utilize the hybrid IR2" role="presentation" style="display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; position: relative;">IR2IR2-tree and propose a novel hashing scheme for efficient pruning. Second, we propose an inverted index-based solution, named BE-Inv, that is more cache concious and exhibits great pruning power for boolean expression matching. Our third method, named SKB-Inv, adopts a novel two-level partitioning scheme to organize the spatial entities into inverted lists and effectively facilitate the pruning in the spatial, textual, and boolean expression dimensions. In addition, we propose an adaptive query processing strategy that takes into account the selectivity of query keywords and predicates for early termination. We conduct our experiments using two real datasets with 3.5 million Foursquare venues and 50 million Twitter geo-profiles. The results show that the methods based on inverted index are superior to the hybrid IR2" role="presentation" style="display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; position: relative;">IR2IR2-tree; and SKB-Inv achieves the best performance.

Keywords

Spatial keyword search, Boolean expression matching, IR-tree, Inverted index, Two-level partitioning

Discipline

Computer Engineering | Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

VLDB Journal

Volume

27

Issue

3

First Page

1

Last Page

20

ISSN

1066-8888

Identifier

10.1007/s00778-018-0497-6

Publisher

Springer Verlag (Germany)

Additional URL

https://doi.org/10.1007/s00778-018-0497-6

Link to Full Text

Share

COinS