{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:21:31Z","timestamp":1672291291330},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>We study the efficient evaluation of top-k queries over data items, where the score of each item is dynamically computed by applying an item-specific function whose parameter value is specified in the query. For example, online retail stores rank items by price, which may be a function of the quantity being queried: \"Stay 3 nights, get a 15% discount on double-bed rooms.\" Similarly, while ranking possible routes in online maps by predicted congestion level, the score (congestion) is a function of the time being queried, e.g., \"At 5PM on a Friday in Palo Alto, the congestion level on 101 North is high.\" Since the parameter---the number of nights or the time the online map is queried, in the above examples---is only known at query time, and online applications have stringent response-time requirements, it is infeasible to evaluate every item-specific function to determine the item scores, especially when the number of items is large. Further, space considerations make it infeasible to pre-compute and store the score of each item for each value of the input parameter. In this paper, we develop a novel technique that compresses the (large) set of item scores for all parameter values by dividing the parameter range into intervals, taking into account the expected query workload. This compressed representation is then used to do top-k pruning of query results. Our experiments show that the proposed techniques are scalable and efficient.<\/jats:p>","DOI":"10.14778\/1453856.1453968","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1044-1055","source":"Crossref","is-referenced-by-count":2,"title":["Efficient top-k processing over query-dependent functions"],"prefix":"10.14778","volume":"1","author":[{"given":"Lin","family":"Guo","sequence":"first","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sihem Amer","family":"Yahia","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghu","family":"Ramakrishnan","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayavel","family":"Shanmugasundaram","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Utkarsh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.09.016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568519"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253302"},{"key":"e_1_2_1_5_1","volume-title":"ICDE","author":"Chen C.","year":"2002","unstructured":"C. Chen , Y. Ling . A Sampling-Based Estimator for Top-K Query . ICDE 2002 . C. Chen, Y. Ling. A Sampling-Based Estimator for Top-K Query. ICDE 2002."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303990"},{"key":"e_1_2_1_7_1","volume-title":"YFilter: Efficient and Scalable Filtering of XML Documents. ICDE","author":"Diao Y.","year":"2002","unstructured":"Y. Diao , P. M. Fischer , M. J. Franklin , R. To . YFilter: Efficient and Scalable Filtering of XML Documents. ICDE 2002 . Y. Diao, P. M. Fischer, M. J. Franklin, R. To. YFilter: Efficient and Scalable Filtering of XML Documents. ICDE 2002."},{"key":"e_1_2_1_8_1","volume-title":"Probabilistic Optimization of Top N Queries. VLDB","author":"Donjerkovic D.","year":"1999","unstructured":"D. Donjerkovic , R. Ramakrishnan . Probabilistic Optimization of Top N Queries. VLDB 1999 . D. Donjerkovic, R. Ramakrishnan. Probabilistic Optimization of Top N Queries. VLDB 1999."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(87)90165-2"},{"key":"e_1_2_1_10_1","volume-title":"Mathematical Programming","author":"Dyer E.","year":"1984","unstructured":"E. Dyer . An O(n) Algorithm for the Multiple-Choice Knapsack Linear Program . Mathematical Programming , 1984 . E. Dyer. An O(n) Algorithm for the Multiple-Choice Knapsack Linear Program. Mathematical Programming, 1984."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375677"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237715"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223841"},{"key":"e_1_2_1_17_1","volume-title":"On Quality of Service Optimization with Discrete QoS Options. IEEE Real Time Technology and Applications Symp.","author":"Lee C.","year":"1999","unstructured":"C. Lee , J. Lehoczky , R. Rajkumar , Y. P. Siewiorek . On Quality of Service Optimization with Discrete QoS Options. IEEE Real Time Technology and Applications Symp. , 1999 . C. Lee, J. Lehoczky, R. Rajkumar, Y. P. Siewiorek. On Quality of Service Optimization with Discrete QoS Options. IEEE Real Time Technology and Applications Symp., 1999."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_20_1","volume-title":"Introduction to Modern Information Retrieval","author":"Salton G.","year":"1983","unstructured":"G. Salton and M. McGill . Introduction to Modern Information Retrieval . McGraw-Hill , 1983 . G. Salton and M. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983."},{"key":"e_1_2_1_21_1","unstructured":"J. Widom S. Ceri. Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996   J. Widom S. Ceri. Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90014-0"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453968","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:00:27Z","timestamp":1672225227000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453968"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453968"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453968","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}