Name
Abstract | ||
|---|---|---|
We consider the problem of evaluating an expression over sets.The sets are preprocessed and are therefore sorted, and theoperators can be any of union, intersection, difference,complement, and symmetric difference (exclusive union). Given theexpression as a formula and the sizes of the input sets, we areinterested in the worst-case complexity of evaluation (in terms ofthe size of the sets). The problem is motivated by documentretrieval in search engines where a user query translates directlyto an expression over the sets containing the user-entered words.Special cases of of this problem have been studied [7,6] where theexpression has a restricted form. In this paper, we present anefficient algorithm to evaluate the most general form of a setexpression. We show a lower bound on this problem for expressionsof the form E 1, or E 1-E 2 where E 1 andE 2 are expressions with union, intersection,and symmetric difference operators. We demonstrate that thealgorithm's complexity matches the lower bound in these instances.We, moreover, conjecture that the algorithm works optimally, evenwhen we allow difference and complement operations in E1 and E 2. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92182-0_34 | ISAAC |
Keywords | Field | DocType |
general set expressions,input set,general form,anefficient algorithm,restricted form,e 1-e,form e,worst-case complexity,symmetric difference,symmetric difference operator,exclusive union,search engine,document retrieval,lower bound | Symmetric difference,Discrete mathematics,Combinatorics,Search engine,Expression (mathematics),Of the form,Computer science,Upper and lower bounds,Operator (computer programming),Document retrieval,Conjecture | Conference |
Volume | ISSN | Citations |
5369 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Chiniforooshan | 1 | 118 | 16.38 |
| Arash Farzan | 2 | 136 | 11.07 |
| Mehdi Mirzazadeh | 3 | 13 | 1.74 |