<p>It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values). </p>

<p>On the other hand, if we use  a tree based data structure, we may be able to improve the run-time from the $k \cdot Q(n)$ time to perform $k$ queries that each individually take $Q(n)$ time. For example, if the keys are clustered closely together, and we use a finger-search tree. (See e.g. <a href="http://www.cs.au.dk/~gerth/papers/finger05.pdf">Brodal's chapter on finger search trees</a>).</p>

<p>If you are dealing with sequential files, then
<a href="http://libres.uncg.edu/ir/uncg/f/P_Palvia_Expressions_1985.pdf">Expressions for Batched Searching of Sequential and Hierarchical Files</a> is a relevant reference.</p>

<p>If you are concerned with the I/O cost of accessing an external database, then perhaps <a href="http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF10/buffertree.pdf">the buffer tree</a> is a more relevant reference.</p>

CC BY-SA 3.0
2012-03-27T19:10:13.657Z
That s very interesting Joe ! thanks ! - [the buffer tree reference is especially nice]
AJed
CC BY-SA 3.0
2012-03-27T19:00:14.607Z
2012-03-27T19:00:14.607Z
Joe
<p>I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a distinct key. We are looking for the value of each key (that is, $v(q _i)$. Noticing that, a set of keys $Q&#39; \subset Q$ <em>may</em> have the same corresponding value [that is, for each $q _i, q _j \in Q' \subset Q, v(q _i) = v (q _j)$].</p>

<p><strong>What is the minimum time complexity to search for the values of all keys in $Q$?</strong></p>

<p><strong>Can it be less then searching individually and sequentially for each $q \in Q$?</strong></p>

<hr>

<p>N.B: I noticed most research in this field considered <em>sequential files</em>. But what would the answer be if the files was indexed using hash table or B+-tree ? </p>

<p>Example: the database D can be a Domain Name Server .. the queries may be any number of url's ? url's are the keys and the value are the IP addresses .. Some URL's may have the same value ... for instance, google.com and goolgle.com returns the same IP ... [hypothetically]  </p>

<lower-bounds><time-complexity><dc.parallel-comp><db.databases>
Lower bounds on batched query search
AJed
# Lower bounds on batched query search

(Asked by: username_0 on 2012-03-27)

I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q\_1, ..., q \_k\}$, where each $q\_i$ is a distinct key. We are looking for the value of each key (that is, $v(q \_i)$. Noticing that, a set of keys $Q' \subset Q$ *may* have the same corresponding value [that is, for each $q \_i, q \_j \in Q' \subset Q, v(q \_i) = v (q \_j)$].

**What is the minimum time complexity to search for the values of all keys in $Q$?**

**Can it be less then searching individually and sequentially for each $q \in Q$?**

---

N.B: I noticed most research in this field considered *sequential files*. But what would the answer be if the files was indexed using hash table or B+-tree ?

Example: the database D can be a Domain Name Server .. the queries may be any number of url's ? url's are the keys and the value are the IP addresses .. Some URL's may have the same value ... for instance, google.com and goolgle.com returns the same IP ... [hypothetically]

**Tags:** lower-bounds, time-complexity, dc.parallel-comp, db.databases


---

## 1 answers

### Answer by username_1 on 2012-03-27. Score: 6

It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values).

On the other hand, if we use a tree based data structure, we may be able to improve the run-time from the $k \cdot Q(n)$ time to perform $k$ queries that each individually take $Q(n)$ time. For example, if the keys are clustered closely together, and we use a finger-search tree. (See e.g. [Brodal's chapter on finger search trees](http://www.cs.au.dk/~gerth/papers/finger05.pdf)).

If you are dealing with sequential files, then
[Expressions for Batched Searching of Sequential and Hierarchical Files](http://libres.uncg.edu/ir/uncg/f/P_Palvia_Expressions_1985.pdf) is a relevant reference.

If you are concerned with the I/O cost of accessing an external database, then perhaps [the buffer tree](http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF10/buffertree.pdf) is a more relevant reference.

> **Comments:**
> **username_0**: That s very interesting username_1 ! thanks ! - [the buffer tree reference is especially nice]  

---

