Abstract—Wireless data broadcast is a promising technique
for information dissemination that leverages the computational
capabilities of the mobile devices, in order to enhance the
scalability of the system. Under this environment, the data are
continuously broadcast by the server, interleaved with some
indexing information for query processing. Clients may then
tune in the broadcast channel and process their queries locally
without contacting the server. Previous work on spatial query
processing for wireless broadcast systems has only considered
snapshot queries over static data. In this paper we propose
an air indexing framework that (i) outperforms the existing
(i.e., snapshot) techniques in terms of energy consumption, while
achieving low access latency, and (ii) constitutes the first method
supporting efficient processing of continuous spatial queries over
moving objects.
Index Terms—Spatial databases, query processing, locationbased
services, wireless data broadcast, air indexes.
I. INTRODUCTION
Mobile devices with computational, storage, and wireless communication
capabilities (such as PDAs) are becoming increasingly
popular. At the same time, the technology behind positioning
systems is constantly evolving, enabling the integration of lowcost
GPS devices in any portable unit. Consequently, new mobile
computing applications are expected to emerge, allowing users
to issue location-dependent queries in a ubiquitous manner. 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.
Spatial queries have been studied extensively in the past, and
numerous algorithms exist (e.g., [10], [11], [21]) for processing
snapshot queries on static data indexed by a spatial access method.
Subsequent methods [22], [24], [30] focused on moving queries
(clients) and/or objects. The main idea is to return some additional
information (e.g., more NNs [22], expiry time [24], validity
region [30]) 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
[22], [30], linear in [24]) and do not include mechanisms for
maintenance of the query results (i.e., when the result expires, a
new query must be issued).
Recent research considers continuous monitoring of multiple
queries over arbitrarily moving objects. In this setting, there is
a central server that monitors the locations of both objects and
K. Mouratidis is with the Singapore Management University. S. Bakiras is
with John Jay College, CUNY. D. Papadias is with the Hong Kong University
of Science and Technology.
queries. The task of the server is to report and continuously
update the query results as the clients and the objects move.
As an example, consider that the data objects are vacant cabs
and the clients are pedestrians that wish to know their k closest
free taxis until they hire one. As the reverse case, the queries
may correspond to vacant cabs, and each free taxi driver wishes
to be continuously informed about his/her k closest pedestrians.
Several monitoring methods have been proposed, covering both
range (e.g., [4], [7], [18]) and kNN (e.g., [19], [26], [29]) queries.
Some of these methods [19], [18], [26], [29] assume that objects
issue updates whenever they move, while others [4], [7] consider
that data objects have some computational capabilities, so that
they inform the server only when their movement influences some
query.
In the aforementioned methods, the processing load at the
server side increases with the number of queries. In applications
involving numerous clients, the server may be overwhelmed by
their queries or take prohibitively long time to answer them.
To avoid this problem, [14] propose wireless data broadcast, a
promising technique that leverages the computational capabilities
of the clients’ mobile devices, and pushes the query processing
task entirely to the client side. In this environment, the server
only monitors the locations of the data objects, but is unaware of
the clients and their queries. The data objects are continuously
broadcast by the server, interleaved with some indexing information.
The clients utilize the broadcast index, called air index, to
tune in the channel only during the transmission of the relevant
data and process their queries locally. Thus, the server load is
independent of the number of clients.
Previous work on location-dependent spatial query processing
for wireless broadcast systems has only considered snapshot
queries over static data. On the other hand, existing spatial
monitoring techniques do not apply to the broadcast environment,
because they assume that the server is aware of the client locations
and processes their queries centrally. In this paper we propose
the Broadcast Grid Index (BGI) method, which is suitable for
both snapshot and continuous queries. Furthermore, BGI extends
to the case that the data are also dynamic. Figure 1 shows an
example of continuous monitoring using BGI. The data objects are
taxis that issue location updates to a central server using unicast
uplink messages. The server processes the location updates, and
continuously broadcasts the object information along with an upto-
date index using a wireless (e.g., 3G) network. Finally, the
interested clients (e.g., mobile devices) listen to the broadcast
channel and process their queries locally. Note that since the
server tasks are independent of the number and the positions
of the clients, this architecture may theoretically support infinite
concurrent clients/queries. On the other hand, high object (e.g.,
taxi) cardinality increases both the server load (for processing the
updates) and the length of the broadcast cycle.
BGI, and broadcast techniques in general, are preferable for
IEEE TRANS. ON MOBILE COMPUTING 2
applications where the number of clients is large with respect to
the number of data objects. As an example [33], Microsoft’s MSN
Direct (msndirect.com) uses broadcasting as an information
dissemination method. Subscribers can receive live information
regarding traffic conditions, stock quotes, gas prices, movie times,
weather reports, etc. Even though location-based queries are not
supported, we believe that this will be the next step, i.e., allowing
the user to filter out unnecessary information using selective
tuning (thus reducing the power consumption).
Server (DBatrao a+d Icnadsetx)
Data olobcjaetcitosn ( tuapxdisa)t eisss uing Clients
Fig. 1. ExammUepnslsiceaagsoetsf BGI
BGI indexes the data with a regular grid. The grid structure
is beneficial in broadcasting environments because the spatial
extents of its cells are implicit, leading to a small index size
(and, thus, less broadcast information). Moreover, a grid supports
fast object updates (as opposed to a more complicated index),
avoiding server overloading in the presence of numerous updates
[15]. In the case of static data, the index information is broadcast
in two parts. The first one contains the cell cardinalities, and
the second one contains the coordinates of the objects falling in
each cell. This allows for efficient query processing at the client
side. For applications where the objects are moving, the server
broadcasts a dirty grid in the beginning of each cycle. The dirty
grid indicates the regions of the data space that have received
updates since the last cycle. The clients re-evaluate their queries
only if the affected regions can potentially invalidate their current
result.
The remainder of the paper is organized as follows. Section
II briefly describes wireless broadcast systems, and overviews
previous work on air indexes. Sections III and IV present the
BGI method for snapshot and continuous kNN queries over static
data, respectively. Section V extends the proposed framework to
dynamic data objects. Range queries are collectively discussed
in Section VI, due to their relative simplicity. Section VII experimentally
evaluates our algorithms and, finally, Section VIII
concludes the paper.
download full report
http://mysmu.edu/faculty/kyriakos/TMC09-BGI.pdf
