# Influential Slot and Tag Selection in Billboard Advertisement

Dildar Ali  Department of Computer Science and Engineering,
Indian Institute of Technology JammuJammuJammu & KashmirIndia181221
<EMAIL_ADDRESS>,  Tejash Gupta  Department of Mathematics and
Scientific Computing, National Institute of Technology Hamirpur1 Thørväld
CircleHamirpurHimachal PradeshIndia<EMAIL_ADDRESS>,  Suman Banerjee
Department of Computer Science and Engineering,
Indian Institute of Technology Jammu1 Thørväld CircleJammuJammu & KashmirIndia
<EMAIL_ADDRESS>and  Yamuna Prasad  Department of Computer
Science and Engineering,
Indian Institute of Technology Jammu1 Thørväld CircleJammuJammu & KashmirIndia
<EMAIL_ADDRESS>
###### Abstract.

The selection of influential billboard slots remains an important problem in
billboard advertisements. Existing studies on this problem have not considered
the case of context-specific influence probability. To bridge this gap, in
this paper, we introduce the Context Dependent Influential Billboard Slot
Selection Problem. First, we show that the problem is NP-hard. We also show
that the influence function holds the bi-monotonicity, bi-submodularity, and
non-negativity properties. We propose an orthant-wise Stochastic Greedy
approach to solve this problem. We show that this method leads to a constant
factor approximation guarantee. Subsequently, we propose an orthant-wise
Incremental and Lazy Greedy approach. In a generic sense, this is a method for
maximizing a bi-submodular function under the cardinality constraint, which
may also be of independent interest. We analyze the performance guarantee of
this algorithm as well as time and space complexity. The proposed solution
approaches have been implemented with real-world billboard and trajectory
datasets. We compare the performance of our method with many baseline methods,
and the results are reported. Our proposed orthant-wise stochastic greedy
approach leads to significant results when the parameters are set properly
with reasonable computational overhead.

Billboard Advertisement, Billboard Database, Trajectory Database, Influence
Probability, Bi-Submodularity

††copyright: none††ccs: Information Systems Computational Advertising

##  1\. Introduction

In recent times, due to the advancement of wireless internet and hand-held
mobile devices, it has become easier to capture moving object’s locations.
This leads to the availability of many datasets of the following kind:
location information of a set of moving objects over different time stamps.
This kind of database is called _Trajectory Database_ (Wang et al., 2021) and
has been used to solve many real-life problems, including route
recommendation, driving behavior prediction, influential location selection
problems, etc. A trajectory database contains the location information of
moving objects, and managing, mining, and efficiently retrieving the required
information leads to a completely new discipline called _Spatial Databases_.
Many Internet Giants, including Google, Alibaba, etc., are in the business of
spatial databases and earn a significant portion of their total revenue.

‘Advertisement’ remains a central theme of any commercial house. The
literature has reported that a commercial house spends $7-10\%$ of its earned
revenue on advertisement. There are several methods by which advertisement can
be conducted, e.g., social media, sponsored search auctions, digital
billboards, etc. Billboard advertising has emerged as an effective approach
among all these techniques due to many advantages, such as ensuring a return
on investment. In billboard advertisement, the billboards are owned by some
other company (e.g., Lamar, Sigtel, etc.), and different e-commerce houses
approach the company for a number of billboard slots depending on their
budget. Here, the question is given the trajectory database, billboard
database, and a positive integer $k$, in which $k$ billboard slots should be
chosen to maximize the influence. This problem has been referred to as the
Top-$k$ Influential Billboard Slot Selection Problem in the literature (Ali et
al., 2023), and a few solution methodologies are available. The influence
probability between a billboard slot and a trajectory has been considered in
all the studies (Ali et al., 2023, 2022; Zhang et al., 2019, 2020). However,
in practice, it varies from context to context. This means it is meaningful to
show the advertisement of a low-cost product (rather than a costly product) to
a low-income person. In this paper, we extend the study of influential
billboard slot selection in the context-specific setting where, for every tag,
there exists a tag-specific influence probability.

In real-world scenarios, billboard advertisement requires not only the
selection of influential slots but also the selection of influential tags.
Now, the question is that given two positive integers $k$ and $\ell$, which
$k$ influential slots and $\ell$ influential tags should be chosen such that
the influence is maximized. To the best of our knowledge, such a problem has
not been addressed in billboard advertisement settings. However, some studies
focus on the influence maximization in the presence of tags in social
networks. The first study in this direction was done by Ke et al. (Ke et al.,
2018), where they studied the problem of finding $k$ seed nodes and $r$
influential tags to maximize the influence in the network. Subsequently, other
solution methodologies have been proposed in the literature, e.g., community-
based approach (Banerjee and Pal, 2022) that exploits the bi-submodularity of
the influence function. This paper bridges this gap by studying the
influential billboard slot selection problem in tag-specific influence
probability settings. In particular, we make the following contributions in
this paper:

  * •

We study the problem of selecting Influential Billboard Slots in the tag-
specific influence probability setting where the goal is to select influential
billboard slots and influential tags to maximize the influence. We formally
call this problem the Influential Slot and Tag Selection Problem.

  * •

We establish several important properties of the influence function and
exploit them to design efficient algorithms to solve this problem.

  * •

We propose an efficient Orthent-wise Stochastic Greedy Maximization Algorithm
and subsequently introduce the Orthent-wise Incremental and Lazy Greedy
Maximization Algorithm.

  * •

We analyze all the algorithms to understand time and space complexities and
performance guarantees.

  * •

Finally, we conduct a number of experiments with real-world trajectory
datasets to exhibit the effectiveness and efficiency of the proposed solution
approaches.

The rest of the paper is organized as follows. Section 2 describes recent
studies from the literature. Section 3 describes the problem background and
defines our problem formally. The proposed solution approaches have been
described in Section 4. Section 5 describes the experimental evaluations of
the proposed solutions. Finally, Section 6 concludes and gives future research
directions.

##  2\. Related Work

In this section, we discuss relevant studies from the literature. This study
comes under the broad umbrella of database and data management. Therefore, we
categorize our literature survey into four major categories: Influential
Location Identification, Influential Billboard Slot Selection, Trajectory-
driven Influence Maximization, and Context-dependent Influence Maximization.

###  2.1. Influential Location Identification

The Site Selection problem has gained significant attention from researchers
due to its wide range of applications. A previous study by Zhou et al. (Zhou
et al., 2011) examined the MaxBRkNN problem, which focuses on finding the
optimal location with the highest number of trajectories as its k-nearest
neighbors based on distance measurements. However, their study assumed fixed
user locations, while our case involves a fixed billboard location and the
evaluation of its influence on moving trajectories. Next, the concept of
location-aware influence maximization problems (Li et al., 2014), (Liu et al.,
2017) is motivated by traditional influence maximization problems, where the
goal is to select a subset of nodes in a social network to maximize influence
spread. While both types of problems aim to maximize influence, there is a
distinction in how influence is propagated. In social networks, influence
spreads from one user to another, whereas in our influence model, an audience
is only influenced if they come across the range of a billboard. Wang et al.
(Wang et al., 2016) studied the problem of selecting probabilistic influence-
based optimal locations to place several facilities. They considered the
moving objects and proposed two noble algorithms and one distance measure. Liu
et al. (Liu et al., 2021) studied the problem of Competitive Location
Selection over Moving Objects that considered competition against the existing
facilities. They presented an influence score model to calculate the
influence. Subsequently, they proposed an efficient pruning technique. Mitra
et al. (Mitra et al., 2019) studied the problem of selecting Top-$k$ locations
to place facilities to maximize user convenience. They defined the notion of
convenience as the minimum extra distance that needs to be traveled to avail
of the facilities. They proposed two variants of the problem. The first one
focuses on minimizing the maximum extra distance that needs to be traveled by
any user, while the second one aims to reduce the total extra distance
traveled by all the users. To address this, they proposed efficient heuristic
solutions. Next, Qi et al. (Qi et al., 2020) studied the online facility
placement problem considering three features, namely user convenience,
temporal impacts, and user coverage. They proposed an $(1-\frac{1}{e})$-factor
approximation algorithm and an online algorithm with the competitive ratio
$\frac{1}{4}$. Recent research has also explored various spatial properties
for developing efficient partition algorithms. Wang et al. (Wong et al., 2009)
focused on finding an optimal region that maximizes the area of the k-nearest
neighbors by intersecting geometric shapes. Similarly, Xia et al. (Xia et al.,
2005) addressed the problem of identifying the most influential places and
introduced a novel pruning technique to eliminate less influential sites.
These studies demonstrate the ongoing efforts to address different aspects of
the Site Selection problem and its variations, considering spatial properties,
influence maximization objectives, and optimization strategies.

###  2.2. Influential Billboard Slot Selection

As mentioned previously, the key problem in billboard advertisement is
selecting a number of influential billboard slots. Several studies on this
problem have been found in the existing literature, and different solutions
have been proposed to address them. Now, in the direction of the influential
billboard selection problem, Zhang et al. (Zhang et al., 2020) studied the
problem of optimizing the impact of billboards on trajectories. The challenge
involves selecting a subset of billboards from a given set, considering their
locations, costs, and budget constraints. This problem is closely related to
our Context Dependent Influential Billboard Slot Selection Problem. However,
our approach aims to maximize influence by choosing a subset of the most
influential billboard slots and a subset of the most influential tags within
the specified budget. This type of subset selection problem shares
similarities with the maximum coverage problem studied by Kuller et al.
(Khuller et al., 1999) where each element in the subset incurs a cost, and the
objective is to maximize coverage within the budget constraints. However, it
has been demonstrated that the standard incremental Greedy algorithm is
inefficient for this problem due to the high computational cost. To address
this limitation, a modified version of the greedy approach was introduced,
which achieves an approximation ratio of $(1-\frac{1}{e})$. Another related
study by Wang et al.(Wang et al., 2022) focuses on the Targeted Outdoor
Advertising Recommendation problem, which involves selecting a subset of
billboards within a given budget while considering a targeted influence model
that incorporates user mobility. Their primary contribution lies in developing
two solution strategies, employing a divide-and-conquer approach and
considering user profiles and advertisement topics. In the direction of
influential billboard slot selection, Ali et al. (Ali et al., 2022) studied
the problem and formulated this as a discrete optimization problem. They
introduced a pruned submodularity graph-based solution approach, which leads
to an approximation ratio of $(1-\frac{1}{e}).(I(S^{OPT})-2k\epsilon)$.
Furthermore, they have introduced spatial clustering-based (Ali et al., 2023)
solutions to reduce the computational costs while maintaining the influence
quality.

###  2.3. Trajectory Driven Influence Maximization

Now, in the past few years, maximization of influence over trajectories is
proven to be an efficient technique and to illustrate it, Guo et al. (Guo et
al., 2017) studied a problem in which they aimed to find the best routes that
are associated with specific ads to maximize their influence on target
audiences. Another study by Zhang et al. (Zhang et al., 2019) focused on
finding a set of highly influential billboards that attract more people’s
attention within certain budget constraints. They introduced an algorithm
based on tangent lines to estimate the upper limit of billboard influence and
reduce computational costs using a termination method based on a user-defined
parameter $\theta$. Their approach achieved an approximation ratio of
$\frac{\theta}{2}(1-\frac{1}{e})$. More recently, Wang et al. (Wang et al.,
2018) studied a new type of query called RkNNT, which estimates route capacity
and planning by considering user information, such as their starting and
ending points from trajectory data. When it comes to outdoor or online
advertising, one of the challenges is selecting the right audience for a
specific advertisement due to a lack of audience profiles. Wang et al. (Wang
et al., 2020) addressed this issue by proposing a divide-and-conquer approach.
Instead of only considering billboards and trajectories, they incorporated
advertisement content, trajectory behavior, and mobility transition to improve
influence delivery from targeted audiences in the outdoor advertising
industry.

###  2.4. Tag-Based Influence Maximization problem

No study on tag-specific influence maximization has been done in the context
of billboard advertisement exists. However, some studies exist on tag-specific
influence maximization problems in social networks. The closest to our study
is the study by Ke et al. (Ke et al., 2018) They addressed the problem of
selecting Top-$k$ influential users and Top-$\ell$ influential tags to
maximize the influence. Their solution methodology relies on the maximization
of submodular function and they proposed a reverse rechable set-based approach
for this problem. However, the proposed solution approaches are deeply rooted
at the bi-submodular function and its maximization. There are many other
studies on tag-based influence maximization. However, they are all in the
context of social network analysis and fundamentally different from these
studies (Tekawade and Banerjee, 2023; Banerjee et al., 2020).

##  3\. Background and Problem Definition

This section describes the background concepts and formally defines our
problem.

###  3.1. Trajectory and Billboard Database

