Top-k spatial aware ads (Record no. 427135)

MARC details
000 -LEADER
fixed length control field 02507nam a22002537a 4500
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION
fixed length control field 230307b |||||||| |||| 00| 0 eng d
041 ## - LANGUAGE CODE
Language code of text/sound track or separate title en.
082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER
Classification number 000
Item number SAV
100 ## - MAIN ENTRY--PERSONAL NAME
Personal name Savla, Virti
245 ## - TITLE STATEMENT
Title Top-k spatial aware ads
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT)
Place of publication, distribution, etc Bengaluru :
Name of publisher, distributor, etc Indian Institute of science ,
Date of publication, distribution, etc 2022 .
300 ## - PHYSICAL DESCRIPTION
Extent 42p.
Accompanying material e-Thesis
Other physical details col. ill. ;
Dimensions 29.1 cm * 20.5 cm
Size of unit 2.507Mb
500 ## - GENERAL NOTE
General note Include bibliographical references and indexes
502 ## - DISSERTATION NOTE
Dissertation note MTech (Res); 2022; Computer science and automation
520 ## - SUMMARY, ETC.
Summary, etc 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.
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Computational Geometry, Voronoi Diagram, Additively Weighted Voronoi Diagram, Spatial Queries
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Computational Geometry
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Voronoi Diagram
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Additively Weighted Voronoi Diagram
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name as entry element Spatial Queries
700 ## - ADDED ENTRY--PERSONAL NAME
Personal name Saladi, Rahul advised
856 ## - ELECTRONIC LOCATION AND ACCESS
Uniform Resource Identifier https://etd.iisc.ac.in/handle/2005/6026
942 ## - ADDED ENTRY ELEMENTS (KOHA)
Koha item type Thesis
Holdings
Withdrawn status Lost status Source of classification or shelving scheme Damaged status Not for loan Home library Current library Date acquired Total Checkouts Barcode Date last seen Koha item type
    Dewey Decimal Classification     JRD Tata Memorial Library JRD Tata Memorial Library 07/03/2023   ET00040 07/03/2023 E-BOOKS

                                                                                                                                                                                                    Facebook    Twitter

                             Copyright © 2023. J.R.D. Tata Memorial Library, Indian Institute of Science, Bengaluru - 560012

                             Contact   Phone: +91 80 2293 2832

Powered by Koha