{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:39:25Z","timestamp":1753439965625},"reference-count":28,"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>Publish\/subscribe (pub\/sub) systems are designed to efficiently match incoming events (e.g., stock quotes) against a set of subscriptions (e.g., trader profiles specifying quotes of interest). However, current pub\/sub systems only support a simple binary notion of matching: an event either matches a subscription or it does not; for instance, a stock quote will either match or not match a trader profile. In this paper, we argue that this simple notion of matching is inadequate for many applications where only the \"best\" matching subscriptions are of interest. For instance, in targeted Web advertising, an incoming user (\"event\") may match several different advertiser-specified user profiles (\"subscriptions\"), but given the limited advertising real-estate, we want to quickly discover the best (e.g., most relevant) ads to display.<\/jats:p>\n          <jats:p>\n            To address this need, we initiate a study of\n            <jats:italic>ranked<\/jats:italic>\n            pub\/sub systems. We focus on the case where subscriptions correspond to interval ranges (e.g, age in [25,35] and salary &gt; $50, 000), and events are points that match all the intervals that they stab (e.g., age=28, salary = $65,000). In addition, each interval has a score and our goal is to quickly recover the top-scoring matching subscriptions. Unfortunately, adapting existing index structures to solve this problem results in either an unacceptable space overhead or a significant performance degradation. We thus propose two novel index structures that are both compact and efficient. Our experimental evaluation shows that the proposed structures provide a scalable basis for designing ranked pub\/sub systems.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453906","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"451-462","source":"Crossref","is-referenced-by-count":36,"title":["Scalable ranked publish\/subscribe"],"prefix":"10.14778","volume":"1","author":[{"given":"Ashwin","family":"Machanavajjhala","sequence":"first","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minos","family":"Garofalakis","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"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"AOL Audience Targeting. www.aolmedianetworks.com\/index.php?id=1936  AOL Audience Targeting. www.aolmedianetworks.com\/index.php?id=1936"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335423"},{"key":"e_1_2_1_3_1","volume-title":"An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems. ICDCS","author":"Banavar G.","year":"1999","unstructured":"G. Banavar , T. Chandra , B. Mukherjee , J. Nagarajarao . An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems. ICDCS 1999 . G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao. An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems. ICDCS 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863975"},{"key":"e_1_2_1_7_1","volume-title":"K. Shim Approximate Query Processing Using Wavelets VLDB","author":"Chakrabarti K.","year":"2000","unstructured":"K. Chakrabarti , M. Garofalakis , R. Rastogi , K. Shim Approximate Query Processing Using Wavelets VLDB 2000 . K. Chakrabarti, M. Garofalakis, R. Rastogi, K. Shim Approximate Query Processing Using Wavelets VLDB 2000."},{"key":"e_1_2_1_8_1","volume-title":"Querying with Intrinsic Preferences. EDBT","author":"Chomicki J.","year":"2002","unstructured":"J. Chomicki . Querying with Intrinsic Preferences. EDBT 2002 . J. Chomicki. Querying with Intrinsic Preferences. EDBT 2002."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217052"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest . Introduction to Algorithms . MIT Press , 1990 . T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"e_1_2_1_11_1","unstructured":"DoubleClick Targeting Filters. www2.doubleclick.com\/dk\/advertisers\/brand\/filters.htm  DoubleClick Targeting Filters. www2.doubleclick.com\/dk\/advertisers\/brand\/filters.htm"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"de Berg M.","year":"2000","unstructured":"M. de Berg , M. van Kreveld , M. Overmars , O. Schwarzkopf . Computational Geometry: Algorithms and Applications . Springer-Verlag , Heidelberg , 2000 . M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Heidelberg, 2000."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958947"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316743"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375677"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/552315.791170"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242647"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1266894.1266940"},{"key":"e_1_2_1_22_1","volume-title":"Jacobsen. Modeling Uncertainties in Publish\/Subscribe Systems. ICDE","author":"Liu H.","year":"2003","unstructured":"H. Liu , H. A. Jacobsen. Modeling Uncertainties in Publish\/Subscribe Systems. ICDE 2003 . H. Liu, H. A. Jacobsen. Modeling Uncertainties in Publish\/Subscribe Systems. ICDE 2003."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/4333"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502050"},{"key":"e_1_2_1_26_1","first-page":"6","author":"Sproull R. L.","year":"1987","unstructured":"R. L. Sproull . Refinements to Nearest-Neighbor Searching in k- Dimensional Trees. Algorithmica 6 , 1987 . R. L. Sproull. Refinements to Nearest-Neighbor Searching in k-Dimensional Trees. Algorithmica 6, 1987.","journal-title":"Dimensional Trees. Algorithmica"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"A. Tomasic C. Garrod K. Popendorf. Symmetric Publish\/Subscribe via Constraint Publication. ExpDB 2006.  A. Tomasic C. Garrod K. Popendorf. Symmetric Publish\/Subscribe via Constraint Publication. ExpDB 2006.","DOI":"10.21236\/ADA469315"},{"key":"e_1_2_1_28_1","unstructured":"Yahoo! Advertising Targeting Options. advertising.yahoo.com\/central\/marketing\/targeting.html  Yahoo! Advertising Targeting Options. advertising.yahoo.com\/central\/marketing\/targeting.html"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:07:27Z","timestamp":1672225647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453906"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453906","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}