A trajectory database contains location information of a set of moving objects
over time. In this problem context, the trajectory database $\mathcal{D}$
contains tuples of the form
$(\mathcal{U}^{{}^{\prime}},\texttt{loc},[t_{1},t_{2}])$ which signifies that
the set of people $\mathcal{U}^{{}^{\prime}}$ were at the location loc for the
duration $[t_{1},t_{2}]$. $m$ denotes the number of tuples of the database
$\mathcal{D}$. For any tuple $t\in\mathcal{D}$, let $t_{u}$ denote the set of
people associated with it. Let $\mathcal{U}=\\{u_{1},u_{2},\ldots,u_{n}\\}$
denotes the set of people covered by the trajectory database, hence
$\mathcal{U}=\underset{t\in\mathcal{D}}{\bigcup}t_{u}$. This is defined as the
people for which there exists at least one tuple which contains the people,
i.e.,
$\mathcal{U}=\\{u_{i}:\exists(\mathcal{U}^{{}^{\prime}},\texttt{loc},[t_{1},t_{2}])\in\mathcal{D}\texttt{
and }u_{i}\in\mathcal{U}^{{}^{\prime}}\\}$. Similar way, $\mathcal{L}$ denotes
the set of locations that are covered by the trajectory database
$\mathcal{D}$, i.e.,
$\mathcal{L}=\\{\texttt{loc}_{i}:(\mathcal{U}^{{}^{\prime}},\texttt{loc}_{i},[t_{j},t_{k}])\in\mathcal{D}\\}$.
Let $[T_{1},T_{2}]$ be the duration for which the trajectory database
$\mathcal{D}$ contains the movement data. This means for every tuple
$t\in\mathcal{D}$, the associated interval
$[t_{i},t_{j}]\subseteq[T_{1},T_{2}]$.

A billboard database $\mathcal{B}$ contains information about different
billboards placed across a city. This database contains the tuple of the form
$(b_{id},\texttt{loc},\texttt{slot\\_duration},\texttt{cost})$, where $b_{id}$
denotes the billboard id, loc denotes the location, slot_duration attribute
contains the duration of each slot for this billboard and its associated cost
etc. The set of billboards covered in the billboard database is
$B=\\{b_{1},b_{2},\ldots,b_{m}\\}$. In the billboard advertisement technique,
an E-Commerce house selects a number of billboard slots (which is dependent on
the budget), and advertisement content (e.g., video, animation, etc.) is
played with the hope that the persons nearby may look into the content and
influenced to it with a certain probability. In the billboard advertisement
problem, the key computational problem addressed in the literature is that for
a given value $k$, which $k$ slots should be chosen to maximize the influence.
In this problem context, every billboard database is associated with a
trajectory database. It makes sense to consider the billboards such that at
least one entry in the trajectory database exists in which the loc is the same
as the location in which the billboard is placed.

###  3.2. Influence Probability

As mentioned previously, once a person sees the advertisement content running
on the billboard, he/she might be influenced by the brand with a certain
probability. It has been assumed in the literature that this probability is
fixed and does not depend on the context. However, in practice, advertisements
are always context-dependent. To explain it further, consider the case of
movie promotion. In this context, showing the advertisement content to someone
unfamiliar with this kind of movie makes no sense. Hence, to make an
advertisement effective, it must be targeted in nature, which means the
observers have to have some inclination towards the advertisement content. In
this paper, we formalize the notion of context through hashtags. Consider
$\mathcal{H}_{u_{i}}$ the set of tags associated with the person $u_{i}$.
Considering all the users in $\mathcal{U}$, the set of tags that are relevant
as a whole is denoted by
$\mathcal{H}=\underset{u_{i}\in\mathcal{U}}{\bigcup}\mathcal{H}_{u_{i}}$. So
for every $h\in\mathcal{H}$ and for every $u\in\mathcal{U}$, $Pr(u|h)$ denotes
the influence probability, and this can be interpreted as the conditional
probability. If the tag $h$ is used as the advertisement content, then the
probability that the person $u$ is influenced will be $Pr(u|h)$.

###  3.3. Influence Function

Recently, billboards have been digital and allocated slot-wise on a payment
basis. Consider all the billboards under consideration are running for the
duration $[T_{1},T_{2}]$, and for each billboard, the slot duration is
$\Delta$. A billboard slot is a tuple consisting of the billboard id and the
duration. We denote the set of all billboard slots as $\mathcal{BS}$ and
$\mathcal{BS}=\\{(b_{i},[t_{j},t_{j}+\Delta]):i\in[m]\text{ and
}t_{j}\in\\{1,\Delta+1,2\Delta+1,\ldots,T_{2}-\Delta+1\\}\\}$. In billboard
advertisement, billboards are owned by an influence provider (e.g., Lamar),
and commercial houses approach the influence provider for a number of
billboard slots to maximize the influence of their product. Naturally, the
question arises: how can we quantify the influence of a given set of billboard
slots? We state this in Definition 3.1.

###### Definition 3.1 (Influence of Billboard Slots).

Given a subset of billboard slots $\mathcal{S}\subseteq\mathcal{BS}$, its
aggregated influence probability is denoted by $\phi(\mathcal{S})$ and defined
by Equation No. 1.

(1)
$\phi(\mathcal{S})=\underset{u\in\mathcal{U}}{\sum}1-\underset{t\in\mathcal{D}\wedge
u\in t_{u}}{\prod}\underset{b\in\mathcal{BS}}{\prod}(1-Pr(u,b))$

Here, $\phi$ is the influence function that maps each subset of the billboard
slots to its expected influence, hence
$\phi:2^{\mathcal{BS}}\longrightarrow\mathbb{R}_{0}^{+}$ and
$\phi(\emptyset)=0$. The influence model stated in Definition 3.1 has been
widely accepted in the literature and most of the existing studies on
billboard advertisement. However, as mentioned previously, if the
advertisements need to be effective, the context is very important, and in
that case, the influence model mentioned in Definition 3.1 can not be applied
directly. In this direction, first define the context-dependent influence
probability of a person. Consider a subset of tags
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ is used for the advertisement
purpose. For any person $u\in\mathcal{U}$, the influence probability for the
given set of tags $\mathcal{H}^{{}^{\prime}}$ is denoted by
$Pr(u|\mathcal{H}^{{}^{\prime}})$ and defined in Definition 3.2.

###### Definition 3.2 (Context Dependent Influence Probability).

Given a subset of tags $\mathcal{H}^{{}^{\prime}}$, for any person
$u\in\mathcal{U}$, the context-dependent influence probability
$Pr(u|\mathcal{H}^{{}^{\prime}})$ can be defined by Equation No. 2.

(2)
$Pr(u|\mathcal{H}^{{}^{\prime}})=1-\underset{h\in\mathcal{H}^{{}^{\prime}}}{\prod}(1-Pr(u|h))$

Now, using the definition 3.2, we define the context-dependent influence for a
given subset of billboard slots in the Definition 3.3.

###### Definition 3.3 (Context Dependent Influence of Billboard Slots).

Given a subset of billboard slots $\mathcal{S}\subseteq\mathcal{BS}$ and a
subset of tags $\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$, the context
dependent influence of $\mathcal{S}$ is denoted by
$\phi(\mathcal{S}|\mathcal{H}^{{}^{\prime}})$ and defined using Equation No.
3.

(3)
$\phi(\mathcal{S}|\mathcal{H}^{{}^{\prime}})=\underset{u\in\mathcal{U}}{\sum}1-\underset{t\in\mathcal{D}\wedge
u\in
t_{u}}{\prod}\underset{b\in\mathcal{BS}}{\prod}(1-Pr(u,b|\mathcal{H}^{{}^{\prime}}))$

In Equation No. 3, for any person $u\in\mathcal{U}$, the value of
$Pr(u|\mathcal{H}^{{}^{\prime}})$ can be computed using Equation No. 3. Here,
$\phi()$ is the combined influence function that maps each subset of slots and
a subset of tags combination to its corresponding influence, i.e.,
$\phi:2^{\mathcal{BS}}\times
2^{\mathcal{H}}\longrightarrow\mathbb{R}^{+}_{0}$. From this equation, it can
be observed that the influence depends on the parameters of which slots are
chosen and which tags are used in the advertisement.

###  3.4. Problem Definition

As mentioned in Section 3.3, selecting both tags and billboard slots
effectively is important. Also, it is easy to follow that more slots and tags
will lead to more influence. However, as mentioned previously, obtaining a
required billboard slot from an influence provider is subject to payment.
Also, creating advertisement content based on a tag is also budget-consuming.
The E-Commerce house that is doing this advertisement will have budget
constraints. So, the goal here is to select $k$ many billboard slots and
$\ell$ many tags to maximize the influence defined in Definition 3.3. We call
this problem the Context Dependent Influential Billboard Slot Selection
Problem, which asks for given $k$ and $\ell$ which $k$ influential slots and
tags should be chosen respectively to maximize the influence. We formally
state the problem in Definition 3.4.

###### Definition 3.4 (Context Dependent Influential Billboard Slot Selection
Problem).

Given a trajectory database $\mathcal{D}$, a billboard database $\mathcal{B}$,
and two positive integers $k$ and $\ell$, this problem asks to choose $k$
influential billboard slots and $\ell$ influential tags such that the
influence is maximized. Mathematically, this problem can be expressed as
follows:

(4)
$(\mathcal{S}^{OPT},\mathcal{H}^{OPT})\longleftarrow\underset{\mathcal{S}\subseteq\mathcal{BS}\wedge\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}}{argmax}\
\phi(\mathcal{S}|\mathcal{H}^{{}^{\prime}})$

It is reasonable to consider that even if there is no tag, some default tag
$h^{{}^{\prime}}$ still exists, which can be used even if no tag is selected.
We want to select $\ell$ many tags on the top of the default tag. In Equation
No. 4, $\mathcal{S}^{OPT}$ and $\mathcal{H}^{OPT}$ denotes $k$-sized optimal
slot subset and $\ell$-sized optimal tag subset. It can be easily observed
that the problem introduced in Definition 3.4 is the generalization of the
Influential Billboard Slot Selection Problem (Ali et al., 2023) where the
context-dependent influence probability has not been considered. Hence, the
hardness result of the second problem continues to hold for the first problem
as well. So Theorem 3.5 holds.

###### Theorem 3.5.

For a given $k$ and $\ell$, finding the optimal slot and tag set for the
Context-Dependent Influential Billboard Slot Selection Problem is NP-hard.

Suppose the Problem 3.4 is solved, and we obtain a $k$ size slot subset and
$\ell$ size tag subset. Let them be $\mathcal{S}$ and
$\mathcal{H}^{{}^{\prime}}$. This essentially means that if the slots in
$\mathcal{S}$ are chosen, then it is meaningful to select the tags in
$\mathcal{H}^{{}^{\prime}}$ or vice versa. Still, the problem is not solved on
the ground because we must also report which tag will be displayed in which
slot. This question leads us to the second problem, which is as follows:
“Given a set of slots $\mathcal{S}$ and tags $\mathcal{H}^{{}^{\prime}}$ which
tag is to be displayed in which slot such that the influence is maximized.” We
formally call this problem the Tag Allocation Problem stated in Definition
3.6.

###### Definition 3.6 (Tag Allocation Problem).

Given a trajectory database $\mathcal{D}$, a billboard database $\mathcal{B}$,
a slot and tag subset $\mathcal{S}$ and $\mathcal{H}^{{}^{\prime}}$,
respectively the tag allocation problem asks to assign each slot to a tag such
that the influence is maximized.

This problem returns a boolean matrix $\mathcal{X}$ is of $k\times\ell$ whose
$(i,j)$-th entry will be $1$ if the $j$-th tag is allocated to the $i$-th slot
and $0$ otherwise. As the influence is dependent on both slots and tags, in
the rest of the paper, we write the influence function as
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$ though its interpretation
remains the same.

###  3.5. An Illustrative Example

Now, we present our problem with the help of an illustrative example. This
illustration has been used as a running example and referred to many times
subsequently. Figure 1 contains information about the trajectory database,
billboard database, and the context-specific influence probability. In this
problem instance, the set of persons
$\mathcal{U}=\\{u_{1},u_{2},\ldots,u_{7}\\}$, the set of locations
$\mathcal{L}=\\{x_{1},x_{2},x_{3},x_{4}\\}$, the set of billboards
$\mathcal{B}=\\{b_{1},b_{2},\ldots,b_{7}\\}$. Also, five different contexts
are abstracted using the tags $\mathcal{H}=\\{h_{1},h_{2},\ldots,h_{5}\\}$.
The third table contains the tag-specific influence probabilities for each
user. There must be thirty-five entries as there are seven users and five
tags. However, for the user-tag combinations whose entry is not present in the
table (e.g., $(u_{1},h_{3})$, $(u_{7},h_{5})$, etc.), denotes the
corresponding influence probability is $0$. Also, consider that all the
billboards are running for the time duration $[1,10]$. Assume that the
duration of each advertisement slot is $2$ (i.e., $\Delta=2$). Hence, there
are thirty-five slots in total. In our example, $k=4$ and $\ell=2$.

Figure 1. Figure used in the Running Example

###  3.6. Set Function and Its Properties

