An Effective Tag Assignment Approach for Billboard Advertisement
Dildar Ali Harishchandra Kumar Suman Banerjee Yamuna Prasad




Ali et al. 
Indian Institute of Technology Jammu,
J & K-181221, India. National Institute of Technology Raipur, Chhattisgarh, India

2021rcs2009@iitjammu.ac.in, hkumar049.btech2021@cse.nitrr.ac.in, suman.banerjee@iitjammu.ac.in, yamuna.prasad@iitjammu.ac.in
An Effective Tag Assignment Approach for Billboard Advertisement
    Dildar Ali1 Harishchandra Kumar2 Suman Banerjee1 Yamuna Prasad1
    
===================================================================

§ ABSTRACT 
  Billboard Advertisement has gained popularity due to its significant outrage in return on investment. To make this advertisement approach more effective, the relevant information about the product needs to be reached to the relevant set of people. This can be achieved if the relevant set of tags can be mapped to the correct slots. Formally, we call this problem the Tag Assignment Problem in Billboard Advertisement. Given trajectory, billboard database, and a set of selected billboard slots and tags, this problem asks to output a mapping of selected tags to the selected slots so that the influence is maximized. We model this as a variant of traditional bipartite matching called One-To-Many Bipartite Matching (OMBM). Unlike traditional bipartite matching, a tag can be assigned to only one slot; in the OMBM, a tag can be assigned to multiple slots while the vice versa can not happen. We propose an iterative solution approach that incrementally allocates the tags to the slots. The proposed methodology has been explained with an illustrated example. A complexity analysis of the proposed solution approach has also been conducted. The experimental results on real-world trajectory and billboard datasets prove our claim on the effectiveness and efficiency of the proposed solution. 




§ INTRODUCTION

