• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Top-k Spatial Aware Ads

    View/Open
    Thesis full text (2.507Mb)
    Author
    Savla, Virti
    Metadata
    Show full item record
    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 displayed (where k would typically be 3 or 5) such that the profit made by the app is maximized. The pricing model needs to take into account 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. Motivated by such applications, in this work, we design fast algorithms to retrieve top-k objects using the provided spatial and non-spatial attributes. We refer them as Top-k Spatial Aware Ads Queries (SAA). In Top-k-Saa, the query is user location and we return top-k objects that have the best score. The scoring function is based on the distance between the object and query point (spatial attribute) and non-spatial attributes. We propose algorithms that efficiently preprocess the data using appropriate data structures and aid in fast query processing. A simple O(n log k) algorithm returns the top-k ads based on the scoring function value. We obtain the following results. 1. Our first algorithm uses O(n log n) space and answers the Top-k-Saa query in O(k log2 n) time. The fast query time is obtained by leveraging the properties of additively weighted Voronoi diagram, along with other supporting data structures. 2. Our second algorithm improves upon the first algorithm by improving the query time to O(k log n) in expectation, while using the same space. This is achieved via an interesting combination of randomization with a “top-2” structure.
    URI
    https://etd.iisc.ac.in/handle/2005/6026
    Collections
    • Computer Science and Automation (CSA) [392]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV