Name
Abstract | ||
|---|---|---|
It is well known that a search engine can significantly benefit from an auxiliary database, which can suggest interpretations of the search query by means of the involved concepts and their interrelationship. The difficulty is to translate abstract notions like concept and interpretation into a concrete search algorithm that operates over the auxiliary database. To surpass existing heuristics, there is a need for a formal basis, which is realized in this paper through the framework of a search database system, where an interpretation is identified as a parse. It is shown that the parses of a query can be generated in polynomial time in the combined size of the input and the output, even if parses are restricted to those having a nonempty evaluation. Identifying that one parse is more specific than another is important for ranking answers, and this framework captures the precise semantics of being more specific; moreover, performing this comparison between parses is tractable. Lastly, the paper studies the problem of finding the most specific parses. Unfortunately, this problem turns out to be intractable in the general case. However, under reasonable assumptions, the parses can be enumerated in an order of decreasing specificity, with polynomial delay and polynomial space. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1807085.1807121 | PODS |
Keywords | Field | DocType |
polynomial delay,specific parses,paper study,polynomial space,search query,polynomial time,concrete search algorithm,search engine,auxiliary database,search database system,database system,search algorithm,database search | Web search query,Search algorithm,Information retrieval,Ranking,Polynomial,Computer science,Theoretical computer science,Heuristics,PSPACE,Parsing,Time complexity,Database | Conference |
Citations | PageRank | References |
15 | 0.76 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ronald Fagin | 1 | 8808 | 2643.66 |
| Benny Kimelfeld | 2 | 1034 | 71.63 |
| Yunyao Li | 3 | 144 | 11.06 |
| Sriram Raghavan | 4 | 1096 | 97.25 |
| Shivakumar Vaithyanathan | 5 | 2518 | 234.40 |