RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient.

Arne Andersson Peter Bro Miltersen Søren Riis Mikkel Thorup

Published in: FOCS (1996)

Keyphrases

worst case
lower bound
log log
keywords
upper bound
query processing
np hard
response time
query expansion
user interaction
database
data sources
computational complexity
relevance feedback
data structure
query evaluation
user queries
vector space
keyword search