In the past few years, advertisement has become a central goal for any E-commerce house as it gives a way to convince people about their products or different social and political events, and because of this, their products and ticket sales increase, i.e., revenue increases. The existing literature reported that around 7 - 10% of total revenue is utilized by an E-commerce house for advertising purposes[<https://www.lamar.com/howtoadvertise/Research/>]. Among the several advertising techniques (e.g., newspapers, social networks, television, billboards, etc), billboard advertising has emerged as an effective advertising technique as it is easy to place advertisements and ensures more investment returns[<https://www.thebusinessresearchcompany.com/report/billboard-and-outdoor-advertising-global-market-report>]. Billboard Advertisement is a technique for creating a promotional advertisement for products, events, etc., with the hope that if the content is displayed to a relevant group of people, a subset of them will be influenced, and they might buy the product or attend the event. This will help increase revenue or promote the event. The advertisement content is formalized as tags, and different tags are relevant to different sets of people. So, the tag plays an important role in determining the influence of a billboard. In real-life scenarios, billboard advertisements require the selection of slots and tags, and although the influence value depends on billboard slots and tags, the literature is limited. However, a few studies have considered using tags to maximize their influence on social networks <cit.>. Ke at al.<cit.> first studied the problem of finding ℓ many tags and k many users in a social network to maximize the influence. In the context of the billboard advertisement, Ali et al. <cit.> first introduce the problem of finding the most influential billboard slots and tags. Knowing which tag is important to which slot to maximize the influence is essential in practical scenarios. This is the key problem addressed in this paper. 



  
Motivation.
To make an advertisement effective, it is important to adopt a suitable approach such that the information reaches the group of relevant people. In real life, different tags are relevant to various categories of people. Consider a political party running a campaign for an upcoming election and proposing different projects in their election manifesto for different categories of people. For example, this might include doubling the farmer's income in the next three years and a certain percentage tax benefit to the industrialists. Now, the tags relevant to the benefits of the farmers must be displayed on the billboard slots where the audience is farmers. So, to address the real-life scenario study of Tag Assignment Problem in Billboard Advertisement is essential.



  
Our Contribution. 

In billboard advertising, the influence varies greatly depending on which tags are displayed in which slots. Studies like <cit.> have explored finding the top-k influential billboard slots using various techniques. Recently, Ali et al. <cit.> proposed methods to identify influential slots and tags jointly.  However, no existing literature specifically addresses the tag assignment problem in billboard advertisements. This paper tackles this issue and proposes an iterative approach for incrementally allocating tags to slots.
In particular, we make the following contributions in this paper:


    
  * We model the Tag Assignment Problem as a two-sided matching problem and show that this problem is NP-hard.
    
  * We introduce One-to-Many Bipartite Matching and propose an iterative solution for the tag assignment problem.
    
  * We analyzed the time and space requirement of the proposed solution and provided an approximation guarantee.
    
  * The proposed approaches have been implemented with real-world trajectory and billboard datasets to highlight their effectiveness and efficiency.


Rest of the paper has been organized as follows. Section <ref> describes the required preliminary concepts and defines our problem formally. Section <ref> contains the proposed solution approaches with a detailed analysis. The experimental evaluation has been described in Section <ref>. Finally, Section <ref> concludes our study and gives directions for future research.



§ PRELIMINARIES AND PROBLEM DEFINITION
 
This section describes the preliminary concepts and formally defines our problem. Initially, we start by explaining the billboard advertisement and its procedure.



 §.§ Billboard Advertisement
 A trajectory database contains the location information of trajectories of a particular city, and it can be stated in Definition <ref>.

 
The trajectory database 𝒟 is a collection of a tuple in the form of <𝒰_id, 𝒰_loc, [t_1,t_2]>, where 𝒰_id, 𝒰_loc and [t_1,t_2] represents the unique user id, user location and time stamp, respectively.


For example, there is a tuple <𝒰_9, Kolkata_Airport, [200, 300]> and it denotes user 𝒰_9 was in the Kolkata_Airport for the duration of [200, 300]. Next, we define the billboard database in Definition <ref>.

 
A billboard database can be defined in the form of a tuple <b_id, b_loc, b_cost>, where b_id, b_loc and b_cost denotes a unique billboard id, billboard location, and billboard cost, respectively.


Assume a set of digital billboards ℬ={b_1, b_2, …, b_m} owned by an influence provider are placed across a city run for the duration [T_1, T_2]. Different commercial houses can hire these billboards slot-wise to show their advertisement content. Now, we define the notion of billboard slot in Definition <ref>.

 
A billboard slot is denoted by a tuple of the form (b_j, [t,t+Δ]) where b_j ∈ℬ and t ∈{T_1, T_1 + Δ + 1, …, T_2- Δ-1}. Here, Δ denotes the duration of each slot.

It can be observed that for each billboard, the number of slots associated with it will be T_2-T_1/Δ [Here, we assume that Δ perfectly divides T_2-T_1.]. There are m many billboards (i.e., |ℬ|=m), hence, the total number of slots denoted as ℬ𝒮 are m ·T_2-T_1/Δ. Depending on the available budget, an e-commerce house hires slots weekly or monthly to fulfill their influence demand. Next, we describe the influence function in Section <ref>.



 §.§ Influence Function

Normally, e-commerce companies approach the influence provider, who owns multiple billboard slots, to advertise their products and maximize the influence of their products. Now, one question arises: How is the influence of a billboard slot calculated? We state this in Definition <ref>.


    Given a subset of billboard slots 𝒮⊆ℬ𝒮, the influence of 𝒮  is denoted as ℐ(𝒮) and defined it as the sum of the influence probabilities of the individual users in the trajectory database.
    
    ℐ(𝒮)= u ∈𝒟∑ [1-  b ∈𝒮∏(1-Pr(u,b))]
  

Here, the influence function ℐ() maps each subset of billboard slots to its corresponding influence value, i.e., ℐ: 2^ℬ𝒮⟶ℝ^+_0 and ℐ(∅) = 0. The influence function defined in Equation <ref> is widely used in the existing advertising literature <cit.> also.

The Influence function ℐ() is non-negative, monotone and submodular.


As mentioned previously, when one person views an advertisement running on a billboard slot, he is influenced by a certain probability. Most existing literature <cit.> does not consider that the probability value also depends on the running advertisement content (e.g., tag).
 
Therefore, we have considered tags to be an important factor in this paper. Consider 𝒯_u_i be the set of tags associated with user u_i and for all the users in 𝒰, the set of tags is relevant as a whole can be denoted as 𝒯 = u_i ∈𝒰⋃𝒯_u_i. Now, for every u ∈𝒰 and t ∈𝒯, the influence probability can be denoted as Pr(u|t) and defined in Definition <ref>.


Given a subset of tags 𝒯^'⊆𝒯 and any user u ∈𝒰, the tag-specific influence probability can be defined in Equation <ref>.

 
    Pr(u|𝒯^')= 1-t ∈𝒯^'∏ (1-Pr(u|t))



Now, to find out the impact of tags in billboard slots, we define the Tag-specific influence of a billboard slot in Definition <ref>.

 
Given a subset of billboard slots 𝒮⊆ℬ𝒮 and a subset of tags 𝒯^'⊆𝒯, the tags-specific influence of 𝒮 is denoted by ℐ(𝒮 | 𝒯^') and defined using Equation No. <ref>.

    ℐ(𝒮|𝒯^')= u ∈𝒰∑ 1- b ∈𝒮∏ (1-Pr(u,b|𝒯^'))



