Some Connections between Bounded Query Classes and Non-Uniform Complexity
Amihood AmirRichard BeigelWilliam I. GasarchPublished in: Electron. Colloquium Comput. Complex. (2000)
Keyphrases
- query processing
- database
- query complexity
- response time
- tractable cases
- algebraic operations
- query evaluation
- decision problems
- query formulation
- worst case
- user queries
- space complexity
- user interaction
- class hierarchies
- relevance feedback
- keywords
- computational complexity
- complexity measures
- databases
- query expansion
- class hierarchy
- bounded treewidth
- maintenance cost
- data sources
- complex queries
- communication cost
- retrieval systems
- class labels