Publication Type
Journal Article
Version
publishedVersion
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
225
Last Page
244
ISSN
1066-8888
Identifier
10.1007/s00778-018-0497-6
Publisher
Springer Verlag (Germany)
Citation
ZHANG, Dongxiang; LI, Yuchen; CAO, Xin; SHAO, Jie; and SHEN, Heng Tao.
Augmented keyword search on spatial entity databases. (2018). VLDB Journal. 27, (3), 225-244.
Available at: https://ink.library.smu.edu.sg/sis_research/4037
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/s00778-018-0497-6
