Continuous Monitoring of Spatial Queries in Wireless Broadcast Environments

Modules:
1. Network Module
2. Wireless Broadcasting
3. Air Indexing
4. Spatial Query Processing
5. Continuous kNN Queries

Module Description:

1. Network Module

Client-server computing or networking is a distributed application architecture that partitions tasks or workloads between service providers (servers) and service requesters, called clients. Often clients and servers operate over a computer network on separate hardware. A server machine is a high-performance host that is running one or more server programs which share its resources with clients. A client also shares any of its resources; Clients therefore initiate communication sessions with servers which await (listen to) incoming requests.







2. Wireless Broadcasting

The transmission schedule in a wireless broadcast system consists of a series of broadcast cycles. Within each cycle the data are organized into a number of index and data buckets. A bucket (which has a constant size) corresponds to the smallest logical unit of information, similar to the page concept in conventional storage systems. A single bucket may be carried into multiple network packets (i.e., the basic unit of information that is transmitted over the air). However, they are typically assumed to be of the same size (i.e., one bucket equals one packet).

3. Air Indexing

The main motivation behind air indexes is to minimize the power consumption at the mobile client. Although in a broadcast environment, the uplink transmissions are avoided, receiving all the downlink packets from the server is not energy efficient. For instance, the Cabletron 802.11 network card (wireless LAN) was found to consume 1,400 mW in the transmit, 1,000 mW in the receive, and 130 mW in the sleep mode. Therefore, it is imperative that the client switches to the sleep mode (i.e., turns off the receiver) whenever the transmitted packets do not contain any useful information.







4. Spatial Query Processing

Spatial queries have been studied extensively in the past and numerous algorithms exist for processing snapshot queries on static data indexed by a spatial access method. Subsequent methods focused on moving queries (clients) and/or objects. The main idea is to return some additional information (e.g., more NNs, expiry time, and validity region) that determines the lifespan of the result. Thus, a moving client needs to issue another query only after the current result expires. These methods focus on single query processing, make certain assumptions about object movement (e.g., static in, linear in), and do not include mechanisms for maintenance of the query results (i.e., when the result expires, a new query must be issued).

The possibility of broadcasting spatial data together with a data partitioning index. They present several techniques for spatial query processing that adjust to the limited memory of the mobile device. The authors evaluate their methods experimentally for range queries (using the R-tree as the underlying index) and illustrate the feasibility of this architecture.


5. Continuous kNN Queries

Consider, for instance, a user (mobile client) in an unfamiliar city, who would like to know the 10 closest restaurants. This is an instance of a k nearest neighbor (kNN) query, where the query point is the current location of the client and the set of data objects contains the city restaurants. Alternatively, the user may ask for all restaurants located within a certain distance, i.e., within 200 meters. This is an instance of a range query.