The table looks at complexity for some queries. For inverted lists, the first line is the cost of list traversal and merger, the second the cost of accessing the records. The write cost in each case is the size of the solution.

"d" stands for symmetric difference (more usually ) ). For conjunctive ("and") queries in multilists, we scan the shorter list, looking for occurrences of the other (K,KV) pair. If, as we suggested, inverted list records retain such pairs, we can optionally adopt that strategy in appropriate cases.