A set function is defined as a mapping from all possible subsets of a _ground
set_ (say $\mathcal{X}=\\{x_{1},x_{2},\ldots,x_{n}\\}$) to a positive real
number including $0$, i.e.,
$f:2^{\mathcal{X}}\longrightarrow\mathbb{R}^{0}_{+}$. A set function is said
to be normalized if $f(\emptyset)=0$. There are several properties of the set
function that can be exploited to design efficient algorithms for optimization
problems. The properties that are of interest are _non-negativity_ ,
_monotonicity_ , and _submodularity_. A set function is said to be non-
negative if for all $\mathcal{X}\subseteq X$, $f(\mathcal{X})\geq 0$. The
function $f()$ is said to be monotone if for all $\mathcal{X}\subseteq X$ and
$x\in X\setminus\mathcal{X}$, $f(\mathcal{X}\cup\\{x\\})\geq(\mathcal{X})$.
The function $f()$ is submodular if for all
$\mathcal{X}_{1}\subseteq\mathcal{X}_{2}\subseteq X$ and for all $x\in
X\setminus\mathcal{X}_{2}$,
$f(\mathcal{X}_{1}\cup\\{x\\})-f(\mathcal{X}_{1})\geq
f(\mathcal{X}_{2}\cup\\{x\\})-f(\mathcal{X}_{2})$. In recent times, the study
of the biset function has also emerged, and it can be observed that the
influence function $\phi()$ as defined in Equation No. 3 is also a biset
function where the ground sets are the set of billboard slots $\mathcal{BS}$
and the set of tags $\mathcal{H}$. Similarly, for biset functions as well, a
few properties are of interest in this paper, and they are defined
subsequently.

###### Definition 3.7 (Non-Negativity of a Biset function).

Given a biset function $\phi(.,.)$ defined on the $\mathcal{BS}$ and
$\mathcal{H}$ is said to be non-negative if for all
$\mathcal{S}\subseteq\mathcal{BS}$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$,
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})\geq 0$.

###### Definition 3.8 (Bi-Monotonicity of a Biset function).

Given a biset function $\phi(.,.)$ defined on the $\mathcal{BS}$ and
$\mathcal{H}$ is said to have the bi-monotonicity property if for all
$\mathcal{S}\subseteq\mathcal{BS}$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ the following two holds:

  * •

For all $s\in\mathcal{BS}\setminus\mathcal{S}$,
$\phi(\mathcal{S}\cup\\{s\\},\mathcal{H}^{{}^{\prime}})\geq\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$.

  * •

For all $h\in\mathcal{H}\setminus\mathcal{H}^{{}^{\prime}}$,
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}}\cup\\{h\\})\geq\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$.

###### Definition 3.9 (Bi-Submodularity of a Biset function).

Given a biset function $\phi(.,.)$ defined on the $\mathcal{BS}$ and
$\mathcal{H}$ is said to have the bi-submodularity property if the following
two conditions hold.

  * •

For all $\mathcal{S}_{1}\subseteq\mathcal{S}_{2}\subseteq\mathcal{BS}$, for
all $s\in\mathcal{BS}\setminus\mathcal{S}_{2}$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$,
$\phi(\mathcal{S}_{1}\cup\\{s\\},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}_{1},\mathcal{H}^{{}^{\prime}})\geq\phi(\mathcal{S}_{2}\cup\\{s\\},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}_{2},\mathcal{H}^{{}^{\prime}})$.

  * •

For all $\mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\mathcal{H}$, for all
$h\in\mathcal{H}\setminus\mathcal{H}_{2}$, and for all
$\mathcal{S}\subseteq\mathcal{BS}$,
$\phi(\mathcal{H}_{1}\cup\\{h\\},\mathcal{S})-\phi(\mathcal{H}_{1},\mathcal{S})\geq\phi(\mathcal{H}_{2}\cup\\{h\\},\mathcal{S})-\phi(\mathcal{H}_{2},\mathcal{S})$.

This property has been exploited to design efficient algorithms subsequently
in this paper. The symbols and notations used in this paper have been
mentioned in Table 1.

Table 1. Symbols and Notations with their Interpretations

Notation |  Description
---|---
$\mathcal{D}$ |  The Trajectory Database
$d$ |  Number of tuples in $\mathcal{D}$
$\mathcal{U}$ |  Set of people covered by $\mathcal{D}$
$t$ |  An arbitrary tuple of $\mathcal{D}$
$t_{u}$ |  The set of users associated with tuple $t$
$\mathcal{L}$ |  Locations covered by the database $\mathcal{D}$
$[T_{1},T_{2}]$ |  Time duration for which the billboards are operating
$\mathcal{B}$ |  The Billboard Database
$a$ |  The number of billboard slots, i.e., $|\mathcal{BS}|=a$
$m$ |  The number of billboards
$\Delta$ |  Slot duration
$\mathcal{BS}$ |  The set of billboard slots
$\mathcal{H}$ |  The set of tags under consideration
$b$ |  The number of tags, i.e., $|\mathcal{H}|=b$
$\mathcal{H}_{u_{i}}$ |  The set of tags associated with the person $u_{i}$
$\phi(.,.)$ |  The influence function
$k$ |  The number of slots to be chosen
$\ell$ |  The number of tags to be chosen
$\mathcal{S}^{{}^{\prime}},\mathcal{S}^{{}^{\prime\prime}}$ |  $k$-sized Slot Subsets
$\mathcal{H}^{{}^{\prime}},\mathcal{H}^{{}^{\prime\prime}}$ |  $\ell$-sized Tag Subsets
$Pr(u|h)$ |  Influence Probability of the person $u$ for the tag $h$
$Pr(u|\mathcal{H}^{{}^{\prime}})$ |  Influence Probability of the person $u$ for the tags $\mathcal{H}^{{}^{\prime}}$
$\mathcal{S}^{OPT},\mathcal{H}^{OPT}$ |  $k$-sized and $\ell$-sized optimal slot and tag subset
$|\mathcal{X}|$ |  Cardinality of the set $\mathcal{X}$
$[n]$ |  The set $\\{1,2,\ldots,n\\}$
$\mathbb{E}[X]$ |  Expectation of the random variable $X$

##  4\. Proposed Solution Approach

In this section, we describe the proposed solution approaches. Initially, we
establish a few properties of the influence function, which will be used to
design efficient algorithms for solving the problem.

###  4.1. Properties of the Influence Function

###### Lemma 4.1.

The influence function $\phi(.,.)$ is non-negative.

###### Proof.

From the description of $\phi(.,.)$, it can be observed that the value of
$\phi$ will be $0$ only when both $\mathcal{S}=\emptyset$ and
$\mathcal{H}^{{}^{\prime}}=\emptyset$. In any other cases, it is easy to
observe that $\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})>0$. Hence, the
statement is proved. ∎

###### Lemma 4.2.

The influence function $\phi(.,.)$ is monotone to both the orthants.

###### Proof.

Consider, $\mathcal{B}_{1}\subseteq\mathcal{B}_{2}\subseteq\mathcal{BS}$,
$\mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\mathcal{H}$, and
$s\notin\mathcal{B}_{2}$ and $l\notin\mathcal{H}_{2}$. To prove that the
influence function $\phi(.,.)$ is monotonic, we need to show that
$\phi(\mathcal{B}_{1},\mathcal{H}_{1})\leq\phi(\mathcal{B}_{2},\mathcal{H}_{2})$.

Let $\phi_{u}(\mathcal{BS},\mathcal{H})$ be the influence value of set
$\mathcal{BS}$ and $\mathcal{H}$ on user $u$. Then, we can express it as
$\phi(\mathcal{BS,H})=\sum_{u\in\mathcal{U}}\phi_{u}(\mathcal{BS,H})$. Since
the influence function $\phi(\mathcal{BS,H})$ is non-negative for any user
$u$, and the sum of non-negative numbers is always non-negative, we have:

$\displaystyle\phi(\mathcal{B}_{1},{H}_{1})$
$\displaystyle\leq\phi(\mathcal{B}_{1},{H}_{1})+\phi(\mathcal{B}_{2}\setminus{B}_{1},{H}_{2})+\phi(\mathcal{B}_{1},{H}_{2}\setminus
H_{1})$ (5) $\displaystyle\leq\phi(\mathcal{B}_{2},{H}_{2})$

Hence, the influence function is monotonic. ∎

###### Lemma 4.3.

Given a trajectory database $\mathcal{D}$, billboard slots information
$\mathcal{BS}$, and Tag information $\mathcal{H}$, the influence function
$\phi(.,.)$ is bisubmodular.

###### Proof.

Consider, $\mathcal{B}_{1}\subseteq\mathcal{B}_{2}\subseteq\mathcal{BS}$,
$\mathcal{H}_{1}\subseteq\mathcal{H}_{2}\subseteq\mathcal{H}$, and
$s\notin\mathcal{B}_{2}$, $l\notin\mathcal{H}_{2}$. We have to show that
adding the billboard slot $s$ to $\mathcal{B}_{1}$ has a greater impact on the
influence value than adding the same billboard slot to $\mathcal{B}_{2}$.
Similarly, adding tag $l$ to $\mathcal{H}_{1}$ has a greater impact on the
influence value than adding the same billboard slot to $\mathcal{H}_{2}$. Now,
assuming the influence function $\phi(.,.)$ is bisubmodular, we can write:

$\displaystyle\phi(\mathcal{B}_{1}\cup\\{s\\},\mathcal{H}_{1})-\phi(\mathcal{B}_{1},\mathcal{H}_{1})$
$\displaystyle\geq\phi(\mathcal{B}_{2}\cup\\{s\\},\mathcal{H}_{2})-\phi(\mathcal{B}_{2},\mathcal{H}_{2})$

For any, $t\in\mathcal{D}\wedge u\in t_{u}$,
$\mathcal{BS}^{{}^{\prime}}\subseteq\mathcal{BS}$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$, the influence of
$\mathcal{BS}^{{}^{\prime}}$ and $\mathcal{H}^{{}^{\prime}}$ are computed by
Equation 3.

(6)
$pr(t,\mathcal{BS}^{{}^{\prime}}|\mathcal{H}^{{}^{\prime}})=1-\prod_{b_{i}\in\mathcal{BS}^{{}^{\prime}}}(1-pr(t,b_{i}|\mathcal{H}^{{}^{\prime}}))$

Using the above equation in the inequality, we have:

$\displaystyle\prod_{b_{i}\in\mathcal{B}_{1}}(1-pr(t,b_{i}|\mathcal{H}_{1}))-\prod_{b_{i}\in\mathcal{B}_{1}\cup\\{s\\}}(1-pr(t,b_{i}|\mathcal{H}_{1}))$
$\displaystyle\geq\prod_{b_{i}\in\mathcal{B}_{2}}(1-pr(t,b_{i}|\mathcal{H}_{2}))-\prod_{b_{i}\in\mathcal{B}_{2}\cup\\{s\\}}(1-pr(t,b_{i}|\mathcal{H}_{2}))$

This inequality holds; hence, our assumption is correct. Similarly, we can
write:

$\displaystyle\phi(\mathcal{B}_{1},\mathcal{H}_{1}\cup\\{l\\})-\phi(\mathcal{B}_{1},\mathcal{H}_{1})$
$\displaystyle\geq\phi(\mathcal{B}_{2},\mathcal{H}_{2}\cup\\{l\\})-\phi(\mathcal{B}_{2},\mathcal{H}_{2})$

This proves that the function $\phi(.,.)$ is bisubmodular. ∎

###  4.2. Solution Methodology

####  4.2.1. Trivial Approach

This is an exhaustive search approach. In this approach, we enumerate all
$k$-sized subsets of the set of billboard slots and $\ell$-sized subsets of
tags. Considering all the billboards are running for the duration
$[T_{1},T_{2}]$ and the slot duration of $\Delta$ time units, hence the number
of billboard slots will be $\frac{T_{2}-T_{1}+1}{\Delta}\cdot m$. So, the
number $k$-sized subsets will be $\binom{\frac{T_{2}-T_{1}+1}{\Delta}\cdot
m}{k}$ and the number of $\ell$ sized subsets of $\mathcal{H}$ will be
$\binom{|\mathcal{H}|}{\ell}$. Subsequently, we create all possible $k$-sized
slot subset and $\ell$-sized tag subset pairs, and for every possible slot-tag
pair, we compute the influence and choose the one that gives the maximum
influence and returns it as a solution. Algorithm 1 describes this procedure
in the form of pseudocode.

As Algorithm 1 is an exhaustive search approach, it always returns an optimal
solution. Now, we analyze this algorithm to understand its time and space
complexity. Consider $T=T_{2}-T_{1}+1$. The time required for the enumeration
process of slot and tag subsets will be of $\mathcal{O}((\frac{T\cdot
m}{\Delta})^{k})$ and $\mathcal{O}(|\mathcal{H}|^{\ell})$, respectively. In
Algorithm 1, the set $\mathcal{Q}$ contains all $k$-sized slot and
$\ell$-sized tag subset pairs. The rest is to calculate the influence
computation for a given slot-tag pair. For any given $\ell$-sized tag subset,
the computational time requirement to calculate the context-specific influence
probability will be $\mathcal{O}(n\cdot\ell)$ where $n$ is the number of
users. On top of it, for a given $k$-sized slot subset, computing the context-
specific influence will take $\mathcal{O}(n\cdot k)$. Hence, the total time
requirement for execution of Algorithm 1 will be of
$\mathcal{O}(((\frac{T\cdot
m}{\Delta})^{k}+|\mathcal{H}|^{\ell})\cdot(n\cdot\ell+n\cdot k))$. The space
requirement by Algorithm 1 will be to store the set $\mathcal{Q}$ which will
be of $\mathcal{O}((\frac{T\cdot m}{\Delta})^{k}\cdot
k+|\mathcal{H}|^{\ell}\cdot\ell)$. Hence, Theorem 4.4 holds.

