子线性时间内二次查找的数据结构或算法？

有没有办法在不到O(n)时间内基于属性或谓词从大集合中选择子集？

举个简单的例子,假设我有很多作者.每个作者与一组书籍有一对多的关系,与出生城市有一对一的关系.

有没有办法有效地进行查询,例如"获得出生在芝加哥的作者的所有书籍"？我能想到的唯一方法是首先从城市中选择所有作者(快速获得良好的索引),然后迭代它们并累积所有书籍(芝加哥的作者数量O(n)在哪里n).

我知道数据库在某些连接中做了类似的事情,Endeca声称能够使用他们所谓的"记录关系导航"来"快速"执行此操作,但我无法找到有关所使用的实际算法的任何信息.他们的计算复杂性

我并不特别关心确切的数据结构......我很想学习如何在RDBMS,键/值存储库或任何事情中做到这一点.

那么,这种性质的三度或四度请求呢？(给我生活在移民人口超过10,000的城市的作者写的所有书籍.)是否有一个广义的n度算法,它的性能特征是什么？

编辑:

我可能只是非常密集,但我不知道倒排索引建议如何帮助.例如,假设我有以下数据:

DATA
1.  Milton        England
2.  Shakespeare   England
3.  Twain         USA

4.  Milton        Paridise Lost
5.  Shakespeare   Hamlet
6.  Shakespeare   Othello
7.  Twain         Tom Sawyer
8.  Twain         Huck Finn

INDEX
"Milton"         (1, 4)
"Shakespeare"    (2, 5, 6)
"Twain"          (3, 7, 8)
"Paridise Lost"  (4)
"Hamlet"         (5)
"Othello"        (6)
"Tom Sawyer"     (7)
"Huck Finn"      (8)
"England"        (1, 2)
"USA"            (3)

说我对"英国作家的书籍"进行了查询.很快,O(1)通过哈希表,我可以从英格兰得到我的作者名单:(1, 2).但是,为了下一步,为了检索书籍,我必须为每个集合{1, 2}进行另一次O(1)查找:1 -> {4}, 2 -> {5, 6}然后对结果进行联合{4, 5, 6}.

或者我错过了什么？也许你的意思是我应该明确地存储一个链接Book to Country的索引条目.这适用于非常小的数据集.但对于大型数据集,匹配任何可能的查询组合所需的索引数将使索引呈指数级增长.