Here, the influence function ℐ() is a combined function that maps each tag and billboard slot to its corresponding influence value, i.e., ℐ: 2^𝒯× 2^ℬ𝒮⟶ℝ^+_0. Next, we describe the bipartite matching in Section <ref>.



 §.§ Bipartite Matching


In this work, we formulate our problem as a bipartite matching problem and state this problem in Section <ref>. Next, we define bipartite matching in Definition <ref>.


A matching is bipartite if it contains a set of edges ℰ_b⊆ E, which do not share any common vertex <cit.>.




In traditional bipartite matching <cit.>, each tag is allocated to exactly one billboard slot, providing an optimal solution in polynomial time (𝒪((n+m)^3) via the Hungarian Method) <cit.>. However, this doesn't suit our problem, as we need to allocate a single tag to multiple billboard slots, with each slot associated with only one tag. To address this, we introduce an iterative approach, formulating it as a one-to-many bipartite matching problem, defined in Definition <ref>.


A matching is said to be one-to-many bipartite matching if it contains a set of edges ℰ_b∈ E that may share a common vertex in u ∈𝒰 whereas each vertex in v ∈𝒱 can connect with at most one vertex in 𝒰 via an edge e ∈ℰ_b <cit.>.



























































































 §.§ Problem Definition

This section defines the Tag Allocation Problem formally. The inputs to this problem are trajectory, and billboard database, and set of selected slots (𝒮) and tags (𝒯^') and the goal is allocate the tags to the slots such that the influence is maximized. One thing to highlight here is that two tags can not be allocated to a single slot. However, the vice versa can happen. Also, it can be observed that in the worst case the number of possible allocations will be of 𝒪(|𝒮|^|𝒯^'|). Now, we state our problem formally in Definition <ref>.





  
Given a trajectory database 𝒟, a billboard database ℬ, a selected subset of slots 𝒮 and tags 𝒯^' respectively, the tag allocation problem asks to assign a tag to a slot such that the influence is maximized.

From the computational point of view, this problem can be posed as follows: 



Tag Allocation Problem 


Input: A trajectory (𝒟) and Billboard (ℬ) Database, A set of slots (𝒮) and tags (𝒯).

Problem: Find out an allocation of the tags to the slots such that the influence is maximized.



By a reduction from the Set Cover Problem, we can show that the Tag Assignment Problem is NP-hard. This result has been presented in Theorem <ref>. Due to the space limitation, we are not able to give the whole reduction. 

 The 
Tag Assignment Problem in Billboard Advertisement is NP-hard and hard to approximate in a constant factor.

Next, we discuss the proposed solution methodologies in Section <ref>.



§ PROPOSED SOLUTION APPROACH



