A well-studied query type on moving objects is the continuous range query. An interesting and practical situation is that instead of being continuously evaluated, the query may be evaluated at different degrees of continuity, e.g. every 2 seconds (close to continuous), every 10 minutes or at irregular time intervals (close to snapshot). Furthermore, the range query may be stacked under predicates applied to the returned objects. An example is the count predicate that requires the number of objects in the range to be at least Y. The conjecture is that these two practical considerations can help reduce communication costs. We propose a safe region-based solution that exploits these two practical considerations. An extensive experimental study shows that our solution can reduce communication costs by a factor of 9.5 compared to an existing state-of-the-art system.

This paper explores efficient ways to use flash memory to store online analytical processing (OLAP) data. The particular type of queries considered are range queries using the aggregate functions SUM, COUNT and AVG. The asymmetric cost of reads and writes for flash memory gives higher importance to how updates are handled in a flash memory environment. A popular data structure used for answering OLAP range-sum queries is the prefix sum cube. It allows the range-sum query to be answered in constant time. However, updating the prefix sum cube is very expensive. To overcome this, the Δ-tree was proposed by Chun et al. (Dynamic update cube for range-sum queries. Proc. Int. Conf. Very Large Data Bases, San Francisco, CA, USA, 2001, pp. 521–530. Morgan Kaufmann Publisher). The Δ-tree stores all updates to the prefix sum cube in a separate r-tree. This approach worked well for the hard disk where in-place updates are relatively cheap. However, for flash memory where in-place updates are very expensive, the Δ-tree performs very poorly. We take a four-pronged approach to overcome the problem of expensive in-place updates. The first is efficient caching of updates in RAM. The second is writing out whole trees from RAM to flash memory instead of incrementally updating a disk resident tree. The third is we allow users to trade bounded amounts of accuracy for less updates via lossy compression. Finally, we use a quadtree index structure instead of the R-tree. We prove that the quadtree compression problem is NP-complete. A greedy heuristic is proposed to find near optimal solutions in polynomial time. Various experiments were conducted to compare the proposed algorithms against the existing Δ-tree. The results show that our algorithms consistently outperformed Δ-tree by factors of between 10 and 100. This demonstrates the importance of designing flash memory customized algorithms for OLAP range queries. In addition, among our algorithms, the error bound solutions with a small error bound setting significantly outperform the accurate solution in terms of performance for a variety of parameter settings. This indicates that the error bound algorithms offer users an effective trade-off between execution time and accuracy.

Location information is necessarily uncertain when objects are constantly moving. The cost can be high to maintain precise locations at the application server for all the objects while many applications may not need all the costly precision that is technically possible. An interesting question is how to reduce the cost associated with obtaining precise locations while satisfying user requirements. A general technique of maintaining uncertain location information is using a “safe-region” for each object, a region in which the object must be in but it is not known where it exactly is. Location updates are only needed when the object moves out of its safe region, or a user query needs more precise information to answer. This paper uses the same idea for finding an object that is likely to be the nearest neighbor of a query location, a query type termed herein Probabilistic one-of Nearest Neighbor (PoNN) query. An algorithm is described that first tries to answer a given PoNN query with the known safe regions. If this fails, the algorithm selects some objects to ask for their precise locations (called location exposures). An innovative method is used by the algorithm in deciding which objects to expose in order to reduce the total number of exposures. The innovation includes an information gain formulation of the problem and careful probability calculations. The paper details the algorithm and shows an experimental study of the algorithm against more straightforward solutions in a simulated environment.