Seminars
View all Seminars | Download ICal for this eventTop-k Spatial Aware Ads
Series: M.Tech (Research) Colloquium- ON-LINE
Speaker: Ms. Virti Savla, M.Tech (Research) student, Dept. of CSA
Date/Time: Mar 09 16:00:00
Location: Microsoft Teams - ON-LINE
Faculty Advisor: Prof. Rahul Saladi
Abstract:
Consider an app on a smartphone which displays local business ads. When a user opens the app, then k local business ads need to be displayed (where k would typically be 3 or 5) such that the profit made by the app is maximized. The pricing model needs to consider that (a) each business is willing to bid a different price, and (b) farther the distance of the user on whose smartphone the ad is displayed, the lesser is the price paid by to the app.
<br>
Motivated by such applications, in this work, we design fast algorithms to retrieve top-k ads using spatial and non-spatial information. We refer to them as Top-k Spatial Aware Ads Queries (SAA). In Top-k SAA, we return top-k objects that have the best score, and the scoring function is based on the distance between the object and query point (spatial attribute) and non-spatial attributes. We propose data structures that efficiently preprocess the input data and aid in fast query processing. A simple O(n log n) algorithm sorts the ads based on the scoring function value and returns the top-k ads. In addition, R-Trees can be used with some modification as data structure to answer these queries. All these methods have high worst-case bounds. In this thesis our goal is to obtain better worst-case bounds in terms of space and query time.
We obtain the following results.<br>
<br>
Our first algorithm uses O(nlog n) space and answers the top-k SAA query in O(k log2n) time. <br>
The fast query time is obtained by leveraging the properties of additively weighted Voronoi diagram, along with other supporting data structures. Our second algorithm improves upon the first algorithm by improving the query time to O(k log n), while using the same space. This is achieved via an interesting combination of randomization with a top-2 structure.
<br>
The proposed algorithms have good worst-case theoretical bounds. We demonstrate, through experiments, that our algorithms perform well in terms of query time and space.
<br>
Microsoft teams link:<br>
<a href="Link