Our experiments are represented in two folded ways: first, by selecting influential slots and tags, and second, by allocating tags to the slots. To address the first goal, we adopt the stochastic greedy approach for influential slots and tags selection introduced by Ali et al. <cit.>. Next, we construct a weighted bipartite graph using the selected slots and tags, and it is described in Section <ref>.



 §.§ Construction of the Weighted Bipartite Graph

 In this formulation, we have billboard slots and tags represented in the form of a bipartite graph 𝒢_b = (𝒰∪𝒱,ℰ_b), where 𝒰 contains the set of tags while 𝒱 contains a set of billboard slots and in practice, |𝒰| < < |𝒱|. We have adopted the following approach to construct the edge set of the bipartite graph.  For every tag u ∈𝒰 and every slot v ∈𝒱, we compute the influence (i.e., edge weight) of all the individual allocations using Equation No. <ref>. Next, we compute the mean weight (μ) and standard deviation of all the edge weight using μ = 1/|ℰ_b|∑_e ∈ℰ_b𝒲(e) and σ = √(1/|ℰ_b|∑_e ∈ℰ_b (𝒲(e) - μ)^2), respectively. For each e ∈ℰ_b we compute θ-score value 𝒵(e) = 𝒲(e) - μ/σ and prune the edge if 𝒵(e) < θ, where θ is the user-defined parameter (it may be -1, 0, etc.). Basically, we set a threshold, i.e., μ + θ·σ, and if 𝒲(e) < μ + θ·σ, then prune that edge. This method ensures that only edges with weights significantly lower than the average are pruned.

Next, we introduce the one-to-many bipartite matching approach and describe it in Section <ref> to address the second goal.



 §.§ One-to-Many Bipartite Matching (OMBM)

The OMBM algorithm takes a bipartite graph containing edges between tags and billboard slots as input and returns an allocation of tags to the billboard slots in the form of a 1-D array. This array maps a billboard slot to a tag such that each is allocated to exactly one tag; however, one tag may be allocated to more than one slot. At first, in Line No 1 to 3, we initialize the array 𝒬 as empty for the slots v ∈𝒱. In-Line No. 4  loop will execute till the billboard slots, |𝒱| is empty and in Line No. 5 to 6, for each slot v ∈𝒱 store the possible matches in the adjacent vertices of v into 𝒞_v from tags set 𝒰. Initially, 𝒞_v is initialized with the adjacent vertices of v i.e., 𝒜(v). Before further discussions, we define the notion of a dominating edge in Definition <ref>.

In a bipartite graph, an edge ℰ_uv is said to be dominating if 𝒲_uv > 𝒲_uv^' and 𝒲_uv > 𝒲_u^'v where 𝒲_uv denotes edge weight of tag u to slot v and v^'≠ v, u^'≠ u, u ∈𝒰, v ∈𝒱.


Next in Line No. 7 dominating edge set E_d is initialized to empty set. In-Line No. 8 to 12 for each slot v ∈𝒱 the lc(v) function takes v as input and returns an adjacent tag u of v that has maximum edge weight, i.e., the best tag for matching. If v is also the best match for lc(u), then such a vertex pair will be added to E_d. Now, in Line No. 11 to 17, Algorithm <ref> deals with the edges that are not added to E_d in Line No. 8  to  12. At first, we pick an end node u ∈𝒰 from E_d. Next, we delete the edge ℰ_uv associated with u as the slot is already matched with a tag. In-Line No. 17, we iterate through all 𝒞_u, and this represents the slots that have not yet been matched with any tag. Now, in Line No. 18, we also check if the total number of slots |Count_lc(v)| connected for the tag lc(v) is still within upper limit Bound_lc(v) or not. If both conditions are satisfied, we add an edge with v and u to E_d and allocate slot v to tag u. In-Line No. 21 and 22, we remove the allocated tag u and slot v, respectively. Finally, Algorithm <ref> will return 𝒬 by allocating billboard slots to tags.
Comment/*  */






  
Complexity Analysis.
In-Line No. 1 to 3, initializing a 1-dimensional array will take 𝒪(k) time as there is k number of slots. The  loop at Line No. 4 will execute for 𝒪(k) times and Line No. 5 to 6 will execute for 𝒪(k^2). Next, in Line No. 7 initializing dominating set E_d will take 𝒪(k) time. Line No. 8  will execute for 𝒪(k^2) times, and Line No. 9 finding the best-matching vertex will take 𝒪(k^2·ℓ) time. Line No. 10 to 12 will take 𝒪(k^2) times, and Line No. 8 to 12 will take 𝒪(k^2·ℓ + k^2) time to execute. Next, in Line No. 13  will execute for 𝒪(k^2) time and Line No. 14 to 16 will take 𝒪(k^2) time. The  at Line No. 17 to 20 will execute for 𝒪(k^2·ℓ) time. Line No. 21 and 22 will take 𝒪(k^2) time. Finally, Line No. 23 to 24 will be executed for 𝒪(k) times in the worst case. So, Algorithm <ref> will take total 𝒪(k + k + k^2·ℓ + k^2 + k^2·ℓ), i.e., 𝒪(k^2·ℓ) time to execute in the worst case. The additional space requirement for Algorithm <ref> will be 𝒪(k + k + ℓ) i.e., 𝒪(k + ℓ) for the 1-D array 𝒬, 𝒞(v) and E_d. 

