This paper tackles a major privacy concern in current location-based services where users have to continuously report their locations to the database server in order to obtain the service. For example, a user asking about the nearest gas station has to report her exact location. With untrusted servers, reporting the location information may lead to several privacy threats. In this paper, we present Casper1; a new framework in which mobile and stationary users can entertain location-based services without revealing their location information. Casper consists of two main components, the location anonymizer and the privacy-aware query processor. The location anonymizer blurs the users’ exact location information into cloaked spatial regions based on user-specified privacy requirements. The privacy-aware query processor is embedded inside the location-based database server in order to deal with the cloaked spatial areas rather than the exact location information. Experimental results show that Casper achieves high quality location-based services while providing anonymity for both data and queries.

Joining ranked inputs is an essential requirement for many database applications, such as ranking search results from multiple search engines and answering multi-feature queries for multimedia retrieval systems. We introduce a new practical pipelined query operator, termed NRA-RJ, that produces a global rank from input ranked streams based on a score function. The output of NRA-RJ can serve as a valid input to other NRA-RJ operators in the query pipeline. Hence, the NRA-RJ operator can support a hierarchy of join operations and can be easily integrated in query processing engines of commercial database systems. The NRA-RJ operator bridges Fagin’s optimal aggregation algorithm into a practical implementation and contains several optimizations that address performance issues. We compare the performance of NRA-RJ against recent rank join algorithms. Experimental results demonstrate the performance trade-offs among these algorithms. The experimental results are based on an empirical study applied to a medical video application on top of a prototype database system. The study reveals important design options and shows that the NRA-RJ operator outperforms other pipelined rank join operators when the join condition is an equi-join on key attributes.

The broadcasting of spatial data together with an index structure is an effective way of disseminating data in a wireless mobile environment. Mobile clients requesting data tune into a continuous broadcast only when spatial data of interest and relevance is available on the channel and thus minimize their power consumption. A mobile client experiences latency (time elapsed from requesting to receiving data) and tuning time (the amount of time spent listening to the channel). This paper studies the execution of spatial queries on broadcasted tree-based spatial index structures. The focus is on queries that require a partial traversal of the spatial index, not only a single-path root-to-leaf search. We present techniques for processing spatial queries while mobile clients are listening to a broadcast of the tree. Our algorithms can handle clients with limited memory, trees broadcast with a certain degree of replication of index nodes, and algorithms executed at the clients may employ different data structures. Experimental work on R*-trees shows that these techniques lead to different tuning times and different latencies. Our solutions also lead to efficient methods for starting the execution of a query in the middle of a broadcast cycle. Spatial query processing in a multiple channel environment is also addressed.

Location-aware environments are characterized by a large number of objects and a large number of continuous queries. Both the objects and continuous queries may change their locations over time. In this paper, we focus on continuous k-nearest neighbor queries (CKNN, for short). We present a new algorithm, termed SEA-CNN, for answering continuously a collection of concurrent CKNN queries. SEA-CNN has two important features: incremental evaluation and shared execution. SEA-CNN achieves both efficiency and scalability in the presence of a set of concurrent queries. Furthermore, SEA-CNN does not make any assumptions about the movement of objects, e.g., the objects velocities and shapes of trajectories, or about the mutability of the objects and/or the queries, i.e., moving or stationary queries issued on moving or stationary objects. We provide theoretical analysis of SEA-CNN with respect to the execution costs, memory requirements and effects of tunable parameters. Comprehensive experimentation shows that SEA-CNN is highly scalable and is more efficient in terms of both I/O and CPU costs in comparison to other R-tree-based CKNN techniques.

This paper introduces the hash-merge join algorithm(HMJ, for short); a new non-blocking join algorithm thatdeals with data items from remote sources via unpredictable,slow, or bursty network traffic. The HMJ algorithmis designed with two goals in mind: (1) Minimize thetime to produce the first few results, and (2) Produce joinresults even if the two sources of the join operator occasionallyget blocked. The HMJ algorithm has two phases: Thehashing phase and the merging phase. The hashing phaseemploys an in-memory hash-based join algorithm that producesjoin results as quickly as data arrives. The mergingphase is responsible for producing join results if the twosources are blocked. Both phases of the HMJ algorithmare connected via a flushing policy that flushes in-memoryparts into disk storage once the memory is exhausted. Experimentalresults show that HMJ combines the advantagesof two state-of-the-art non-blocking join algorithms (XJoinand Progressive Merge Join) while avoiding their short-comings.

To provide users with an overview of medical video content at various levels of abstraction which can be used for more efficient database browsing and access, a hierarchical video summarization strategy has been developed and is presented in this paper. To generate an overview, the key frames of a video are preprocessed to extract special frames (black frames, slides, clip art, sketch drawings) and special regions (faces, skin or blood-red areas). A shot grouping method is then applied to merge the spatially or temporally related shots into groups. The visual features and knowledge from the video shots are integrated to assign the groups into predefined semantic categories. Based on the video groups and their semantic categories, video summaries for different levels are constructed by group merging, hierarchical group clustering and semantic category selection. Based on this strategy, a user can select the layer of the summary to access. The higher the layer, the more concise the video summary; the lower the layer, the greater the detail contained in the summary.

The Web is changing the way organizations are conducting their business. Businesses are rushing to provide modular applications, called Web services, that can be programmatically accessed through the Web. Despite the tremendous developments achieved so far, one of the most important, yet untapped potential, is the use of Web services as facilitators for inter-organizational cooperation. This promising concept, known as Web service composition, is gaining momentum as the potential silver bullet for the envisioned Semantic Web. The development of such integrated services has so far been ad hoc, time-consuming, and requires extensive low-level programming efforts. In this paper, we present WebBIS (Web Base of Internet-accessible Services), a generic framework for composing and managing Web services. We combine the object-oriented and active rules paradigms for such a task. We also provide a ontology-based framework for organizing the Web service space. We finally propose a peer-to-peer mechanism for reporting, propagating, and reacting to changes in Web services.

A watermarking algorithm based on image normalization has recently been proposed by Dong and Galatsanos. In this paper, we introduce a different image normalization method for watermarking. Experimental results show that our new image normalization based watermarking algorithm is more robust against the general affine transformation attack. In addition, we show that flipping and aspect ratio information can be obtained using the central moments of both the original image and the watermarked image.

In this paper, we describe an adaptive lossless compression algorithm for color video sequences utilizing backward adaptive temporal prediction and an integer wavelet transform. We exploit two redundancies in color video sequences, specifically spatial and temporal redundancies. We show that an adaptive scheme exploiting the two redundancies has better compression performance than lossless compression of individual image frames. The result of the proposed scheme is compared to current video compression algorithms.

We describe some of the research issues and challenges in image-based location awareness and navigation. We describe two systems being developed at Purdue University as testbeds for our ideas. The main system architecture combines image processing, mobility, wireless communication, and location awareness.

We propose new schemes to introduce error resilience into the compressed video bitstreams for transmission over packet networks. First, we develop an adaptive packetization scheme that prohibits any dependency across packets, for error resilience purposes, while exploiting the dependency within each packet to improve the source coding performance. Secondly, we address a two-layer rate-distortion optimization scheme to serve our packetization method. We also use forward error correction (FEC) coding across packets to provide further error protection. Finally, we present a simplified version of our schemes to make it fully compliant with the current ITU video coding standard - H.263+.

In this paper, we derive and evaluate theoretical rate-distortion performance bounds for scalable video compression algorithms which use a single motion-compensated prediction (MCP) loop. These bounds are derived using rate-distortion theory based on an optimum mean-square error (MSE) quantizer. By specifying translatory motion and using an approximation of the predicted error frame power spectral density, it is possible to derive parametric versions of the rate-distortion functions which are based solely on the input power spectral density and the accuracy of the motion-compensated prediction. The theory is applicable to systems which allow prediction drift, such as the SNR-scalability in MPEG-2, as well as those with zero prediction drift such as the MPEG-4 fine grained scalable standard.

Leaky motion prediction techniques have been developed as a way to trade-off between video coding efficiency and drift error resilience. In this paper, we present a statistical analysis of leaky motion prediction in the presence of channel errors. We assume the encoder has some basic knowledge of the channel such as the channel error pattern and error rate. We derive a closed-form expression of the rate distortion function and find the analytic solution for the leaky motion prediction parameter. Two examples are presented 10 demonstrate the results.