DC Field | Value | Language |
---|---|---|
dc.contributor.author | Whang, Steven Euijong | ko |
dc.contributor.author | Garcia-Molina, Hector | ko |
dc.contributor.author | Brower, Chad | ko |
dc.contributor.author | Shanmugasundaram, Jayavel | ko |
dc.contributor.author | Vassilvitskii, Sergei | ko |
dc.contributor.author | Vee, Erik | ko |
dc.contributor.author | Yerneni, Ramana | ko |
dc.date.accessioned | 2019-04-16T03:50:35Z | - |
dc.date.available | 2019-04-16T03:50:35Z | - |
dc.date.created | 2018-03-29 | - |
dc.date.created | 2018-03-29 | - |
dc.date.issued | 2009-08 | - |
dc.identifier.citation | 35th International Conference on Very Large Data Bases, VLDB 2009, pp.37 - 48 | - |
dc.identifier.issn | 2150-8097 | - |
dc.identifier.uri | http://hdl.handle.net/10203/260320 | - |
dc.description.abstract | 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. 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 ranked 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. | - |
dc.language | English | - |
dc.publisher | The VLDB Endowment | - |
dc.title | Indexing boolean expressions | - |
dc.type | Conference | - |
dc.identifier.scopusid | 2-s2.0-77954800255 | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 37 | - |
dc.citation.endingpage | 48 | - |
dc.citation.publicationname | 35th International Conference on Very Large Data Bases, VLDB 2009 | - |
dc.identifier.conferencecountry | FR | - |
dc.identifier.conferencelocation | Lyon | - |
dc.identifier.doi | 10.14778/1687627.1687633 | - |
dc.contributor.localauthor | Whang, Steven Euijong | - |
dc.contributor.nonIdAuthor | Garcia-Molina, Hector | - |
dc.contributor.nonIdAuthor | Brower, Chad | - |
dc.contributor.nonIdAuthor | Shanmugasundaram, Jayavel | - |
dc.contributor.nonIdAuthor | Vassilvitskii, Sergei | - |
dc.contributor.nonIdAuthor | Vee, Erik | - |
dc.contributor.nonIdAuthor | Yerneni, Ramana | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.