Note that |E| = kℓ in the case of a complete bipartite graph. However, if some slots are not eligible for certain tags to be allocated due to the θ-score threshold value, then |E| < kℓ. Therefore, we state the complexity of Algorithm <ref> as linear on the number of edges generated between tags and slots.


The time and space complexity of the Algorithm <ref> will be 𝒪(k^2·ℓ) and 𝒪(k+ℓ), respectively.



All edges in the dominating edge set E_d must be a part of the optimal matching in the solution obtained before Line No. 13 in Algorithm <ref>.




 Assume ℳ^opt is an optimal matching in graph 𝒢. Suppose there exists an edge {u,v}∈ E_d not in ℳ^opt. Let {u,v'}∈ℳ^opt with 𝒲_uv > 𝒲_uv'. Consider ℳ^' = [ℳ^opt∖{u,v'}] ∪{u,v}. Then 𝒲(ℳ^') > 𝒲(ℳ^opt), contradicting ℳ^opt's optimality. Hence, all edges in E_d are in ℳ^opt.



Each billboard slot will be assigned at most one tag in the solution.



Given a billboard slot v ∈𝒱 and a tag u ∈𝒰, u is assigned to v only if 𝒬(v) = ∅ (as stated in Line No. 17 to 20 of Algorithm <ref>). Once a tag u is assigned to a billboard slot v, 𝒬(v) is set to u. Since 𝒬(v) ≠∅ after this assignment, the condition 𝒬(v) = ∅ will no longer hold for v. Therefore, v cannot be reassigned to another tag and it defines ∀ v ∈𝒱, ∃ at most one  u ∈𝒰 such that 𝒬(v) = u.
This implies that each billboard slot v is assigned at most one tag in the solution.



Each tag u_i∈𝒰 will finally have exactly Bound_i many billboard slots assigned to it.



In Algorithm <ref>, the allocation performed in Line No. 18 𝒬_v = lc(v) happens when |Count_lc(v)| < Bound_lc(v) and along with Lemma <ref> allows us to conclude this.




 §.§ Tag Allocation Process

The overall tag allocation procedure is shown in Algorithm <ref>. At first, in Line No. 1, a set of billboard slots (𝒮) and a set of tags (𝒯) is provided as an input in the stochastic greedy <cit.>, and it returns a subset of slots and tags, i.e., 𝒮^'⊆𝒮 and 𝒯^'⊆𝒯 as output. Next, in Line No. 2, the bipartite graph is generated using bipartite sets of tags and billboard slots. In-Line No. 3, based on the θ-score threshold value, a pruned bipartite graph (𝒢^') is generated. In-Line No 4, 𝒢^' is used in Algorithm <ref> as input, where it finds a mapping of the billboard slots to the tags and returns a multi-slot tag allocation.

Comment/*  */





Algorithm <ref> gives an approximation ratio of ρ≤ 1 + max_1 ≤ i ≤ m (𝒦_i - δ_i), where δ_i∈{0,1} and 𝒦_i is the set of slots assigned to tag u_i.


As mentioned previously, in Algorithm <ref> Line No. 13 to 20 performs a matching of tag u_i to (|𝒦_i| - δ_i) slots where δ_i∈{0,1}  for i = 1, 2, …, ℓ. Next, lc(v) = u represents the tag u_i is matched with slot v_j where v ∈𝒱 as given in Line No. 18 v = lc(u)= lc(lc(v)) is satisfied. If {v,u} is not part of optimal matching, however, it is added to the E_d then at most (1 + 𝒦_i - δ_i) many edges may not be considered. The cost for assigning slots to a tag t_i will be at most |𝒦_i| + 1 - δ_i. So, the total cost C_A can be approximated by summing the costs over all tags t_i i.e., C_A≤∑_i=1^m (|𝒦_i| + 1 - δ_i) and the optimal solution has a cost C_opt = ∑_i=1^m |𝒦_i|. So we can write ρ = max( ∑_i=1^m (|𝒦_i| + 1 - δ_i)/∑_i=1^m |𝒦_i|).
Since |𝒦_i| are the optimal slots, ρ≤ 1 + max_1 ≤ i ≤ m( 1 - δ_i/|𝒦_i|). The term max_1 ≤ i ≤ m( 1 - δ_i/|𝒦_i|) simplifies to (1 - δ_i) for the worst-case scenario where |𝒦_i| = 1 and hence ρ≤ 1 + max_1 ≤ i ≤ m (𝒦_i - δ_i).




  
An Illustrative Example
 Consider there are ten billboard slots 𝒱 = {b_0,b_1,…, b_9}, three tags 𝒰 = {t_0, t_1, t_2} with corresponding influence value as output after applying stochastic greedy approach <cit.> on the billboard, and tag datasets as shown in Table <ref>, <ref>. Next, a bipartite graph 𝒢 and its corresponding 10 × 3 weight matrix is generated. Now, based on the θ-score value described in Section <ref>, a new bipartite graph 𝒢^' with an updated weight matrix is generated. We initialize an empty (Initialize  to   -1) 1-D array 𝒬 to store the allocation as shown in Table <ref>. In the first iteration, the best allocations for the slots to the tags are as follows: {(0 → 2), (1 → 2), (3 → 2), (4 → 2), (5 → 2), (6 → 2), (7 → 2), (8 → 2), (9 → 2)}, i.e., all the slots are allocated to only one tag t_2 and the allocation for the tag to the slot are { (0 → 4), (1 → 4), (2 → 4)}, i.e., slot b_4 is the best match for t_0, t_1 and t_2 and b_4 is matched to tag t_2 as shown in Table <ref>. The edge weight of all the edges from slot b_4 to the tags is set to be 0, and the influence of tag t_2 is set to 0. Next, the matching is performed between tags t_0, t_1 and all the slots except b_4. Similarly, slots b_9 matched with t_1 and b_2 is matched with t_0. After this, all the tag's influence is 0, iteration 1 is completed, and updated allocation is shown in Table <ref>. Still, some slots are unallocated. So, assign the initial influence value for all the tags and repeat the process till improvement in allocation occurs. The final allocation of slots to tags is as follows: {(2 → 0), (4 → 2), (5 → 0), (7 → 2), (8 → 1), (9 → 1)} as shown in Table <ref>. 

















§ EXPERIMENTAL EVALUATION

In this section, we describe the experimental evaluation of the proposed solution approach. Initially, we start by describing the datasets. 


  
Dataset Description.
We use two datasets for our experiments, previously utilized in various trajectory data analytics studies <cit.>. The New York City (NYC) Dataset, collected from April 12, 2012, to February 16, 2013, includes 227,428 check-ins containing user ID, location name, timestamps, and GPS coordinates [<https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page>]. The VehDS-LA (Vehicle Dataset in Los Angeles) consists of 74,170 samples from 15 streets, featuring data like user ID, street name, latitude, longitude, and timestamps [<https://github.com/Ibtihal-Alablani>]. Further, we have created tag datasets from trajectory datasets of NYC and VehDS-LA containing tag names and tag influences to do our experiments. Additionally, we use billboard data from LAMAR [<http://www.lamar.com/InventoryBrowser>], including billboard ID, latitude, longitude, timestamp, and panel size. The NYC dataset contains 716 billboards (1031040 slots), and the LA dataset includes 1483 billboards (2135520 slots).



  
Experimental Setup. All the key parameters used in our experiments are summarized in Table <ref>, and the default settings are highlighted in bold. The parameters k and ℓ denote the number of slots and tags, respectively, whereas ϵ decides the sample set size in the stochastic greedy <cit.> from which maximum influential slots and tags are chosen. The user-defined parameter θ controls the θ-score threshold, and λ represents the maximum distance a slot can influence trajectories. 





All codes are implemented in Python and executed on an HP Z4 workstation with 64 GB memory and an Xeon(R) 3.50 GHz processor. All the proposed and baseline methods are demonstrated for their effectiveness and efficiency. All codes are executed five times, and average results are reported. Due to the anonymity constraint, we are not putting the Github Link of our implementations which we will do during camera ready submission.



  
Goals of our Experiments. 
In this study, we address the following Research Questions (RQ).


  * RQ1: How does the number of matching tags to slots increase if we increase the number of slots and tags selected?

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

  * RQ3: Varying θ-score, how does the number of matched tags and slots vary?

  * RQ4: How does the influence vary before and after allocating tags to slots?




  
Baseline Methods.
 One tag can be assigned to multiple slots in all the baseline methods; however, the opposite is restricted. Now, we will discuss different baseline methods to compare with our proposed approach as follows:




  * Brute-force Method (BM). In this approach, for each billboard slot, we search for the best match in each tag based on the edge weight (e.g., influence value), and tags are assigned to slots.

  * Max Degree Allocation (MDA). At first, tags are sorted in descending order based on the maximum degree. Then, for each slot, check the degree of the tags connected to the slot and the maximum degree tag allocated to that slot.

  * Top-k Slot and Random Tag (TSRT). First, each slot is sorted in descending order based on individual influence value. Next, tags are allocated to the sorted slots randomly.

  * Random Allocation (RA). In this approach, tags are allocated to slots uniformly at random.





  
Experimental Results and Discussions.
This section will discuss the experimental results of the solution methodologies
and address the research questions mentioned in Section <ref>.



  
Tags, Slots Vs. No. of Matching.
Figure <ref>(a,b) and <ref>(g,h) show the effectiveness of the baseline and proposed methods in the NYC and LA datasets, respectively. We have three main observations. With the fixed number of tags (100), when the number of slots varies from 100 to 300, the number of matched tags and slots increase for baseline and proposed methods, as shown in Figure <ref>(a,g) and <ref>(b,h). Second, when we increase the number of slots in the `BM' and `MDA' approaches, all the slots are matched with only one tag, and this happens because there is one most influential tag that has a maximum degree in the bipartite graph. Among the baseline methods, `RA' and `TSRT' perform well. The `OMBM' has a smaller number of matched slots because in every iteration, a tag can only be allocated to a slot if the slot is the best match for a tag, and that tag is also the best for the slot. The `OMBM' approach in the LA dataset has fewer matched slots than `RA' and `TSRT' by 2.29 % to 3% and 0.76% to 2%, respectively. In the NYC dataset, fewer matched slots are around 10.70% compared to the baseline methods. Third, in the NYC dataset, the `OMBM' outperforms all the baseline methods regarding the number of matched tags, while in the LA dataset, the number of matched tags in `OMBM' is less. This happens because in NYC, the θ-score threshold value is very low compared to the LA dataset, and for this reason, the number of edges that remain in the bipartite graph is huge, and more tags are matched.






  
Tags, Slots Vs. Time.
Figure <ref>(c) and <ref>(i) shows the efficiency of our proposed solution, and from this, we have three main observations. First, with the increase in slots, the run time for all the baseline and proposed approaches increases. The time requirement for the stochastic greedy approach is not presented in this paper; however, in NYC, it takes 152632, 152725, 153038, 153046, and 153125 seconds for the number of slots 100, 150, 200, 250, and 300, respectively. In LA run time is 10880, 11039, 11259, 11283, and 11289 seconds for the same parameter setting. Second, the proposed `OMBM' takes more time than the baseline methods because it needs a comparison of both side vertices in the bipartite graph, i.e., the best match for each slot to tags and tags to slots, resulting in significant increases in run time. Third, the `RA' and `TSRT'  are the fastest methods because they need to compare each slot to tags only once.


  
Varying θ value.  Figure <ref>(d,e) and Figure <ref>(j,k) show the impact of varying θ values on the NYC and LA datasets, respectively. We have three main observations. First, the parameter θ controls the pruning criteria in the bipartite graph in Algorithm <ref>, and accordingly, a dense or sparse bipartite graph is generated. Second,  the effectiveness and efficiency are very sensitive to varying θ values in the NYC and LA datasets for the `OMBM', `RA', and `TSRT' when we very billboard slots from 100 to 300. Third, the large θ value will increase the efficiency with worse effectiveness. This happens because when θ increases, the threshold for pruning increases, the graph becomes sparse, and the number of matched slots and tags becomes less.


  
Effectiveness Test. Figure <ref>(f) and Figure <ref>(ℓ) shows the effectiveness of the proposed and baseline methods for  NYC and LA datasets, respectively. We have two main observations. First, stochastic greedy (SG) selects the required number of slots and tags, which returns maximum influence compared to the proposed and baseline methods. This occurs because the output of `SG' is the input of the proposed and baseline methods in the form of a bipartite graph, and after applying the θ-score threshold, some slots and tags are pruned from that graph. Second, our proposed `OMBM' outperforms the baseline methods in allocating the most influential tags to appropriate slots, and among the baseline methods, `RA' and `TSRT' perform well compared to the other baselines.


  
Scalability Test. 
To evaluate the scalability of our method, we vary the number of slots and tags from 100 to 300 and 25 to 125, respectively. As shown in Figure <ref>(c,i), the efficiency in `OMBM' is very sensitive compared to the baseline methods with a fixed number of tags and varying slot values. We observed that runtime also increases in both NYC and LA datasets with the increasing number of slots from 100 to 300 by 3× to 5 × more for the `OMBM' and baseline methods.


  
Additional Discussion. 
Now, we discuss the effect of additional parameters in our experiments. First, we vary the number of slots (k) between 100 and 300 and the number of tags (ℓ) between 25 and 125 to select the required slots and tags. In Figure <ref>, all results are presented for varying k values while keeping the number of tags fixed. Second, in the stochastic greedy approach <cit.>, ϵ determines the size of the random sample subsets. This work uses ϵ = 0.01 as the default setting. Also, we varied the ϵ value from 0.01 to 0.2 and observed that as ϵ increases, the run time of the stochastic greedy approach decreases; however, the quality of the solution degrades, i.e., the influence value decreases. Third, the influence of all the proposed and baseline methods increases when we vary the distance (λ) from 25 meters to 150 meters. Both influence and run-time increase because one slot can influence more trajectories within its influence range. In our experiment, we set the value of λ to 100 meters for both the NYC and LA datasets, as we observed that increasing λ beyond 100 meters resulted in only marginal improvements. This paper does not report the effect of varying λ and ϵ due to space limitations.


§ CONCLUDING REMARKS
 
In this paper, we have studied the Tag Assignment Problem in the context of Billboard Advertisement and proposed a one-to-many bipartite matching-based solution approach. The proposed methodology is illustrated with an example. An analysis of the proposed methodology has been done to understand its time and space requirements as well as its performance guarantee. Experiments with real-world datasets show that our approach outperforms baseline methods in terms of influence. This study can be extended by considering the following directions. Our study does not consider the `zonal influence constraint' which can be considered for future study. The methodology proposed in this paper works for a single advertiser. One important future direction will be to extend our study in multi-advertiser setting.













splncs04


