{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:15:19Z","timestamp":1761401719452},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>We consider the problem of efficiently indexing Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) Boolean expressions over a high-dimensional multi-valued attribute space. The goal is to rapidly find the set of Boolean expressions that evaluate to true for a given assignment of values to attributes. A solution to this problem has applications in online advertising (where a Boolean expression represents an advertiser's user targeting requirements, and an assignment of values to attributes represents the characteristics of a user visiting an online page) and in general any publish\/subscribe system (where a Boolean expression represents a subscription, and an assignment of values to attributes represents an event). All existing solutions that we are aware of can only index a specialized sub-set of conjunctive and\/or disjunctive expressions, and cannot efficiently handle general DNF and CNF expressions (including NOTs) over multi-valued attributes.<\/jats:p>\n          <jats:p>\n            In this paper, we present a novel solution based on the inverted list data structure that enables us to index arbitrarily complex DNF and CNF Boolean expressions over multi-valued attributes. An interesting aspect of our solution is that, by virtue of leveraging inverted lists traditionally used for ranked information retrieval, we can efficiently return the top-N matching Boolean expressions. This capability enables emerging applications such as\n            <jats:italic>ranked<\/jats:italic>\n            publish\/subscribe systems [16], where only the top subscriptions that match an event are desired. For example, in online advertising there is a limit on the number of advertisements that can be shown on a given page and only the \"best\" advertisements can be displayed. We have evaluated our proposed technique based on data from an online advertising application, and the results show a dramatic performance improvement over prior techniques.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687633","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"37-48","source":"Crossref","is-referenced-by-count":58,"title":["Indexing Boolean expressions"],"prefix":"10.14778","volume":"2","author":[{"given":"Steven Euijong","family":"Whang","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Hector","family":"Garcia-Molina","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Chad","family":"Brower","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]},{"given":"Jayavel","family":"Shanmugasundaram","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]},{"given":"Erik","family":"Vee","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]},{"given":"Ramana","family":"Yerneni","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santa Clara, CA"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301326"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055488"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102120.1102142"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247620"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277837"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/215206.215329"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863975"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0094-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/857076.857078"},{"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.1016\/0004-3702(82)90020-0"},{"key":"e_1_2_1_13_1","volume-title":"Expert Systems: Principles and Programming","author":"Giarratano J. C.","year":"1998","unstructured":"J. C. Giarratano and G. D. Riley . Expert Systems: Principles and Programming , Third Edition : Principles and Programming. Course Technology , 3 edition, February 1998 . J. C. Giarratano and G. D. Riley. Expert Systems: Principles and Programming, Third Edition: Principles and Programming. Course Technology, 3 edition, February 1998."},{"key":"e_1_2_1_14_1","unstructured":"Google Advertising. http:\/\/www.google.com\/ads\/.  Google Advertising. http:\/\/www.google.com\/ads\/."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847241"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453906"},{"key":"e_1_2_1_17_1","unstructured":"Microsoft Advertising. http:\/\/advertising.microsoft.com\/.  Microsoft Advertising. http:\/\/advertising.microsoft.com\/."},{"key":"e_1_2_1_18_1","first-page":"42","volume-title":"Proceedings of the 6th National Conference on Artificial Intelligence","author":"Miranker D. P.","year":"1987","unstructured":"D. P. Miranker . TREAT : A better match algorithm for AI. In K. S. H. Forbus, editor , Proceedings of the 6th National Conference on Artificial Intelligence , pages 42 -- 47 , Seattle, WA , July 1987 . Morgan Kaufmann. D. P. Miranker. TREAT: A better match algorithm for AI. In K. S. H. Forbus, editor, Proceedings of the 6th National Conference on Artificial Intelligence, pages 42--47, Seattle, WA, July 1987. Morgan Kaufmann."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974755"},{"key":"e_1_2_1_20_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell S. J.","year":"2003","unstructured":"S. J. Russell and Norvig. Artificial Intelligence: A Modern Approach ( Second Edition). Prentice Hall , 2003 . S. J. Russell and Norvig. Artificial Intelligence: A Modern Approach (Second Edition). Prentice Hall, 2003."},{"key":"e_1_2_1_21_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten I. H.","year":"1999","unstructured":"I. H. Witten , A. Moffat , and T. C. Bell . Managing Gigabytes: Compressing and Indexing Documents and Images . Morgan Kaufmann Publishers , San Francisco, CA , 1999 . I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers, San Francisco, CA, 1999."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142520"},{"key":"e_1_2_1_23_1","unstructured":"Yahoo! Advertising. http:\/\/advertising.yahoo.com\/.  Yahoo! Advertising. http:\/\/advertising.yahoo.com\/."},{"key":"e_1_2_1_24_1","volume-title":"CIDR","author":"Yalamanchi A.","year":"2003","unstructured":"A. Yalamanchi , J. Srinivasan , and D. Gawlick . Managing expressions as data in relational database systems . In CIDR , 2003 . A. Yalamanchi, J. Srinivasan, and D. Gawlick. Managing expressions as data in relational database systems. In CIDR, 2003."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/176567.176573"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:23:13Z","timestamp":1672226593000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687633"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687633","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}