MaxiZone: Maximizing Influence Zone over Geo-Textual Data

Given a geo-textual dataset \mathbb {O}O, a set \varphiϕ of keywords, a query object q \in \mathbb {O}q∈O, and an integer kk, a reverse top-kk keyword-based location query returns the influence zone \mathcal {R}R of qq such that qq belongs to the result of a top-kk spatial keyword query with query keywords \varphiϕ and any location in \mathcal {R}R as arguments. For a query object qq, the influence zone of qq varies for different keywords \varphiϕ. Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called \tauτ-MaxiZone problem, which finds top-\tauτ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms.