The present invention is directed to a system and a method for evaluating a plurality of moving queries over moving objects. The method, which can be embodied in a computer readable medium containing computer readable code, constructs motion-adaptive bounding boxes around the objects and queries and indexes the objects and queries based upon the bounding boxes. Predictive query results are used to optimize the evaluation of the moving queries. The bounding boxes vary in size and shape depending on the speed and motion direction of the objects and queries. The system of the present invention includes the moving objects and queries, each having an associated motion-adaptive bounding box. The system also provides for a monitoring system capable of monitoring the location and motion of the moving objects and moving queries and of evaluating the moving queries. The monitoring system includes a motion-adaptive query index and a motion-adaptive object index.