###### Theorem 4.4.

The time and space complexity of Algorithm 1 will be of
$\mathcal{O}(((\frac{T\cdot
m}{\Delta})^{k}+|\mathcal{H}|^{\ell})\cdot(n\cdot\ell+n\cdot k))$ and
$\mathcal{O}((\frac{T\cdot m}{\Delta})^{k}\cdot
k+|\mathcal{H}|^{\ell}\cdot\ell)$, respectively.

Data: The Trajectory Database $\mathcal{D}$, The Billboard Database
$\mathcal{B}$, Context Specific Influence Probabilities, Two Positive Integers
$k$ and $\ell$.

Result: $\mathcal{S}\subseteq V(G)$ with $|\mathcal{S}|=k$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ with
$|\mathcal{H}^{{}^{\prime}}|=\ell$ such that
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$ is maximized.

1 $x\longleftarrow\frac{T_{2}-T_{1}+1}{\Delta}\cdot m$;
$y\longleftarrow\binom{\frac{T_{2}-T_{1}+1}{\Delta}\cdot m}{k}$ ;

2 $a\longleftarrow|\mathcal{H}^{{}^{\prime}}|$;
$b\longleftarrow\binom{a}{\ell}$;

3 $\mathcal{Q}\longleftarrow\\{(\mathcal{S}_{i},\mathcal{H}_{j}):i\in[y]\text{
and }j\in[b]\\}$;

4
$(\mathcal{S}^{OPT},\mathcal{H}^{OPT})\longleftarrow\underset{(\mathcal{S}_{i},\mathcal{H}_{j})\in\mathcal{Q}}{argmax}\
\phi(\mathcal{S}_{i},\mathcal{H}_{j})$;

5 $return\ \mathcal{S}^{OPT}\text{ and }\mathcal{H}^{OPT}$;

Algorithm 1 Exhaustive Search Approach for

####  4.2.2. Orthant-Wise Greedy Maximization Algorithm

This section describes an orthant-wise incremental greedy approach to solve
this problem. As mentioned previously, we start with a default slot
$s^{{}^{\prime}}$ and default tag $h^{{}^{\prime}}$, and our approach is as
follows. First, we fix the tag set to $\\{h^{{}^{\prime}}\\}$ and apply an
incremental greedy algorithm that works based on marginal gain computation to
obtain the $k$ size slot set $\mathcal{S}^{{}^{\prime}}$. Now, fixing the slot
set to $\mathcal{S}^{{}^{\prime}}\cup\\{s^{{}^{\prime}}\\}$ , we apply
incremental greedy algorithm to obtain the $\ell$ size tag set
$\mathcal{H}^{{}^{\prime}}$. Next, we do the same thing; however first fix the
slot set to the default slot and apply the incremental greedy algorithm to
choose an $\ell$ size tag set $\mathcal{H}^{{}^{\prime\prime}}$, and then we
fix the tag set to $\mathcal{H}^{{}^{\prime\prime}}\cup\\{h^{{}^{\prime}}\\}$
and apply the incremental greedy algorithm to obtain the $k$ size slot set
$\mathcal{S^{{}^{\prime\prime}}}$. So we have two slot-tag pair
$(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$ and
$(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$. We return
one that leads to the maximum influence. This method consists of the following
four optimization problems.

(7)
$\mathcal{S}^{{}^{\prime}}\longleftarrow\underset{\mathcal{S}\subseteq\mathcal{BS}\wedge|\mathcal{S}|=k}{argmax}\
\phi(\mathcal{S}\cup\\{s^{{}^{\prime}}\\},\\{h^{{}^{\prime}}\\})$ (8)
$\mathcal{H}^{{}^{\prime}}\longleftarrow\underset{H\subseteq\mathcal{H}\wedge|H|=\ell}{argmax}\
\phi(\mathcal{S}^{{}^{\prime}},H\cup\\{h^{{}^{\prime}}\\})$

(9)
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\underset{H\subseteq\mathcal{H}\wedge|H|=\ell}{argmax}\
\phi(\\{s^{{}^{\prime}}\\},H\cup\\{h^{{}^{\prime}}\\})$

(10)
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\underset{\mathcal{S}\subseteq\mathcal{BS}\wedge|\mathcal{S}|=k}{argmax}\
\phi(\mathcal{S}\cup\\{s^{{}^{\prime}}\\},\mathcal{H}^{{}^{\prime\prime}})$

We use Algorithm 2 to solve these optimization problems.

Data: The Trajectory Database $\mathcal{D}$, The Billboard Database
$\mathcal{B}$, Context Specific Influence Probabilities, Two Positive Integers
$k$ and $\ell$.

Result: $\mathcal{S}\subseteq V(G)$ with $|\mathcal{S}|=k$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ with
$|\mathcal{H}^{{}^{\prime}}|=\ell$ such that
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$ is maximized.

1 $\mathcal{S}^{{}^{\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$;

2 for  _$i=1\text{ to }k$_ do

3
$s^{*}\longleftarrow\underset{s\in\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime}}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime}}\cup\\{s\\},\\{h^{{}^{\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

4
$\mathcal{S}^{{}^{\prime}}\longleftarrow\mathcal{S}^{{}^{\prime}}\cup\\{s^{*}\\}$;

5

6for  _$i=1\text{ to }\ell$_ do

7
$h^{*}\longleftarrow\underset{h\in\mathcal{H}\setminus\mathcal{H}^{{}^{\prime}}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}\cup\\{h\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

8
$\mathcal{H}^{{}^{\prime}}\longleftarrow\mathcal{H}^{{}^{\prime}}\cup\\{h^{*}\\}$;

9

10

11for  _$i=1\text{ to }\ell$_ do

12
$h^{*}\longleftarrow\underset{h\in\mathcal{H}\setminus\mathcal{H}^{{}^{\prime\prime}}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}}\cup\\{h\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

13
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\mathcal{H}^{{}^{\prime\prime}}\cup\\{h^{*}\\}$;

14

15

16for  _$i=1\text{ to }k$_ do

17
$s^{*}\longleftarrow\underset{s\in\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime\prime}}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime\prime}}\cup\\{s\\},\mathcal{H}^{{}^{\prime\prime}})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

18
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\mathcal{S}^{{}^{\prime\prime}}\cup\\{s^{*}\\}$;

19

20if  _$\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})
>\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$_ then

21 $return\ \mathcal{S}^{{}^{\prime}}\text{ and }\mathcal{H}^{{}^{\prime}}$;

22

23else

24 $return\ \mathcal{S}^{{}^{\prime\prime}}\text{ and
}\mathcal{H}^{{}^{\prime\prime}}$

Algorithm 2 Orthant-Wise Incremental Greedy Algorithm for the Influential
Slots and Tags Selection Problem

Complexity Analysis. Now, we analyze Algorithm 2 to understand its time and
space complexity and performance guarantee. There are four looping structures
where the first and fourth will execute $\mathcal{O}(k)$ times, whereas the
second and third will execute $\mathcal{O}(\ell)$ times. If we analyze one of
them, the remaining three are done. Now, for any billboard slot
$s\in\mathcal{BS}$ and tag $\ell\in\mathcal{H}$, computing influence using
equation 3 will take $\mathcal{O}(t)$, where $t$ is the number of tuple in the
trajectory database. For the first for loop, the number of times marginal gain
is computed is of $\mathcal{O}(k)$. It is easy to observe that in each
marginal gain computation, the required computational time will be
$\mathcal{O}(2.k.t)$. So, total marginal gain computation for
$|\mathcal{BS}|=n$ will be $\mathcal{O}(2.k.n.t)$. Now, in the worst case for
total $k$ many iteration Line No. $2$ to $4$ will take
$\mathcal{O}(2.k^{2}.n.t)$ time. In the similar way, Line No. $5$ to $7$ each
marginal gain computation takes $\mathcal{O}(2.k.t.\ell)$ and the total
marginal gain computation takes $\mathcal{O}(2.k.t.\ell.m)$, where
$|\mathcal{H}|=m$ and $\ell$ will be upper limit of tags considered. The for
loop iterates for $\ell$ times. So, the total time requirement will be
$\mathcal{O}(2.k.t.\ell^{2}.m)$. In the third greedy, Line No. $8$ to $10$,
each marginal gain computation takes $\mathcal{O}(2.t.\ell)$. So, total
marginal gain computation will take $\mathcal{O}(2.t.\ell.m)$, where
$|\mathcal{H}|=m$ and as the for loop iterates $\ell$ times, total time
requirement will be $\mathcal{O}(2.t.\ell^{2}.m)$. Now, in Line No. $11$ to
$13$, each marginal gain computation will take $\mathcal{O}(2.t.k.\ell)$ and
total marginal gain computation for $n$ number of billboard slots will be
$\mathcal{O}(2.t.k.\ell.n)$. Again, for loop will execute for $k$ times. So,
total marginal gain computation require $\mathcal{O}(2.t.k^{2}.\ell.n)$ time.
Finally, Line No. $14$ to $17$ will take $\mathcal{O}(2.k.\ell.t)$ time.
Hence, the total time requirement for Algorithm 2 will be of
$\mathcal{O}(2.k^{2}.n.t+2.k.t.\ell^{2}.m+2.t.\ell^{2}.m+2.t.k^{2}.\ell.n+2.k.\ell.t)$.
As, $k<<n$ and $\ell<<m$, the reduced quantity will be
$\mathcal{O}(k.m.t+n.\ell.t)$. Additional space required to store the lists
$\mathcal{S}^{{}^{\prime}},\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime}}$
and $\mathcal{H}^{{}^{\prime\prime}}$ will be
$\mathcal{O}(k),\mathcal{O}(k),\mathcal{O}(\ell)$ and $\mathcal{O}(\ell)$
respectively. Hence, the total extra space requirement for Algorithm 2 will be
of $\mathcal{O}(2k+2\ell)$.

Though the incremental greedy algorithm gives a constant factor approximation
guarantee, also simple to understand and easy to implement, it takes huge
computational time, as we have observed in our experiments. This is primarily
because of the excessive number of marginal gain computations. To address this
problem, we propose a stochastic greedy algorithm that works much faster
without degrading the quality of the solution very much.

####  4.2.3. Lazy Greedy Algorithm

As mentioned previously, due to the excessive number of influence function
evaluations, the execution time is very high. However, this algorithm can be
implemented efficiently where, in all practical situations, the number of
influence function evaluations will be much less, though in the worst case,
the number of evaluations can be as much as incremental greedy. The key idea
is to Consider the first for loop and its first iteration. We compute the
marginal gain for all the slots with respect to the empty set, which is
equivalent to computing their influence value. Subsequently, we sort the slots
based on this value in descending order, and the first slot is chosen. Now, in
the second iteration, we compute the marginal gain of the slots in the sorted
order and consider the following situation. Suppose the marginal gain of the
$i$-th slot is lesser than that of the $(i+1)$-th slot. Now, applying the
submodularity property, it can be ensured that even if we compute the marginal
gain of the slots, it can not be more than the marginal gain of the $i$-th
slot. Hence, from the $(i+1)$-th slot on words, there is no need to compute
their marginal gains, and they can be skipped safely. This leads to
significant improvement in execution time, though the worst-case time
complexity will remain the same. Algorithm 3 describes this procedure in the
form of pseudocode.

Data: The Trajectory Database $\mathcal{D}$, The Billboard Database
$\mathcal{B}$, Context Specific Influence Probabilities, Two Positive Integers
$k$ and $\ell$.

Result: $\mathcal{S}\subseteq V(G)$ with $|\mathcal{S}|=k$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ with
$|\mathcal{H}^{{}^{\prime}}|=\ell$ such that
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$ is maximized.

