Finding the optimal location and keywords in obstructed and unobstructed space

Choudhury, F, Culpepper, S, Bao, Z and Sellis, T 2018, 'Finding the optimal location and keywords in obstructed and unobstructed space', VLDB Journal, vol. 27, no. 4, pp. 445-470.

Document type: Journal Article
Collection: Journal Articles

Title Finding the optimal location and keywords in obstructed and unobstructed space
Author(s) Choudhury, F
Culpepper, S
Bao, Z
Sellis, T
Year 2018
Journal name VLDB Journal
Volume number 27
Issue number 4
Start page 445
End page 470
Total pages 26
Publisher Association for Computing Machinery
Abstract The problem of optimal location selection based on reverse k nearest neighbor (RkNN) queries has been extensively studied in spatial databases. In this work, we present a related query, denoted as a Maximized Bichromatic Reverse Spatial Textual k Nearest Neighbor (MaxST) query, that finds an optimal location and a set of keywords for an object so that the object is a kNN object for as many users as possible. Such a query has many practical applications including advertisements, where the query is to find the location and the text contents to include in an advertisement so that it is relevant to the maximum number of users. The visibility of the advertisements also has an important role in the users' interests. In this work, we address two instances of the spatial relevance when ranking items: (1) the Euclidean distance and (2) the visibility. We carefully design a series of index structures and approaches to answer the MaxST for both instances. Specifically, we present (1) the Grp-topk approach that requires the computation of the top-k objects for all of the users first and then applies various pruning techniques to find the optimal location and keywords; (2) the Indiv-U approach, where we use similarity estimations to avoid computing the top-k objects of the users that cannot be a final result; and (3) the Index-U approach where we propose a hierarchical index structure over the users to improve pruning. We show that the keyword selection component in MaxST queries is NP-hard and present both approximate and exact solutions for the problem.
Subject Global Information Systems
Database Management
Keyword(s) Efficiency
Reverse kNN
Spatial-textual query
DOI - identifier 10.1007/s00778-018-0504-y
Copyright notice © Springer-Verlag GmbH Germany, part of Springer Nature 2018
ISSN 1066-8888
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 73 Abstract Views  -  Detailed Statistics
Created: Fri, 14 Dec 2018, 16:06:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us