1 $\mathcal{S}^{{}^{\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$;

2 $\text{Initialize an empty sorted list},\mathcal{Q}=[~{}]$;

3 for  _$\text{each u}\in\mathcal{BS}$_ do

4 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime}}\cup\\{u\\},\\{h^{{}^{\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

5 $\text{Add u to}\ \mathcal{Q}\ \text{by u.mg in descending order}$;

6

7while  _$|\mathcal{S}^{{}^{\prime}}|\neq k$ _ do

8 $u=\mathcal{Q}[top]$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

9 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime}}\cup\\{u\\},\\{h^{{}^{\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

10 $\mathcal{Q}\longleftarrow\mathcal{Q}\cup\\{u\\}$;

11 if  _$\mathcal{Q}[top]=u$_ then

12
$\mathcal{S}^{{}^{\prime}}\longleftarrow\mathcal{S}^{{}^{\prime}}\cup\\{u\\}$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

13

14

15

16$\mathcal{Q}=[~{}]$;

17 for  _$\text{each u}\in\mathcal{H}$_ do

18 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}\cup\\{u\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

19 $\text{Add u to}\ \mathcal{Q}\ \text{by u.mg in descending order}$;

20

21

22while  _$|\mathcal{H}^{{}^{\prime}}|\neq\ell$ _ do

23 $u=\mathcal{Q}[top]$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

24 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}\cup\\{u\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

25 $\mathcal{Q}\longleftarrow\mathcal{Q}\cup\\{u\\}$;

26 if  _$\mathcal{Q}[top]=u$_ then

27
$\mathcal{H}^{{}^{\prime}}\longleftarrow\mathcal{H}^{{}^{\prime}}\cup\\{u\\}$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

28

29

30

31$\mathcal{Q}=[~{}]$;

32 for  _$\text{each u}\in\mathcal{H}$_ do

33 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}}\cup\\{u\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

34 $\text{Add u to}\ \mathcal{Q}\ \text{by u.mg in descending order}$;

35

36while  _$|\mathcal{H}^{{}^{\prime\prime}}|\neq\ell$ _ do

37 $u=\mathcal{Q}[top]$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

38 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}}\cup\\{u\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

39 $\mathcal{Q}\longleftarrow\mathcal{Q}\cup\\{u\\}$;

40 if  _$\mathcal{Q}[top]=u$_ then

41
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\mathcal{H}^{{}^{\prime\prime}}\cup\\{u\\}$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

42

43

44

45$\mathcal{Q}=[~{}]$;

46 for  _$\text{each u}\in\mathcal{BS}$_ do

47 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime\prime}}\cup\\{u\\},\\{\mathcal{H}^{{}^{\prime\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

48 $\text{Add u to}\ \mathcal{Q}\ \text{by u.mg in descending order}$;

49

50

51while  _$|\mathcal{S}^{{}^{\prime\prime}}|\neq k$ _ do

52 $u=\mathcal{Q}[top]$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

53 $u.mg\longleftarrow\
\phi(\mathcal{S}^{{}^{\prime\prime}}\cup\\{u\\},\\{\mathcal{H}^{{}^{\prime\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

54 $\mathcal{Q}\longleftarrow\mathcal{Q}\cup\\{u\\}$;

55 if  _$\mathcal{Q}[top]=u$_ then

56
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\mathcal{S}^{{}^{\prime\prime}}\cup\\{u\\}$;
$\mathcal{Q}\longleftarrow\mathcal{Q}\setminus\\{u\\}$;

57

58

59if  _$\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})
>\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$_ then

60 $return\ \mathcal{S}^{{}^{\prime}}\text{ and }\mathcal{H}^{{}^{\prime}}$;

61

62else

63 $return\ \mathcal{S}^{{}^{\prime\prime}}\text{ and
}\mathcal{H}^{{}^{\prime\prime}}$

Algorithm 3 Orthant-Wise Lazy Greedy Algorithm for the Influential Slots and
Tags Selection Problem

Complexity Analysis. Now, we analyze the proposed Lazy greedy algorithm and
understand its time and space requirements. Initialization at Line No. $1$ and
$2$ will take $\mathcal{O}(1)$ time. Now, for any billboard slot
$s\in\mathcal{BS}$ and tag $\ell\in\mathcal{H}$, computing influence using
equation 3 will take $\mathcal{O}(t)$, where $t$ is the number of tuple in the
trajectory database. Now, computing marginal gain for all billboard slots will
take $\mathcal{O}(2.n.t)$, where $|\mathcal{BS}|=n$, and sorted list
$\mathcal{Q}$ will take $\mathcal{O}(n.\log n)$ time for sorting. Hence, Line
No. $3$ to $5$ will take $\mathcal{O}({2.n.t+n.\log n})$ time. Now, at Line
No. $7$, deletion of an element will take $\mathcal{O}(\log n)$ time as sorted
list $Q$ is considered as max heap. At Line No. $8$ computing marginal gain
will take $\mathcal{O}(2.k.t)$ as $|\mathcal{S}^{{}^{\prime}}|$, will be $k$
in the worst case. In Line No. $9$ adding an element into $\mathcal{Q}$ will
take $\mathcal{O}(\log n)$ time and Line No. $11$ also take $\mathcal{O}(\log
n)$ time. In the best case, Line No. $6$ to $11$ will take
$\mathcal{O}(3.k.\log n+2.k^{2}.t)$ time. In the worst case, the time
requirement will be $\mathcal{O}(2.n.\log n+2.n.k.t+k.\log n)$. As $k<<n$, the
reduced quantity for best case and worst case will be $\mathcal{O}(k.\log
n+k^{2}.t)$ and $\mathcal{O}(n.\log n+n.k.t)$ respectively. So, the first
greedy in the Line No. $2$ to $11$ will take $\mathcal{O}(2.n.t+2.n.\log
n+n.k.t)$ i.e., $\mathcal{O}(n.t+n.\log n)$ time in the worst case. Now, Line
No. $12$ to $15$ will take $\mathcal{O}(2.m.k.t+m.\log m)$ time where
$|\mathcal{H}|=m$, and Line No. $16$ to $21$ will take
$\mathcal{O}(3.\ell.\log m+2.k.\ell^{2}.t)$ time in best case. In the worst
case, time requirement will be $\mathcal{O}(2.m.\log m+2.m.k.\ell.t+\ell.\log
m)$, and as $\ell<<m$, the reduced quantity will be $\mathcal{O}(m.\log
m+m.k.t)$. So the second greedy from Line No. $12$ to $21$ will take
$\mathcal{O}(2.m.t.k+m.\log m+m.\log m+m.k.t)$ i.e., $\mathcal{O}(m.\log
m+m.k.t)$ time in the worst case. In the third greedy Line No. $22$ to $25$
will take $\mathcal{O}(2.m.t+m.\log m)$ and From Line No. $26$ to $31$ will
take $\mathcal{O}(3.\ell.\log m+2.\ell^{2}.t)$ in the best case scenario. Now,
in the worst case, it will take $\mathcal{O}(2.m.\log m+2.m.\ell.t+\ell.\log
m)$ time. Hence, Line No. $22$ to $31$ will take $\mathcal{O}(2.m.t+m.\log
m+2.m.\log m+2.m.\ell.t+\ell.\log m)$ i.e., $\mathcal{O}(m.\log m+m.t)$ time.
Now, in Line No. $32$ to $35$ will take $\mathcal{O}(2.n.k.\ell.t+n.\log n)$
time and Line No. $36$ to $41$ will take $\mathcal{O}(3.k.\log
n+2.k^{2}.\ell.t)$ time when best case occurs. But, in the worst case, it will
take $\mathcal{O}(2.n.\log n+2.n.k.\ell.t+k.\log n)$ time. Hence, Line No.
$32$ to $41$ will take $\mathcal{O}(2.n.k.\ell.t+n.\log n+2.n.\log
n+2.n.k.\ell.t+k.\log n)$ i.e., $\mathcal{O}(n.\log n+n.\ell.t)$ time.
Finally, Line No. $42$ to $45$ will take $\mathcal{O}(2.k.\ell.t)$ time.
Hence, the time total time requirement for Algorithm 3 will be of
$\mathcal{O}(n.t+n.\log n+m.\log m+m.k.t+m.\log m+m.t+n.\log
n+n.\ell.t+2.k.\ell.t)$. As, $k<<n$ and $\ell<<m$ the reduced quantity will be
of $\mathcal{O}(n.t+n.\log n+m.\log m+m.t+k.\ell.t)$.

Now, the additional space requirement to store the lists
$\mathcal{S}^{{}^{\prime}},\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime}}$,
$\mathcal{H}^{{}^{\prime\prime}}$ and $\mathcal{Q}$ will be
$\mathcal{O}(k),\mathcal{O}(k),\mathcal{O}(\ell)$, $\mathcal{O}(\ell)$ and
$\mathcal{O}(max(n,m))$ respectively. As, in our experiment we have considered
$m<<n$, the total space complexity will be of $\mathcal{O}(n+2k+2\ell)$, i.e.,
$\mathcal{O}(n)$.

####  4.2.4. Stochastic Greedy Algorithm

In this approach in every iteration instead of computing the marginal gains of
all the remaining elements, we sample out $\frac{n}{k}\log\frac{1}{\epsilon}$
many elements from the ground set for slot selection and
$\frac{n}{\ell}\log\frac{1}{\epsilon}$ many elements for tag selection.
Marginal gain is computed only for the sampled elements only. Here, we mention
that $\epsilon$ is a control parameter that controls the trade-off between the
quality of the solution and the execution time. Algorithm 4 describes this
process as pseudocode.

Data: The Trajectory Database $\mathcal{D}$, The Billboard Database
$\mathcal{B}$, Context Specific Influence Probabilities, Two Positive Integers
$k$ and $\ell$.

Result: $\mathcal{S}\subseteq V(G)$ with $|\mathcal{S}|=k$ and
$\mathcal{H}^{{}^{\prime}}\subseteq\mathcal{H}$ with
$|\mathcal{H}^{{}^{\prime}}|=\ell$ such that
$\phi(\mathcal{S},\mathcal{H}^{{}^{\prime}})$ is maximized.

1 $\mathcal{S}^{{}^{\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\\{s^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$,
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\\{h^{{}^{\prime}}\\}$;

2 $\mathcal{R}\longleftarrow\emptyset$, $\epsilon\longleftarrow 0.01$;

3 for  _$i=1\text{ to }k$_ do

4 $\mathcal{R}\longleftarrow\text{Sample
}\frac{a}{k}\log\frac{1}{\epsilon}\text{ many elements from
}\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime}}$;

5 $s^{*}\longleftarrow\underset{s\in\mathcal{R}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime}}\cup\\{s\\},\\{h^{{}^{\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

6
$\mathcal{S}^{{}^{\prime}}\longleftarrow\mathcal{S}^{{}^{\prime}}\cup\\{s^{*}\\}$;

7

8for  _$i=1\text{ to }\ell$_ do

9 $\mathcal{R}\longleftarrow\text{Sample
}\frac{b}{\ell}\log\frac{1}{\epsilon}\text{ many elements from
}\mathcal{H}\setminus\mathcal{H}^{{}^{\prime}}$;

10 $h^{*}\longleftarrow\underset{h\in\mathcal{R}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}\cup\\{h\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$;

11
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\mathcal{H}^{{}^{\prime\prime}}\cup\\{h^{*}\\}$;

12

13

14for  _$i=1\text{ to }\ell$_ do

15 $\mathcal{R}\longleftarrow\text{Sample
}\frac{b}{\ell}\log\frac{1}{\epsilon}\text{ many elements from
}\mathcal{H}\setminus\mathcal{H}^{{}^{\prime\prime}}$;

16 $h^{*}\longleftarrow\underset{h\in\mathcal{R}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}}\cup\\{h\\})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

17
$\mathcal{H}^{{}^{\prime\prime}}\longleftarrow\mathcal{H}^{{}^{\prime\prime}}\cup\\{h^{*}\\}$;

18

19

20for  _$i=1\text{ to }k$_ do

21 $\mathcal{R}\longleftarrow\text{Sample
}\frac{a}{k}\log\frac{1}{\epsilon}\text{ many elements from
}\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime\prime}}$;

22 $s^{*}\longleftarrow\underset{s\in\mathcal{R}}{argmax}\
\phi(\mathcal{S}^{{}^{\prime\prime}}\cup\\{s\\},\mathcal{H}^{{}^{\prime\prime}})-\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$;

23
$\mathcal{S}^{{}^{\prime\prime}}\longleftarrow\mathcal{S}^{{}^{\prime\prime}}\cup\\{s^{*}\\}$;

24

25if  _$\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})
>\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}})$_ then

26 $return\ \mathcal{S}^{{}^{\prime}}\text{ and }\mathcal{H}^{{}^{\prime}}$;

27

28else

29 $return\ \mathcal{S}^{{}^{\prime\prime}}\text{ and
}\mathcal{H}^{{}^{\prime\prime}}$

Algorithm 4 Stochastic Greedy Algorithm for the Influential Slots and Tags
Selection Problem

Complexity Analysis. Now, we analyze the time and space requirements for the
Stochastic Greedy Algorithm. Initialization at Line No. $1$ and $2$ will take
$\mathcal{O}(1)$ time. To sample out $\frac{a}{k}\log\frac{1}{\epsilon}$ many
element it will take $\mathcal{O}(\frac{a}{k}\log\frac{1}{\epsilon}.k)$, i.e.,
$\mathcal{O}(a.\log\frac{1}{\epsilon})$ time. Now, for any billboard slot
$s\in\mathcal{BS}$ and $l\in\mathcal{H}$, calculating influence using equation
3 will take $\mathcal{O}(t)$ time, in which $t$ is the number of tuple in the
trajectory database. In Line No. $5$ computing marginal gain will take
$\mathcal{O}(2.k.\frac{a}{k}\log\frac{1}{\epsilon}.t)$, i.e.,
$\mathcal{O}(2.a.\log\frac{1}{\epsilon}.t)$ time and Line No. $6$ will execute
for $\mathcal{O}(k)$ time. So, Line No. $3$ to $6$ will take
$\mathcal{O}(a.\log\frac{1}{\epsilon}+2.a.\log\frac{1}{\epsilon}.t+k)$ time.

Now, in the second greedy, Line No. $8$ will take
$\mathcal{O}(b.\log\frac{1}{\epsilon})$ time. In Line No. $9$ computing
marginal gain will take $\mathcal{O}(2.b.\log\frac{1}{\epsilon}.k.t)$ and in
Line No. $10$ will take $\mathcal{O}(\ell)$ time. Hence, Line No. $7$ to $10$
will take
$\mathcal{O}(b.\log\frac{1}{\epsilon}+2.b.\log\frac{1}{\epsilon}.k.t+\ell)$
time. In the third greedy, Line No. $12$ will take
$\mathcal{O}(b.\log\frac{1}{\epsilon})$ time. In Line No. $13$ computing
marginal gain will take $\mathcal{O}(2.b.\log\frac{1}{\epsilon}.\ell.t)$ time
and Line No. $14$ will take $\mathcal{O}(\ell)$ time. Hence, Line No. $11$ to
$14$ will take
$\mathcal{O}(b.\log\frac{1}{\epsilon}+2.b.\log\frac{1}{\epsilon}.\ell.t+\ell)$.
Similarly, in the fourth greedy, Line No. $16$ will take
$\mathcal{O}(a.\log\frac{1}{\epsilon})$ time. To compute marginal gain, Line
No. $17$ will take $\mathcal{O}(2.a.\log\frac{1}{\epsilon}.\ell.t)$ time and
Line No. $18$ will take $\mathcal{O}(k)$ time. So, Total time taken by Line
No. $15$ to $18$ is of
$\mathcal{O}(a.\log\frac{1}{\epsilon}+2.a.\log\frac{1}{\epsilon}.\ell.t+k)$.
Finally, Line No. $19$ to $22$ will take $\mathcal{O}(2.k.\ell.t)$ time for
final comparison. Hence, Algorithm 4 will take total
$\mathcal{O}(a.\log\frac{1}{\epsilon}+2.a.\log\frac{1}{\epsilon}.t+k+b.\log\frac{1}{\epsilon}+2.b.\log\frac{1}{\epsilon}.k.t+\ell+b.\log\frac{1}{\epsilon}+2.b.\log\frac{1}{\epsilon}.\ell.t+\ell+a.\log\frac{1}{\epsilon}+2.a.\log\frac{1}{\epsilon}.\ell.t+k+2.k.\ell.t)$
time. As, $k<<a$ and $\ell<<b$, the reduced quantity will be of
$\mathcal{O}(a.\log\frac{1}{\epsilon}.\ell.t+b.\log\frac{1}{\epsilon}.k.t+k.\ell.t)$.

Now, the additional space requirement to store the lists
$\mathcal{S}^{{}^{\prime}},\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime}}$,
$\mathcal{H}^{{}^{\prime\prime}}$ and $\mathcal{R}$ will be
$\mathcal{O}(k),\mathcal{O}(k),\mathcal{O}(\ell)$, $\mathcal{O}(\ell)$ and
$\mathcal{O}(max(a.\log\frac{1}{\epsilon},b.\log\frac{1}{\epsilon}))$
respectively. Hence, total space requirement for Algorithm 4 will be of
$\mathcal{O}(max(a.\log\frac{1}{\epsilon},b.\log\frac{1}{\epsilon})+2k+2\ell)$.

Now, we analyze this methodology. Initially, we prove some theoretical
results.

###### Lemma 4.5.

The number of influence function evaluations by Algorithm 4 will be equal to
$4(a+b)\log\frac{1}{\epsilon}$, i.e.,
$\mathcal{O}((a+b)\log\frac{1}{\epsilon})$.

###### Proof.

From the description of Algorithm 4, we can observe that in each iteration of
the first for loop $\frac{a}{k}\log\frac{1}{\epsilon}$ many elements are
sample out. So the number of times the marginal gain is computed is of
$\frac{a}{k}\log\frac{1}{\epsilon}$. In each marginal gain computation, the
number of influence function evaluations is $2$. So, in the first for loop,
the number of influence function evaluations will be equal to $2\times
k\times\frac{a}{k}\log\frac{1}{\epsilon}=2a\log\frac{1}{\epsilon}$. Similarly,
for the execution of the fourth for loop also, the number of influence
function evaluations will be $2a\log\frac{1}{\epsilon}$. As the number of tags
is $b$, it can be observed that for each of the second and third for loops,
the number of influence function evaluations will be
$2b\log\frac{1}{\epsilon}$. In total, the number of influence function
evaluations will be
$4(a+b)\log\frac{1}{\epsilon}=\mathcal{O}((a+b)\log\frac{1}{\epsilon})$. ∎

Here, we want to describe a comparative study regarding the number of
influence function evaluations between Algorithm 2 and 4. For Algorithm 4, it
is $4(a+b)\log\frac{1}{\epsilon}$ and has been stated in Lemma 4.5. Now, we do
the same for Algorithm 2. First, we consider the first for loop. There are $a$
many billboard slots in its first iterations, so the number of marginal gain
computations will be $a$. The second iteration will be $(a-1)$ and so on. As
in each marginal gain computation, the influence function is evaluated two
times; hence, the number of influence function evaluations will be equal to
$2[a+(a-1)+(a-2)+\ldots+(a-(k-1))]=2ka-k(k-1)$. The quantity is the same for
the fourth for loop also. It is easy to convince that for both the second and
third for loop, the number of influence function evaluations will be $2\ell
b-\ell(\ell-1)$. Hence, the total number of influence function evaluations
will be $4(ka+\ell b)-2(k^{2}+\ell^{2}-k-\ell)$. Here, we want to highlight
that It can be observed that the number of influence function evaluations for
the incremental greedy algorithm is dependent on the number of slots and tags
to be selected (i.e., $k$ and $\ell$ value). However, for the stochastic
greedy algorithm, the same is independent of $k$ and $\ell$.

###### Lemma 4.6.

Consider the first for loop of Algorithm 4 and assume that after the execution
of its $i$-th iteration, the solution set is $\mathcal{S}^{{}^{\prime}}_{i}$.
The expected influence gain of Algorithm 4 in the $(i+1)$-th will be at least
$\frac{1-\epsilon}{k}\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\phi(\mathcal{S}^{{}^{\prime}}\cup\\{s^{*}\\},\\{\mathcal{H}^{{}^{\prime}}\\})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$.

###### Proof.

First we estimate the probability that
$\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})\neq\emptyset$.
As mentioned the first for loop, $\mathcal{R}$ consists of
$\frac{a}{k}\log\frac{1}{\epsilon}$ random samples from
$\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime}}$. Hence, the following holds,

$Pr[\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})=\emptyset]=(1-\frac{|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}{|\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime}}|})^{|\mathcal{R}|}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq
e^{-\frac{|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}{|\mathcal{BS}\setminus\mathcal{S}^{{}^{\prime}}|}\cdot|\mathcal{R}|}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq
e^{-\frac{|\mathcal{R}|}{a}\cdot|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}$

Now, we have the following

$Pr[\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})\neq\emptyset]\geq
1-e^{-\frac{|\mathcal{R}|}{a}\cdot|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}$

$\ \ \ \ \ \ \ \ \ \ \
\geq(1-e^{-\frac{k\cdot|\mathcal{R}|}{a}})\cdot\frac{|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}{k}$

It can be observed that $|\mathcal{R}|=\frac{a}{k}\log\frac{1}{\epsilon}$. So
we can rewrite the above quantity as follows:

(11) $\displaystyle
Pr[\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})\neq\emptyset]\geq(1-\epsilon)\cdot\frac{|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}{k}$

In the stochastic greedy algorithm, in each iteration, an element (say
$s^{*}$) is put in the set $\mathcal{S}^{{}^{\prime}}$ from the set
$\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})$ to
maximize the marginal gain value,
$\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$. Now, we
can say $\mathcal{R}$ is equally likely to hold each element from
($\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})$. So, we can obtain,

$\displaystyle
E[\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})]$
$\displaystyle\geq
Pr[\mathcal{R}\cap(\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}})\neq\emptyset]$
$\displaystyle\times\frac{1}{|\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}|}$
$\displaystyle\times\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}).$

Now, from the equation (13), we can conclude that

$\displaystyle
E[\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})]$
$\displaystyle\geq\frac{1-\epsilon}{k}\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$
$\displaystyle\geq\frac{1-\epsilon}{k}\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\phi(\mathcal{S}^{{}^{\prime}}\cup\\{s^{*}\\},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}).$

∎

Now, we prove the approximation ratio of the stochastic greedy algorithm. In
particular, we prove Theorem 4.7.

###### Theorem 4.7.

Let $\mathcal{S}^{OPT}$ and $\mathcal{H}^{OPT}$ be an optimal $k$-sized and an
$\ell$-sized slot and tag set, respectively. Also assume
$\mathcal{S}^{\mathcal{A}}$ and $\mathcal{H}^{\mathcal{A}}$ are the $k$-sized
and an $\ell$-sized slot and tag set returned by Algorithm 4. Then
$\phi(\mathcal{S}^{\mathcal{A}},\mathcal{H}^{\mathcal{A}})\geq(1-\frac{1}{e}-\epsilon)^{2}\cdot\phi(\mathcal{S}^{OPT},\mathcal{H}^{OPT})$.
In other words, Algorithm 4 gives $(1-\frac{1}{e}-\epsilon)^{2}$ factor
approximation guarantee.

###### Proof.

It can be observed that any one of the following two cases may happen. Case I:
$\mathcal{S}^{\mathcal{A}}=\mathcal{S}^{{}^{\prime}}$,
$\mathcal{H}^{\mathcal{A}}=\mathcal{H}^{{}^{\prime}}$ and Case II:
$\mathcal{S}^{\mathcal{A}}=\mathcal{S}^{{}^{\prime\prime}}$,
$\mathcal{H}^{\mathcal{A}}=\mathcal{H}^{{}^{\prime\prime}}$

Let, $\mathcal{S}^{{}^{\prime}}_{i}=\\{s_{1},s_{2},s_{3},\ldots s_{i}\\}$
defines the solutions at each step returns by first For Loop in Algorithm 4
after $i^{th}$ iteration. Now, from the outcomes of lemma 4.6 we can write,

(12) $\displaystyle
E[\Delta(s_{i+1}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}}]\geq\frac{1-\epsilon}{k}\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$

Using the submodularity property, we can obtain,

$\displaystyle\underset{s^{*}\in\mathcal{S}^{OPT}\setminus\mathcal{S}^{{}^{\prime}}}{\sum}\Delta({s}^{*}|\mathcal{S}^{{}^{\prime}},\mathcal{H}^{{}^{\prime}})$
$\displaystyle\geq\Delta(\mathcal{S}^{OPT}|\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})$
$\displaystyle\geq\phi(\mathcal{S}^{OPT},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})$

Now, if we put these results in Equation (14), we get,

$\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime}}_{i+1},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})|\mathcal{S}^{{}^{\prime}}_{i}]$
$\displaystyle\geq\frac{1-\epsilon}{k}\phi(\mathcal{S}^{OPT},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})$

Now, if we take expectation over $\mathcal{S}^{{}^{\prime}}_{i}$, we can
obtain,

$\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime}}_{i+1},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})]=\frac{1-\epsilon}{k}\phi(\mathcal{S}^{OPT},\mathcal{H}^{{}^{\prime}})-\phi(\mathcal{S}^{{}^{\prime}}_{i},\mathcal{H}^{{}^{\prime}})]$

If we apply induction to it,

$\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime}}_{k},\mathcal{H}^{{}^{\prime}}]\geq(1-(1-\frac{1-\epsilon}{k})^{k}).\phi(\mathcal{S}^{OPT},\mathcal{H}^{\mathcal{A}})$
(13)
$\displaystyle\geq(1-\frac{1}{e}-\epsilon).\phi(\mathcal{S}^{OPT},\mathcal{H}^{\mathcal{A}})$

Now, in a similar way, for the second, third, and fourth For Loop, we can
write:

(14) $\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime}}_{k},\mathcal{H}^{{}^{\prime}}_{l}]\geq(1-\frac{1}{e}-\epsilon)^{2}.\phi(\mathcal{S}^{OPT},\mathcal{H}^{OPT})$

(15) $\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime\prime}},\mathcal{H}^{{}^{\prime\prime}}_{l}]\geq(1-\frac{1}{e}-\epsilon).\phi(\mathcal{S}^{\mathcal{A}},\mathcal{H}^{OPT})$

(16) $\displaystyle
E[\phi(\mathcal{S}^{{}^{\prime\prime}}_{k},\mathcal{H}^{{}^{\prime\prime}}_{l}]\geq(1-\frac{1}{e}-\epsilon)^{2}.\phi(\mathcal{S}^{OPT},\mathcal{H}^{OPT})$

∎

##  5\. Experimental Evaluations

This section describes the experimental evaluations of the proposed solution
approaches. Initially, we start by describing the datasets used in our
experiments.

###  5.1. Dataset Description

We use the following two datasets in our experiments. These datasets have been
used in many previous studies on trajectory data analytics (Yang et al., 2015;
Ali et al., 2023; Zhang et al., 2020). The first dataset comprises check-in
records in New York City111https://www.nyc.gov/site/tlc/about/tlc-trip-record-
data.page, collected over approximately ten months, specifically from April
12, 2012, to February 16, 2013. It encompasses a total of 227,428 check-ins.
Each check-in entry includes timestamps, GPS coordinates, and semantic
representation denoted by fine-grained venue categories. The second dataset,
VehDS-LA222https://github.com/Ibtihal-Alablani (Vehicle dataset in the city of
LA), consists of 74,170 samples from 15 streets in Los Angeles. Each sample
within the dataset is associated with several features like street name,
latitude, longitude, timestamp, etc. Billboard datasets are crawled from
LAMAR333http://www..lamar.com/InventoryBrowser, one of the largest billboard
providers globally. This billboard dataset contains user id, venue id,
latitude, longitude, timestamp, panel size, etc. The billboard dataset for New
York City includes 716 billboards, i.e., 1031040 billboard slots, and Los
Angeles contains 1483 billboards, i.e., 2135520 billboard slots.

Observations. In terms of high-influence billboards, New York City (NYC)
surpasses Los Angeles in quantity. The trajectories influenced by these high-
influence billboards in NYC exhibit significant overlap compared to Los
Angeles.

###  5.2. Experimental Setup

The following setup has been adopted to conduct our experiments.

Key Parameters. All the parameters are summarized in Table 2, including the
number of billboard slots $k$ and tags $\ell$ to be picked. The user-defined
parameter $\epsilon$ defines the size of random subsets. The distance
threshold, $\lambda$, determines the maximum distance a billboard can
influence the trajectories. In each experiment, we fixed one parameter value
and varied the other parameter values.

Table 2.  Parameter Settings Parameter |  Values
---|---
$k$ |  $25,50,100,150,200$
$\ell$ |  $10,20,30,40,50$
$\epsilon$ |  $0.01,0.05,0.1,0.15,0.2$
$\lambda$ |  $25m,50m,75m,100m,125m$

Performance Metrics. The effectiveness metrics include total influence
maximization by proposed Algorithms, and the efficiency metric is evaluated
through the running time, which is determined by the average result from three
consecutive runs.

Environment Setup. All codes are implemented in Python using Jupyter Notebook
and experimented on an HP Z4 workstation with 64 GB memory and an Xeon(R) 3.50
GHz processor.

###  5.3. Baseline Methodologies

We have compared the performance of the proposed solution approaches with the
following baseline methods:

##### Random Slot and Random Tag (RSRT):

In this method, $k$ many random slots and $\ell$ many random tags are chosen
and returned as solution.

##### Random Slot and High-Frequency Tag(RSHFT):

Frequency of a tag is defined as the number of people with whom this tag is
associated. In this method, we count the frequency of every tag and sort all
the tags based on the frequency value. This method returns $\ell$ many tags
and $k$ many random slots from this sorted list.

##### Maximum Coverage Slot and Random Tag (MAXSRT):

For any billboard slot, its coverage is defined as the number of people
passing by that slot. In this method, the coverage of every billboard slot is
computed, and they are sorted based on this value. From this sorted list, $k$
many billboard slots are returned, and $\ell$ many tags are chosen uniformly
at random.

##### Top-$k$ Slot and Top-$\ell$ Tag (TSTT):

In this method, individually calculate influence for all billboard slots and
individual influence for all tags. After that, separately sort them in
descending order based on their influence values. From this sorted list, we
pick Top-$k$ billboard slots and Top-$\ell$ tags.

##### Top-$k$ Slot and Random $\ell$ Tag (TSRT):

In this method, individual influence for both billboard slots and tags is
calculated. Then, billboard slots based on influence value are sorted in
descending order, and from the sorted list, Top-$k$ slots will be picked. In
the case of tags, randomly $\ell$ many tags are picked from an unsorted tag
list.

##### Random $k$ Slot and Top-$\ell$ Tag (RSTT):

This method is just reverse of TSRT approach. At first, individual influence
for both billboard slots and tags is computed, and according to the influence
value, all tags are sorted in descending order. Now, from the sorted tags
list, Top-$\ell$ tags are picked, and from the billboard slot set, randomly
$k$ many slots are chosen.

###  5.4. Goals of our Experiments

In this study, we address the following Research Questions (RQ).

  * •

RQ1: How does the influence value increase if we increase the number of slots
and tags to be selected?

  * •

RQ2: If we increase the number of slots and tags, how do the computational
time requirements of the proposed and the baseline methods change?

  * •

RQ3: If we increase the size of the trajectory, how do the proposed method’s
influence value and computational time requirement change?

  * •

RQ4: For the stochastic greedy algorithm, if we change the value of
$\epsilon$, how do the computational time and the quality of the solution
change?

###  5.5. Experimental Results with Discussions

In this section, we describe the experimental results and answer each research
question posed in Section 5.4.

##### Budget $(k,\ell)$ Vs. Influence

: Budget and influence are two important components that often play a
significant role in decision-making for billboard advertisements. It is
trivial that increasing the budget will also increase the influence value. In
our experiment, for each ‘tag’ value $\ell$, we vary the ‘number of billboard
slot‘ $k$ as $25$, $50$, $100$, $150$, and $200$ to measure the obtained
influence value and time requirement, as presented in Figure 2. Now, it is
observed that the influence probability of ‘tags’ in the NYC dataset is not
well distributed as some ‘tags’ are the most influential, and most of the
‘tags’ are the least influential. That’s why ‘Lazy Greedy’, ‘Stochastic
Greedy’, and among baseline methodologies, ‘TSTT’, ‘RSTT’, and ‘RSHFT’
performs well. But, ‘MAXSRT’, and ‘TSRT’ are not performing well due to random
‘tag’ selection. On the other hand, the influence probability of ‘tags’ in the
LA dataset is well distributed, and for this reason, ‘TSRT’, and ‘RSTT’
perform well as compared to the NYC dataset. It is also observed that in the
LA dataset, very few billboard slots play an important role in influence
maximization, and for this reason, among the baseline methods, ‘TSTT’ gives
almost equal influence compared to ‘Stochastic Greedy’. On the other hand, in
the NYC dataset, the influence probability of billboard slots is well
distributed. That’s why the influence difference between ‘Stochastic Greedy’
and ‘TSTT’ is differentiable, as shown in Figure 2 $(a,b,c,d,e)$. Now, when we
increase the ‘number of billboard slot’ from $25$ to $200$ with a fixed value
of $\ell=10$, $\epsilon=0.01$, the influence value of ‘Lazy Greedy’,
‘Stochastic Greedy’, ‘TSTT’, ‘RSTT’, ‘RSHFT’, ‘MAXSRT’, and ‘TSRT’ are
increases from $353.74$, $353.36$, $352.27$, $339.50$, $265.43$, $50.93$,
$19.71$ to $437.55$, $434.21$, $414.16$, $376.49$, $297.14$, $84.25$, $56.19$
respectively. Similarly, if we fixed ‘number of billboard slot’, $k=200$ and
vary $\ell$ from $10$ to $50$ then the influence value of ‘Lazy Greedy’,
‘Stochastic Greedy’, ‘TSTT’, ‘RSTT’, ‘RSHFT’, ‘MAXSRT’, and ‘TSRT’ are
increases from $437.55$, $434.21$, $414.16$, $376.49$, $297.14$, $84.25$,
$56.19$ to $651.45$, $641.69$, $617.26$, $583.42$, $577.81$, $338.21$,
$294.46$ respectively. Similar types of observations can also be observed in
the LA dataset. Therefore, among the proposed two methods, ‘Lazy Greedy’ gives
more influence compared to ‘Stochastic Greedy’ because of the randomized
element selection behavior of ‘Stochastic Greedy’, and ‘TSTT’ gives maximum
influence among other baseline methods for both LA and NYC datasets as
reported in Figure 2.

|  |  |
---|---|---|---
(a) $\ell=10$ | (b) $\ell=20$ | (c) $\ell=30$ | (d) $\ell=40$
|  |  |
(e) $\ell=50$ | (f) $\ell=10$ | (g) $\ell=20$ | (h) $\ell=30$
|  |  |
(i) $\ell=40$ | (j) $\ell=50$ | (k) $\ell=10$ | (l) $\ell=20$
|  |  |
(m) $\ell=30$ | (n) $\ell=40$ | (o) $\ell=50$ | (p) $\ell=10$
|  |  |
(q) $\ell=20$ | (r) $\ell=30$ | (s) $\ell=40$ | (t) $\ell=50$
Figure 2.  $(1)$ Influence varying $\ell$, when $k=25,50,100,150,200$,
$\epsilon=0.01$ ,$(a,b,c,d,e)$ for NYC, and $(f,g,h,i,j)$ for LA Dataset.
$(2)$ Time varying $\ell$, when $k=25,50,100,150,200$, $\epsilon=0.01$
,$(k,\ell,m,n,o)$ for NYC, and $(p,q,r,s,t)$ for LA Dataset.

#####  Budget $(k,\ell)$ Vs. Time:

In billboard advertisements, the efficiency of an algorithm is determined by
the analysis of time with respect to the budget. Now, to understand the time
requirement for proposed and baseline methods, we vary different $k$, and
$\ell$ values with respect to time. From Figure 2, it is observed that with a
fixed value of $\ell$, when $k$ increases, the time requirement also
increases. For example, in the LA dataset, when we fixed the value of
$\ell=10,\epsilon=0.01$, and vary $k$ value from $25$ to $200$, the time
requirement in seconds for ‘Lazy Greedy’, ‘Stochastic Greedy’, ‘TSTT’, ‘TSRT’,
and ‘RSTT’ increases from $40571$, $112259$, $16667$, $7929$, $323$ to
$43193$, $114119$, $16885$, $7984$, $332$ respectively. Here, we observed that
the small changes in time between $k=25$ to $k=200$ is happen, and this occurs
due to marginal gain computation for each proposed as well as baseline method.
Similarly, when we set $\ell=50,\epsilon=0.01$, and vary $k=25$ to $k=200$,
the time requirement for ‘Lazy Greedy’, ‘Stochastic Greedy’, ‘TSTT’, ‘TSRT’,
and ‘RSTT’ also increases from $46002$, $113872$, $16855$, $7945$, $360$ to
$47652$, $115215$, $16907$, $7993$, $365$ respectively. Here, one thing needs
to be highlighted: the experimental results of ‘Lazy Greedy’ are reported in
Figure 2 is the best case time requirements, and in the worst case it will
take same run time as ‘Incremental Greedy’. But when the dataset size is
extremely large, ‘Lazy Greedy’ may not be the right choice. Now, in the case
of ‘Stochastic Greedy’, its computational time is always far better than the
‘Incremental Greedy’ method as it is independent of the size of $k$, and
$\ell$ as discussed in Lemma 4.5. In the case of the NYC dataset, a similar
type of behavior is observed in the LA dataset for the proposed and baseline
methods. One thing must be pointed out: we have not reported the time
requirements for the ‘RSHFT’, ‘MAXSRT’, and ‘RSRT’ methods as these methods
take less than $10$ second of computational time.

#####  Trajectory Size Vs. Influence, Time:

Figure 3 shows the impact of varying trajectory size on influence and time. We
observe: (1) the influence of all proposed and baseline methods increases with
the increment of trajectory size because more users can be influenced. (2) In
the NYC and LA datasets, the influence of ‘Lazy Greedy’, and ‘Stochastic
Greedy’ is consistently better than the baseline methods. We take $k=200$, and
$\ell=50$, and vary trajectory size $40k$, $80k$, $120k$, $160k$, $200k$ for
the NYC, and $15k$, $30k$, $45k$, $60k$, $74k$ for the LA dataset as shown in
Figure 3(a), 3(b). (3) In the NYC dataset, when trajectory sizes are $40k$,
$80k$, $120k$, $160k$, $200k$, and its corresponding unique users encountered
are $924$, $969$, $1017$, $1064$, $1083$ respectively. In the case of the LA
dataset, when the trajectory varies between $15k$ to $74k$, the number of
unique users encountered is $2000$. (4) Figures 3(c), and 3(d) shows
computational time for the NYC and LA dataset. We observe that ‘Lazy Greedy’,
and ‘Stochastic Greedy’ scale linearly w.r.t. trajectory size, which is
consistent in our analysis in both the NYC and LA datasets. Although the
growth in time requirement in ‘Stochastic Greedy’ is faster than ‘Lazy
Greedy’, e.g., when trajectory size varies from $40k$ to $220k$, and $15k$ to
$74k$, the time requirement increases almost $6$x times, and $6.5$x times for
NYC and LA datasets, respectively. But, in the ‘Lazy Greedy’, run time
increases linearly in the best case as only one time marginal gain needs to be
computed for all the elements, and from on-wards only comparison operation
needs to be executed. Now, among the baseline methods, ‘TSTT’ takes maximum
time, and with the increase of trajectory size, the run time of all baseline
methods increases linearly.

|  |  |
---|---|---|---
(a) $k=200,\ell=50,\epsilon=0.01$ | (b) $k=200,\ell=50,\epsilon=0.01$ | (c) $k=200,\ell=50,\epsilon=0.01$ | (d) $k=200,\ell=50,\epsilon=0.01$
Figure 3. $(1)$ Influence varying trajectory size, when $k=200$, $\ell=50$,
and $\epsilon=0.01$ $(a)$ for NYC, and $(b)$ for LA Dataset. $(2)$ Time
varying trajectory size, when $k=200$, $\ell=50$, and $\epsilon=0.01$ $(c)$
for NYC, and $(d)$ for LA Dataset.

#####  Epsilon ($\epsilon$) Vs. Influence, Time:

Figure 4(a), 4(b) shows the impact of varying $\epsilon$ values on ‘Stochastic
Greedy’ w.r.t. influence, and time. We find: (1) when the $\epsilon$ value
increases, the influence value decreases. The decreasing influence rate in the
NYC dataset is more than in the LA dataset. (2) when the $\epsilon$ value
varies from $0.01$ to $0.2$, the run time on both the NYC and LA datasets
decreases linearly. In the ‘Stochastic Greedy’, we randomly pick a subset of
elements, and the cardinality of the subset depends on the $\epsilon$ value.
If the $\epsilon$ value decreases, then the subset size increases, and there
is a very small loss in influence compared to ‘Incremental Greedy’, but run
time increases. For example, in the NYC dataset, when $k=200,\ell=50$ and vary
$\epsilon$ for the value of $0.01,0.05,0.1,0.15,0.2$, the influence values are
$641.69$, $631.60$, $610.11$, $594.27$, $593.12$ and corresponding run-time
are $193850$, $147011$, $127458$, $110355$, $95880$ in seconds, respectively.
A similar type of result was observed on the LA dataset as shown in Figure
4(a), 4(b). So, the user-defined parameter $\epsilon$, gives us the freedom to
compromise either in influence or run time.

|  |  |
---|---|---|---
(a) $k=200,\ell=50$ | (b) $k=200,\ell=50$ | (c) $k=200,\ell=50,\epsilon=0.01$ | (d) $k=200,\ell=50,\epsilon=0.01$
Figure 4. $(1)$ Influence varying $\epsilon~{}(a)$, and Time Varying
$\epsilon~{}(b)$ when $k=200$, $\ell=50$ for NYC, LA Dataset. $(2)$ Influence
$(c)$, Time $(d)$, varying trajectory size, when $k=200$, $\ell=50$, and
$\epsilon=0.01$ for different Algorithms on NYC Dataset.

#####  Additional Discussions:

To find out the efficiency of ‘Stochastic Greedy’, we compare its performance
with ‘Incremental Greedy’ and ‘Lazy Greedy’. In our experiment, we fixed
$k,\ell,\epsilon$ value, which varies over different trajectory sizes. Our
experiment shows that ‘Incremental Greedy’ and ‘Lazy Greedy’ achieve the same
amount of influence, but there is a huge difference when talking about run
time. ‘Stochastic Greedy’ achieves less influence than both ‘Incremental
Greedy’ and ‘Lazy Greedy’ but takes much less run time compared to
‘Incremental Greedy’. As we previously discussed, in the worst case, ‘Lazy
Greedy’ will take the same amount of time as ‘Incremental Greedy’ takes, and
in our experiment, we, fortunately, got the best case results of ‘Lazy Greedy’
due to the nature of the datasets, as reported in Figure 4(c), 4(d). When
trajectory size increases from $5k$ to $25k$, the run time of ‘Incremental
Greedy’, ‘Lazy Greedy’, and ‘Stochastic Greedy’ also increases from $96044$,
$2090$, $4546$ to $572512$, $6144$, $15905$ seconds, i.e., $6$x, $3$x, $3.5$x
respectively. So, for trajectory size $25k$, ‘Incremental Greedy’ will take
almost $36$x more time than ‘Stochastic Greedy’, and we observe that for
larger trajectory size, i.e., $200k$, the ‘Incremental Greedy will not
complete its execution with a reasonable computational time. One thing needs
to be highlighted for our experiment: we take $\lambda=100~{}meter$, i.e., we
assume within the range of $100m$, a billboard slot can influence all
trajectories with a certain probability as shown in Figure 5. We have also
experimented with $25m$, $50m$, $75m$, $100m$, and $125m$ as $\lambda$ values
and observed that with the increment of $\lambda$ value, the influence as well
as run time increases because one billboard slot can influence more number of
trajectories.

|  |  |
---|---|---|---
(a) $k=200,\ell=50,\epsilon=0.01$ | (b) $k=200,\ell=50,\epsilon=0.01$ | (c) $k=200,\ell=50,\epsilon=0.01$ | (d) $k=200,\ell=50,\epsilon=0.01$
Figure 5. $(1)$ Influence varying Distance $(\lambda)$, when $k=200$,
$\ell=50$, and $\epsilon=0.01$ $(a)$ for NYC, and $(b)$ for LA Dataset. $(2)$
Time varying Distance $(\lambda)$, when $k=200$, $\ell=50$, and
$\epsilon=0.01$ $(c)$ for NYC, and $(d)$ for LA Dataset.

##  6\. Conclusion

This paper has studied the problem of jointly selecting influential billboard
slots and influential tags. First, we show that the joint influence function
is non-negative, monotone, and bi-submodular. We show that the problem is NP-
hard and subsequently propose an orthant-wise incremental greedy algorithm
that gives a constant factor approximation algorithm. Though this method is
simple to understand and easy to implement, it still does not scale well when
the trajectory dataset is large due to excessive marginal gain computations.
To address this approach, we propose the orthant-wise Lazy and Stochastic
Greedy approach, which executes fast while leading to more or less similar
influence. Still, the problem is not solved on the ground because we must also
report which tag will be displayed in which slot to maximize the influence.
Developing more efficient techniques to address slot selection and allocation
problems will remain an active area of research in the near future.

## References

  * (1)
  * Ali et al. (2022) Dildar Ali, Suman Banerjee, and Yamuna Prasad. 2022\.  Influential Billboard Slot Selection Using Pruned Submodularity Graph. In _Advanced Data Mining and Applications_ , Weitong Chen, Lina Yao, Taotao Cai, Shirui Pan, Tao Shen, and Xue Li (Eds.). Springer Nature Switzerland, Cham, 216–230.
  * Ali et al. (2023) Dildar Ali, Suman Banerjee, and Yamuna Prasad. 2023\.  Influential Billboard Slot Selection using Spatial Clustering and Pruned Submodularity Graph.  arXiv:2305.08949 [cs.DB]
  * Banerjee and Pal (2022) Suman Banerjee and Bithika Pal. 2022.  Budgeted influence and earned benefit maximization with tags in social networks.  _Social Network Analysis and Mining_ 12, 1 (2022), 21\.
  * Banerjee et al. (2020) Suman Banerjee, Bithika Pal, and Mamata Jenamani. 2020\.  Budgeted influence maximization with tags in social networks. In _Web Information Systems Engineering–WISE 2020: 21st International Conference, Amsterdam, The Netherlands, October 20–24, 2020, Proceedings, Part I 21_. Springer, 141–152.
  * Guo et al. (2017) Long Guo, Dongxiang Zhang, Gao Cong, Wei Wu, and Kian-Lee Tan. 2017.  Influence Maximization in Trajectory Databases.  _IEEE Transactions on Knowledge and Data Engineering_ 29, 3 (2017), 627–641.  https://doi.org/10.1109/TKDE.2016.2621038
  * Ke et al. (2018) Xiangyu Ke, Arijit Khan, and Gao Cong. 2018.  Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks. In _Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018_ , Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 1097–1111.  https://doi.org/10.1145/3183713.3199670
  * Khuller et al. (1999) Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. 1999\.  The budgeted maximum coverage problem.  _Inform. Process. Lett._ 70, 1 (1999), 39–45.  https://doi.org/10.1016/S0020-0190(99)00031-9
  * Li et al. (2014) Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, and Wen-syan Li. 2014.  Efficient Location-Aware Influence Maximization. In _Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data_ (Snowbird, Utah, USA) _(SIGMOD ’14)_. Association for Computing Machinery, New York, NY, USA, 87–98.  https://doi.org/10.1145/2588555.2588561
  * Liu et al. (2017) Dongyu Liu, Di Weng, Yuhong Li, Jie Bao, Yu Zheng, Huamin Qu, and Yingcai Wu. 2017\.  SmartAdP: Visual Analytics of Large-scale Taxi Trajectories for Selecting Billboard Locations.  _IEEE Transactions on Visualization and Computer Graphics_ 23, 1 (2017), 1–10.  https://doi.org/10.1109/TVCG.2016.2598432
  * Liu et al. (2021) Ping Liu, Meng Wang, Jiangtao Cui, and Hui Li. 2021\.  Top-k competitive location selection over moving objects.  _Data Science and Engineering_ 6, 4 (2021), 392–401.
  * Mitra et al. (2019) Shubhadip Mitra, Priya Saraf, and Arnab Bhattacharya. 2019\.  Tips: mining top-k locations to minimize user-inconvenience for trajectory-aware services.  _IEEE Transactions on Knowledge and Data Engineering_ 33, 3 (2019), 1238–1250.
  * Qi et al. (2020) Zhixin Qi, Hongzhi Wang, Tao He, Chunnan Wang, Jianzhong Li, and Hong Gao. 2020\.  TAILOR: time-aware facility location recommendation based on massive trajectories.  _Knowledge and Information Systems_ 62, 9 (2020), 3783–3810.
  * Tekawade and Banerjee (2023) Atharva Tekawade and Suman Banerjee. 2023.  Influence Maximization with Tag Revisited: Exploiting the Bi-submodularity of the Tag-Based Influence Function. In _International Conference on Advanced Data Mining and Applications_. Springer, 772–786.
  * Wang et al. (2022) Liang Wang, Zhiwen Yu, Bin Guo, Dingqi Yang, Lianbo Ma, Zhidan Liu, and Fei Xiong. 2022.  Data-Driven Targeted Advertising Recommendation System for Outdoor Billboard.  _ACM Trans. Intell. Syst. Technol._ 13, 2, Article 29 (jan 2022), 23 pages.  https://doi.org/10.1145/3495159
  * Wang et al. (2020) Liang Wang, Zhiwen Yu, Dingqi Yang, Huadong Ma, and Hao Sheng. 2020.  Efficiently Targeted Billboard Advertising Using Crowdsensing Vehicle Trajectory Data.  _IEEE Transactions on Industrial Informatics_ 16, 2 (2020), 1058–1066.  https://doi.org/10.1109/TII.2019.2891258
  * Wang et al. (2016) Meng Wang, Hui Li, Jiangtao Cui, Ke Deng, Sourav S Bhowmick, and Zhenhua Dong. 2016\.  Pinocchio: Probabilistic influence-based location selection over moving objects.  _IEEE Transactions on Knowledge and Data Engineering_ 28, 11 (2016), 3068–3082.
  * Wang et al. (2021) Sheng Wang, Zhifeng Bao, J Shane Culpepper, and Gao Cong. 2021\.  A survey on trajectory data management, analytics, and learning.  _ACM Computing Surveys (CSUR)_ 54, 2 (2021), 1–36.
  * Wang et al. (2018) Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, and Gao Cong. 2018.  Reverse k Nearest Neighbor Search over Trajectories (Extended Abstract). In _2018 IEEE 34th International Conference on Data Engineering (ICDE)_. 1785–1786.  https://doi.org/10.1109/ICDE.2018.00250
  * Wong et al. (2009) Raymond Chi-Wing Wong, M. Tamer Özsu, Philip S. Yu, Ada Wai-Chee Fu, and Lian Liu. 2009\.  Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor.  _Proc. VLDB Endow._ 2, 1 (aug 2009), 1126–1137.  https://doi.org/10.14778/1687627.1687754
  * Xia et al. (2005) Tian Xia, Donghui Zhang, Evangelos Kanoulas, and Yang Du. 2005\.  On Computing Top-t Most Influential Spatial Sites. In _Proceedings of the 31st International Conference on Very Large Data Bases_ (Trondheim, Norway) _(VLDB ’05)_. VLDB Endowment, 946–957.
  * Yang et al. (2015) Dingqi Yang, Daqing Zhang, Vincent. W. Zheng, and Zhiyong Yu. 2015.  Modeling User Activity Preference by Leveraging User Spatial Temporal Characteristics in LBSNs.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ 45, 1 (2015), 129–142.
  * Zhang et al. (2020) Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. 2020\.  Towards an Optimal Outdoor Advertising Placement: When a Budget Constraint Meets Moving Trajectories.  _ACM Trans. Knowl. Discov. Data_ 14, 5, Article 51 (jul 2020), 32 pages.  https://doi.org/10.1145/3350488
  * Zhang et al. (2019) Yipeng Zhang, Yuchen Li, Zhifeng Bao, Songsong Mo, and Ping Zhang. 2019.  Optimizing Impression Counts for Outdoor Advertising. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (Anchorage, AK, USA) _(KDD ’19)_. Association for Computing Machinery, New York, NY, USA, 1205–1215.  https://doi.org/10.1145/3292500.3330829
  * Zhou et al. (2011) Zenan Zhou, Wei Wu, Xiaohui Li, Mong Li Lee, and Wynne Hsu. 2011.  MaxFirst for MaxBRkNN. In _2011 IEEE 27th International Conference on Data Engineering_. 828–839.  https://doi.org/10.1109/ICDE.2011.5767892