THE IMPACT OF FILTERING ON
SPATIAL CONTINUOUS QUERIES
Thomas Brinkhoff
Institute for Applied Photogrammetry and Geoinformatics (IAPG) FH Oldenburg/Ostfriesland/Wilhelmshaven (University of Applied Sciences) Ofener Str. 16/19, D-26121 Oldenburg, Germany
tbrinkhoff@https://www.doczj.com/doc/d43657107.html,
ABSTRACT
Spatiotemporal database systems (STDBS) are primarily motivated by applica-tions tracking and presenting moving objects. Such applications must be kept informed about new, relocated, or removed objects fulfilling a given query condi-tion. Consequently, a STDBS must inform its clients about these updates. Such queries are called continuous queries. The volume and frequency of transmissions is influenced by technical restrictions like the computing power of a client, the spatial distances a client is able to distinguish, and the maximum speed and throughput of the network connection. In this paper, filtering algorithms are pre-sented that allow reducing the number of transmitted update operations. Two con-tradicting optimization goals can be observed: First, to reduce the memory re-quirements of the STDBS for buffering these operations and, second, to reduce the volume and frequency of transmissions. However, delaying or even not transmit-ting updates to a client may decrease the quality of the query result. In an experi-mental investigation, this impact is examined for the presented algorithms. Keywords: spatiotemporal database systems, moving objects, continuous queries 1 Introduction
Spatiotemporal database systems(STDBS) are an enabling technology for applica-tions such as Geographic Information Systems (GIS), environmental information systems, and multimedia. Especially, the storage and the retrieval of moving ob-jects are central tasks of a STDBS. The investigation of spatiotemporal database systems is especially motivated by applications, which require to track and to visualize moving objects. Many of these applications originate from the field of traffic telematics, which combines techniques from the areas of telecommunica-tion and computer science in order to establish traffic information and assistance services. Such applications require the management of moving objects, e.g., of vehicles of a fleet (Wolfson et al., 1999) (Brinkhoff, 1999).
An important issue is the support of mobile and location-based applications. Mo-bile applications refer to locations and require the transmission of spatial or spatio-temporal data. The appearance of mobile applications has also an impact on the devices used for presenting data: Personal digital assistants (PDAs) or mobile telephones are used as clients. However, the computing power of such devices is
rather restricted compared to traditional computers. In addition, speed and throughput of wireless networks are subject to large variations.
The work presented in this paper is motivated by the two trends mentioned before. Applications tracking and presenting moving objects require to be kept informed about new, relocated, or removed objects fulfilling a given query condition. Con-sequently, a STDBS must inform its clients about such update operations. The query causing this process is called continuous query (Terry et al., 1992). The result set of a spatial continuous query is influenced by the update operations occurring in the database and by a given query condition that consists of spatial predicates (e.g., a window query) and optionally of non-spatial predicates defining further selections (e.g., a selection of vehicles that are cars or motorbikes). For mobile applications, the processing capabilities of the client must be also taken into account. Typical technical restrictions concern the computing power of the client, the spatial distances the client is able to (or wants to) distinguish, and the maximum speed and throughput of the connection between the STDBS and the client. Therefore, it is not advisable to transmit the complete result of a continuous query. Instead, a reasonable filtering must be performed. Two contradicting opti-mization goals can be observed: First, to reduce the memory requirements of the STDBS for buffering the operations and, second, to reduce the volume and fre-quency of transmissions to the client. However, delaying or even not transmitting update operations to a client may decrease the quality of the query result. There-fore, algorithms for filtering the result of a spatial continuous query are required that maintain a sufficient quality of the query result.
The paper starts with a short definition of the model used for describing moving objects and presents the main properties of spatial continuous queries. The second section introduces a first algorithm for processing continuous queries. More so-phisticated algorithms are presented and analyzed in the third section. They limit the memory requirements of the STDBS and reduce the volume and frequency of the transmissions. Then, the quality of the query results and other properties of these algorithms are experimentally investigated. Finally, the paper concludes with a summary and an outlook on future work.
2 Continuous Queries
2.1 Definitions
The following discussion assumes a STDBS, which stores the positions and other attributes of moving objects. In a temporal database, valid time and transaction time are distinguished. The valid time describes the time when a record is valid in the modeled reality. The transaction time is the time when a record is committed in the database system.
In the following, it is assumed that a moving object obj has an identifier obj.id. The object is described by a sequence of records obj i (i∈N). Each record consists of a spatial location obj i.loc (short: loc i), of a time stamp obj i.time (short: time i) giving the beginning of the valid time, of a time stamp obj i.trTime (short: trTime i)
giving the transaction time, and of non-spatiotemporal attributes obj i .attr (short: attr i ). A time stamp t is represented by a natural number (t ∈N ). If the records obj i und obj i+1 exist, the valid time of record obj i corresponds to the interval [time i , time i+1). If no record obj i+1 exists for a record obj i , the record obj i is the current state of the corresponding moving object from the point of view of the STDBS. Furthermore, a final record obj i may exist with i > j for all records obj j of this moving object. It indicates the end of the lifetime of the object. In order to sim-plify the discussion, we assume that time i ≤ trTime i holds.
We distinguish three basic types of updates concerning a moving object: 1. the insertion of a new object, 2. the modification of an existing object, and 3. the dele-tion of an existing object. With respect to the query condition of a distinct client, the type of an (modifying) update operation may change (Brinkhoff and Weit-k?mper, 2001). For example, the position of an object representing a vehicle has been modified in the database. If this vehicle leaves the query window of a client, this modification must be reclassified to a deletion for this client. Table 1 gives a summary of such reclassifications. The vehicle leaving the window is represented by the (yes, no) row and the modification column. I1 and D1 denote updates that do not need to be reclassified. I2 and D2 denote reclassified updates.
fulfills query condition? original type of operation:
insertion deletion modification
previous record obj i-1 current record obj i reclassified type of operation:
no no - - - no yes insertion (I1) . / . insertion (I2) yes no . / . deletion (D1) deletion (D2) yes yes . / . . / . modification (M)
Table 1: Reclassification of update operations.
The reclassified type of an update operation may also determine the interest of a client in this operation: Deletions are typically of high interest . The same holds for insertions. For modifications, the situation may be different. In general, the num-ber of modifications considerably exceeds the number of other operations. There-fore, it may be tolerable to skip some modifications, especially if the distance to the last reported position is small or the topology has not changed (e.g., the car is still on the motorway or is still in the same county). Then, the result set received by a client is not identical to the complete result set of a continuous query. In contrast to the assumptions done in queuing theory, not only a delaying but also a skipping of operations is allowed. Another restriction concerns the database: the STDBS cannot store a refection of all update operations each client has received according to its individual query condition – that would be much too expensive.
2.2 A first algorithm
If a moving object is changed in the database, the STDBS will determine the af-fected clients and will reclassify the type of the update operation with respect to the query conditions of the concerned clients. If the update is of interest for a dis-
tinct client, the STDBS will call the procedure collectUpdates (see figure 1). In general, the new update operation is added to the set client.ops, which collects the operations intended for the client. newOp consists of the identifier of the corre-sponding object (objId), of the current object representation (curr), and the reclas-sified type of the operation (opType). If an element concerning the same object already exists in the set client.ops, this element will be updated. Depending on the former and the current type of the operation, the element will be deleted or modi-fied. collectUpdates guarantees that for each object at most one operation exists in the set client.ops.
The function computeTransmission determines the set of operations to be sent to a client. The STDBS calls this function before the updates are transmitted to a client. This first solution returns client.ops as result and empties the set then.
void collectUpdates (Client client, Operation newOp) {
// Adds an update operation newOp to a collection of a client.
// case 1: the operation concerns no object referenced in the set
? {op.objId | op ∈ client.ops})
(newOp.objId
if
∪ {newOp};
client.ops
=
client.ops
// case 2: the operation concerns an object referenced in the set {
else
// determine the stored operation
Operation oldOp = op∈client.ops with op.objId == newOp.objId;
// if necessary, delete the operation from the set
((oldOp.opType∈{I1,I2}) && (newOp.opType∈{D1,D2}))
if
client.op = client.op \ {oldOp};
// or update the type of operation and the description
((oldOp.opType∈{D1,D2}) && (newOp.opType∈{I1,I2})) {
else
if
oldOp.opType = M; // delete plus insert becomes modification
=
newOp.curr;
oldOp.curr
}
// or update only the description
newOp.curr;
=
else
oldOp.curr
}}
Set computeTransmission (Client client) {
// Determines the update operations to be sent to a client.
Set sendOps = client.ops;
?;
client.ops
=
sendOps;
return
}
Figure 1: First version of the filtering algorithm.
An open question concerns the time when a set of updates should be transmitted to a client. One solution is a transmission as soon as the transaction time has ex-ceeded a given period ?t. In this case, the size of the set client.ops is only limited by the number of updates that a STDBS is able to process in the given period ?t. This number can be quite large. Assuming a STDBS used by many clients in par-allel, this results in huge memory requirements and bad scalability. Furthermore, the performance of the client or of the network connection to the client may re-strict the size of the set of operations that can be processed during a given period. By reducing the period ?t, the first disadvantage may be reduced. However, the sum of transferred operations would increase. The reason for this increase is that
the probability of replacing operations in the set client.ops decreases with shorter periods ?t. Time restrictions, which require that a minimum period between two
data transmissions, are another rationale against reducing ?t. The same argumentation will hold if the transmission is triggered by the size of the set cli-
ent.ops. Only in the case of ?t=1, the algorithm computes the complete result of a continuous query. Otherwise, the transmission of operations may be delayed. By replacing outdated entries, the result set may be smaller than the complete result.
We can observe two contradicting optimization goals: First, to reduce the memory requirements of the STDBS for buffering update operations and, second, to reduce
the volume and frequency of transmissions to the client. In the following, we try to balance between these two objectives by modifying the presented algorithm.
3 Improving the Algorithm
According to (Brinkhoff and Weitk?mper, 2001), table 2 summarizes the parame-
ters and functions, which can be used for describing the restrictions of a client. These parameters are used by the algorithms presented in this section.
parameter description maxOps The maximum number of update operations that can be sent to
a client by one transmission.
minOps The minimum number of operations reasonable to be sent to a
client by one transmission; it holds: minOps≤maxOps.
minPeriod The minimum period between two transmissions to a client.
thr A threshold for the measure of interest (see section 3.1).
function description intr(ob prev,obj curr)The measure of interest for operations that are not of high
interest.
isRelevant(ob prev,obj curr) Boolean function determining whether an update operation is
relevant for a client or not.
Table 2: Parameters and functions used for describing the restrictions of a client.
3.1 Algorithm Observing the Restrictions of a Client
An algorithm, which determines the next update operations to be sent to a client
for performing the continuous query, should observe the restrictions and measures described above. Like in section 2.2, the algorithm presented in figure 2 consists
of the operations collectUpdates and computeTransmission.
The procedure collectUpdates is similar to the first version. A previous object description (prev) and an attribute time have been added to the elements of the set client.ops. The parameter newOp also includes an attribute prev representing the previous object representation in the database. A STDBS should be able to deter-
mine newOp.prev efficiently. For a new element in the set client.ops, the attribute
time is generally set to the valid time of newOp.prev.An exception from this rule
is the insert operation I1. Then, time is set to the valid time of the new object. If an element concerning the same object already exists in the set client.ops, this ele-
ment will be updated. Note that the attribute time is not changed in this case. It still represents the time when the operation was inserted into client .ops .
void collectUpdates (Client client, Operation newOp) {
// Adds an update operation newOp to a collection of a client .
// case 1: the operation concerns no object referenced in the set if (newOp.objId ? {op.objId | op ∈ client.ops}) {
newOp.time = (newOp.opType == I1) ? newOp.curr.time : newOp.prev.time; client.ops = client.ops ∪ {newOp};
}
// case 2: the operation concerns an object referenced in the set, // the attribute oldOp.time remains unchanged!
else {
// determine the operation
Operation oldOp = op ∈client.ops with op.objId == newOp.objId;
// if necessary delete the operation from the set
if ((oldOp.opType ∈{I1,I2}) && (newOp.opType ∈{D1,D2}))
client.op = client.op \ {oldOp};
// or update the type of operation and the description
else if ((oldOp.opType ∈{D1,D2}) && (newOp.opType ∈{I1,I2})) {
oldOp.opType = M; // delete plus insert becomes modification oldOp.curr = newOp.curr;
}
// or update only the description
else oldOp.curr = newOp.curr;
} }
Set computeTransmission (Client client, Time currTime) {
// Determines the updates to be sent to a client . currTime : the current time
// initialize the set of operations to be sent
Set sendOps = ?;
// if the period is too short: return nothing
if (currTime-client.timePrev) < client.minPeriod)
return sendOps;
// determine the operations of high interest
Set o1 = {op ∈client.ops | (op.opType)∈{I1,I2,D1,D2}) ∨
(intr(op.prev,op.curr)≥client.thr)) ∧ isRelevant(op.prev,op.curr) }; if ( |o1| > client.maxOps )
sendOps = {op ∈o1| client.maxOps elements having the oldest time stamps}; else
sendOps = o1;
// determine further operations of interest
if (|sendOps| < client.minOps) {
Set o2 ={op ∈client.ops ∧op ?sendOps|isRelevant(op.prev,op.curr)}; sendOps = sendOps ∪ {op ∈o2| client.minOps-|o1| elements
having the highest intr(op.prev,op.curr) }; }
// final actions
if (sendOps ≠ ?)
client.prevTime = currTime;
client.ops = client.ops \ sendOps;
return sendOps;
}
Figure 2: Filtering algorithm observing the restrictions of a client.
The function computeTransmission has been completely modified: it deter-mines the set of operations to be sent to the client observing the parameters and functions of table 2. First, the algorithm tests whether the time interval between the time, when update operations were sent to the client last, and the current time is sufficient. Then, a set of operations is determined. This set contains all opera-
tions of high interest and the operations whose measure of interest exceeds a given threshold thr. The elements are ranked according to the attribute time, which was determined by the operation collectUpdates. If necessary, this sequence will be cut by maxOps. If it is reasonable, further operations are added. The selected elements form the result of the function computeTransmission. These elements are removed from the set client.ops.
Note that non-relevant update operations are not removed from the set ops. There are two reasons for that. The first reason is to accumulate the movement. The STDBS cannot derive the last object representation obj last sent to a client without explicitly storing this information; the attribute prev of a new update operation newOp is often not identical to obj last. Furthermore, keeping non-relevant opera-tions in the set allows preserving the value of the attribute time. Otherwise, a se-quence of non-relevant movements would repeatedly change the value of time. In consequence, the ranking of this operation within other operations would stay on a low level. By keeping the first value of time, the ranking of the operation is im-proved over the time. Figure 3 illustrates these effects.
t i
obj
0 at (20,30)
t i+1
obj
1
at (25,15)
t i+2
obj
2
at (30,10)
t i+3
obj
3
at (35,15)
database time:
update not sent:
(obj
0, t
i
, I1)
inserted into ops (obj
1
, t
i
, I1) sent
and removed from
ops
update not sent:
(obj
2
, t
i+1
, U1)
inserted into ops
(obj
3
, t
i+1
, U1) sent
and removed
from ops
Figure 3: Illustration of setting and keeping the attribute time.
3.1.1 Discussion of the time complexity
The filtering algorithm depicted in figure 2 observes the parameters of table 2.
However, its design has not considered any optimizations for reducing the time or
the space complexity of the algorithm. Let us first discuss time complexity.
We can distinguish two different rankings using the attribute op.time (op∈client.ops) and the function intr computing the measure of interest. There-fore, we consider the two subsets ops1 and ops2 separately. ops1 consists of all
operations of high interest plus the relevant operations of lower interest. ops2 con-
sists of the other operations of lower interest. The assignment of an operation to
one of these two subsets will only change, if the object description op.curr is changed. This is unproblematic because in this case the algorithm collectUp-dates is called, which can handle this case. The ordering of ops1 is trouble-free because the attribute op.time will not be changed and the property isRelevant is
static as long as the corresponding object op.curr is not changed. The same holds
for the ordering of ops2 because the result of the function intr does not change
without changing op.curr.
The operations performed on the sets consists (a) of the insertion of elements, (b)
of the search for an existing element (and its deletion) and (c) of the retrieval (and
deletion) of the first k elements according to the ordering of the elements of ops1
and ops2, respectively. For supporting these operations, the following options exist (n denotes the number of elements in client.ops):
? Operation (b) determines the existence of an operation in the set by using the identifier of the corresponding object. For an efficient search, we must know the value of the attribute, which defines the ordering: the valid time of the ob-ject representation originally inserted into client.ops and the object representa-tion inserted before into client.ops. However, the original valid time is un-known for the calling STDBS. Therefore, the effort for performing operation
(a) is O(log(n)) and for operation (c) O(maxOps*log(n)) if a balanced search
tree according to the orders of ops1 and ops2 is used. However, the worst-case search time of (b) will be of O(n) in this case.
? Organizing the sets by two redundant balanced search trees allows performing the operations (a) and (b) in O(log(n)) and operation (c) in O(maxOps*log(n)).
However, each update operation must be performed twice and the space re-quirements are considerably increased by keeping two search trees.
3.1.2 Discussion of the space complexity
The number of elements in the set client.ops is only limited by the number of all current valid moving objects fulfilling the spatial and other non-spatial query conditions. This number is denoted by N; it holds: n≤N. In the worst case for each client performing the continuous query, the status of all moving objects ful-filling the query condition at the beginning or in the meantime must be recorded in the set client.ops. Then, n will be quite large. Assuming a STDBS used by many clients in parallel, that means a huge memory and maintenance overhead. There-fore (and because of the time complexity of the algorithm), it is necessary to re-duce this overhead by limiting the size of the set client.ops. This is the topic of the next section.
3.2 Restricting the space complexity
We modify the presented algorithm by restricting its memory demands using a parameter maxSize. The minimum value of maxSize is determined by the parame-ter maxOps: maxSize≥maxOps. However, a higher value of maxSize would im-prove the quality of the results of the continuous query. If we restrict the size of the set, we will need a replacement strategy, which is required for a new important operation in the case that the set is full. The obvious replacement strategy is to remove the least important element from the set client.ops if the set has the size maxSize. However, one exception must be observed. If we removed delete opera-tions, this would have very drastic impacts of the client: the corresponding object would never be removed by the client in most cases. Therefore, we must not re-move such operations from the set client.ops. Instead, we remove another opera-tion having an older time stamp op.time from the set. However, in the case where only delete operations exist, this approach does not work. Then, it is a solution to neglect the space restrictions or to disregard the time restriction minPeriod, i.e. means to send data earlier (and in consequence more data) to the client than ex-pected.
Removing elements from the set of operations has a further impact: A client may receive update or delete operations concerning objects unknown for the client because it has not received any insert operation for this object before. Conse-quently, such an update must be executed as an insertion and such a deletion can be ignored by the client.
4 Experimental Investigation
The experiments presented in the following investigate the applicability of the algorithms. Especially, the impact of the technical restrictions and of limiting the memory on the quality of the query results should be examined.
4.1 Test data and queries
For generating suitable test data, the generator for spatiotemporal data presented in (Brinkhoff, 2000) was used. This generator allows computing moving objects using a network observing several rules in order to simulate typical traffic situa-tions. In our case, a street network consisting of 6,065 edges was used, which can be downloaded from the web site of the generator given in that paper. Six object classes were defined. The maximum distance done by an object was between 1/250 and 1/8000 of the sum of the x-extension and the y-extension of the data space. The probability of a move per time stamp was 25%. The query condition used for the queries in the following tests is quite simple: it selects all objects lying in a query window having a size of 10% of the data space.
4.2 The tests and their results
The following experiments were performed by an implementation of the continu-ous query programmed in Java using Oracle 8i. The continuous queries were started at time stamp 640 and stopped at time stamp 1280. At time stamp 640, 281 moving objects were within the query window and at the end 387 objects. During the query, the complete number of operations to be transmitted to a client was 56,712. The measure of interest intr was computed as follows:
(1) intr(obj prev,obj curr) := (time curr - time prev) + w loc * dist(time curr , time prev)
The factor w loc scales the Euclidean distance such that the influence of time and space is equalized. The threshold thr is set on a value that would be exceeded for dist = 0, if the period between the two operations was larger than 4*minPeriod. The first test series investigate the results of the continuous query for different minimum periods minPeriod. Figure 4 gives an overview of the results. The re-sults of a minPeriod of 1 correspond to the results computed by the algorithm presented in section 2.2; the other results are computed using the algorithm of section 3.1. The omitting degree describes the quality of the query result according to definition of (Brinkhoff and Weitk?mper, 2001). The smaller the omitting de-gree, the better the quality of the query result. The omitting degree consists of two components: timeOD describes the temporal quality and distOD the spatial qual-ity. Because of a lack of space, the definition of the omitting degree cannot be presented here.
Figure 4: Results depending on the minimum period minPeriod.
The number of transmitted operations declines from 56,712 for a minPeriod of 1
to 7,769 for a minPeriod of 32, i.e. by a factor of 7.3. The number of operations per transmission increases by a factor of about 4.2. This effect results from the fact that with increasing values of minPeriod the probability increases that an opera-tion is updated by a new operation before it is transmitted to the client. In conse-quence, the quality of the result decreases considerably; for a minPeriod of 32, we observe an omitting degree of about 0.61. The average delay is not so much af-fected because it is only measured for transmitted operations and not for opera-tions being replaced before sending them to the client.
In the next test series, the number of operations transmitted to the client (maxOps) was limited. The value of minOps was always set to maxOps /2. Figure 5 shows the main results for a minPeriod of 4 and 8. In the unlimited case (unl), up to 292 and 362 operations per transmission occur.
Figure 5: Results depending on the number of operations per transmission.
By limiting the number of operations, also the total number of transmissions op-erations decreases: we observe factors of 3.8 and 4.9 between the unlimited case and a maximum number of 64 operations for a minPeriod of 4 and 8, respectively. Consequently, the measure omitDeg increases. However, the increase is relatively
moderate, especially for the distance measure distOD. This observation demon-strates that the heuristics used by the algorithm for selecting the transmitted opera-tions have success and compensate some of the loss of quality. The graphs depict-ing the average delay are quite interesting. They show that up to a certain point, the main effect of limiting maxOps is that older operations in the set client.ops are replaced by newer operations. In this case, no impact on avDelay can be observed. Beyond this point, the transmission of operations is really delayed and avDelay increases. Another observation concerns the size of client.ops: the smaller maxOps, the larger the maximum size of this set. Therefore, the maximum size of client.ops (maxSize) is limited in the test series of figure 6. That means we investi-gate a version of the algorithm of section 3.1, which observes the space restric-tions presented in section 3.2.
Figure 6: Results depending on maxOps and maxSize (unl = unlimited). Limiting maxSize leads to a further decline of the number of transmitted opera-tions. Again, the impact on the quality of the query result is rather moderate. Es-pecially, the distance portion of the omitting degree is almost unaffected.
We can summarize that the experiments have shown that the proposed algorithm allows limiting the number of transmitted operations as well as of the number of operations buffered by the STDBS without a huge loss of quality. Especially, the impact on the distance between the locations of the transmitted object descriptions is rather moderate.
5 Conclusions
In this paper, filtering algorithms for processing spatial continuous queries in a spatiotemporal database system (STDBS) have been presented. After presenting a first algorithm, we have observed two contradicting optimization goals: First, to reduce the memory requirements of the STDBS and second, to reduce the volume and frequency of transmissions to the clients. In order to balance between these two objectives, an algorithm has been presented that observes different parameters modeling technical restrictions as well as the interest of a client in a distinct up-date operation. A restriction of the memory requirements of the algorithm has been achieved by using an adapted replacement strategy.
However, delaying and not transmitting update operations to a client decreases the quality of the query result. In an experimental investigation, the proposed algo-rithms have been examined measuring the quality of the query results. These tests
have shown that the algorithm, which was finally proposed, allows limiting the number of transmitted operations as well as of the number of the operations buff-ered by the STDBS without a huge loss of quality. Especially, the impact on the distance between the locations of the transmitted object descriptions is rather moderate.
The definition of continuous queries in this paper was based on a quite simple model of moving objects. Therefore, future work should cover a definition using a more expressive data model. The same holds for the application. More complex is, e.g., the detection of collisions for moving 3D objects (Mirtich, 2000). The ex-perimental investigations presented in this paper have been based on a standard database system. A major drawback of using such a database system is the high effort for determining the previous object description of an updated object. This disadvantage must be eliminated by extending the database system by a suitable buffering technique or by using (prototypes of) spatiotemporal database systems. Then, more detailed performance investigations including the measurement of the processing time for performing continuous queries will be reasonable. Another aspect is the behavior of the restricting parameters. In this paper, it is assumed that they do not change over the time with respect to a client. However, the resolution of a client may be changed by performing a zoom operation. The parameters minOps, maxOps and minPeriod may be affected by the traffic of other users of the network connection or by a changed capacity of the connection (e.g., using the new mobile telephone standard UMTS, the maximum speed of a connection will depend on the distance of the mobile telephone to the next base station.) There-fore, efficient filter algorithms are required, which observe varying restrictions.
6 References
Brinkhoff T (1999) Requirements of Traffic Telematics to Spatial Databases. In: Proceed-ings 6th International Symposium on Large Spatial Databases, Hong Kong, China. Lecture Notes in Computer Science, Vol.1651, Springer, pp 365-369.
Brinkhoff T (2000) Generating Network-Based Moving Objects. In: Proceedings 12th Inter-national Conference on Scientific and Statistical Database Management, Berlin, Germany, pp 253-255. Extended version accepted for GeoInformatica, Kluver.
Brinkhoff T, Weitk?mper J (2001) Continuous Queries within an Architecture for Querying XML-Represented Moving Objects. In: Proceedings 7th International Symposium on Spa-tial and Temporal Databases, Redondo Beach, CA. Lecture Notes in Computer Science, Vol.2121, Springer, pp 136-154.
Mirtich B (2000) Timewarp Rigid Body Simulation. In: Proceedings ACM SIGGRAPH 27th International Conference on Computer Graphics and Interactive Techniques, New Orleans, LA, pp 193-200.
Terry D, Goldberg D, Nichols D, Oki B (1992) Continuous Queries over Append-Only Databases. In: Proceedings ACM SIGMOD International Conference on Management of Data, San Diego, CA, pp 321-330.
Wolfson O, Sistla AP, Chamberlain S, Yesha Y (1999) Updating and Querying Databases that Track Mobile Units. In: Distributed and Parallel Databases, 7(3), pp 257-287.
On the contrary Onthecontrary, I have not yet begun. 正好相反，我还没有开始。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, the instructions have been damaged. 反之，则说明已经损坏。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, I understand all too well. 恰恰相反，我很清楚 https://www.doczj.com/doc/d43657107.html, Onthecontrary, I think this is good. ⑴我反而觉得这是好事。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, I have tons of things to do 正相反，我有一大堆事要做 Provided by jukuu Is likely onthecontrary I in works for you 反倒像是我在为你们工作 https://www.doczj.com/doc/d43657107.html, Onthecontrary, or to buy the first good. 反之还是先买的好。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, it is typically american. 相反，这正是典型的美国风格。 222.35.143.196 Onthecontrary, very exciting.
恰恰相反，非常刺激。 https://www.doczj.com/doc/d43657107.html, But onthecontrary, lazy. 却恰恰相反，懒洋洋的。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, I hate it! 恰恰相反，我不喜欢！ https://www.doczj.com/doc/d43657107.html, Onthecontrary, the club gathers every month. 相反，俱乐部每个月都聚会。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, I'm going to work harder. 我反而将更努力工作。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, his demeanor is easy and nonchalant. 相反，他的举止轻松而无动于衷。 https://www.doczj.com/doc/d43657107.html, Too much nutrition onthecontrary can not be absorbed through skin. 太过营养了反而皮肤吸收不了. https://www.doczj.com/doc/d43657107.html, Onthecontrary, I would wish for it no other way. 正相反，我正希望这样 Provided by jukuu Onthecontrary most likely pathological. 反之很有可能是病理性的。 https://www.doczj.com/doc/d43657107.html, Onthecontrary, it will appear clumsy. 反之，就会显得粗笨。 https://www.doczj.com/doc/d43657107.html,
一般过去式 时间状语：yesterday just now (刚刚) the day before three days ag0 a week ago in 1880 last month last year 1. I was in the classroom yesterday. I was not in the classroom yesterday. Were you in the classroom yesterday. 2. They went to see the film the day before. Did they go to see the film the day before. They did go to see the film the day before. 3. The man beat his wife yesterday. The man didn’t beat his wife yesterday. 4. I was a high student three years ago. 5. She became a teacher in 2009. 6. They began to study english a week ago 7. My mother brought a book from Canada last year. 8.My parents build a house to me four years ago . 9.He was husband ago. She was a cooker last mouth. My father was in the Xinjiang half a year ago. 10.My grandfather was a famer six years ago. 11.He burned in 1991
●I wonder if it’s because I have been at school for so long that I’ve grown so crazy about going home. ●It is because she wasn’t well that she fell far behind her classmates this semester. ●I can well remember that there was a time when I took it for granted that friends should do everything for me. ●In order to make a difference to society, they spent almost all of their spare time in raising money for the charity. ●It’s no pleasure eating at school any longer because the food is not so tasty as that at home. ●He happened to be hit by a new idea when he was walking along the riverbank. ●I wonder if I can cope with stressful situations in life independently. ●It is because I take things for granted that I make so many mistakes. ●The treasure is so rare that a growing number of people are looking for it. ●He picks on the weak mn in order that we may pay attention to him. ●It’s no pleasure being disturbed whena I settle down to my work. ●I can well remember that when I was a child, I always made mistakes on purpose for fun. ●It’s no pleasure accompany her hanging out on the street on such a rainy day. ●I can well remember that there was a time when I threw my whole self into study in order to live up to my parents’ expectation and enter my dream university. ●I can well remember that she stuck with me all the time and helped me regain my confidence during my tough time five years ago. ●It is because he makes it a priority to study that he always gets good grades. ●I wonder if we should abandon this idea because there is no point in doing so. ●I wonder if it was because I ate ice-cream that I had an upset student this morning. ●It is because she refused to die that she became incredibly successful. ●She is so considerate that many of us turn to her for comfort. ●I can well remember that once I underestimated the power of words and hurt my friend. ●He works extremely hard in order to live up to his expectations. ●I happened to see a butterfly settle on the beautiful flower. ●It’s no pleasure making fun of others. ●It was the first time in the new semester that I had burned the midnight oil to study. ●It’s no pleasure taking everything into account when you long to have the relaxing life. ●I wonder if it was because he abandoned himself to despair that he was killed in a car accident when he was driving. ●Jack is always picking on younger children in order to show off his power. ●It is because he always burns the midnight oil that he oversleeps sometimes. ●I happened to find some pictures to do with my grandfather when I was going through the drawer. ●It was because I didn’t dare look at the failure face to face that I failed again. ●I tell my friend that failure is not scary in order that she can rebound from failure. ●I throw my whole self to study in order to pass the final exam. ●It was the first time that I had made a speech in public and enjoyed the thunder of applause. ●Alice happened to be on the street when a UFO landed right in front of her. ●It was the first time that I had kept myself open and talked sincerely with my parents. ●It was a beautiful sunny day. The weather was so comfortable that I settled myself into the
高中英语~词性~句子成分~语法构成 第一章节：英语句子中的词性 1.名词：n. 名词是指事物的名称，在句子中主要作主语.宾语.表语.同位语。 2.形容词;adj. 形容词是指对名词进行修饰~限定~描述~的成份，主要作定语.表语.。形容词在汉语中是（的）.其标志是: ous. Al .ful .ive。. 3.动词：vt. 动词是指主语发出的一个动作，一般用来作谓语。 4.副词：adv. 副词是指表示动作发生的地点. 时间. 条件. 方式. 原因. 目的. 结果.伴随让步. 一般用来修饰动词. 形容词。副词在汉语中是（地）.其标志是：ly。 5.代词：pron. 代词是指用来代替名词的词，名词所能担任的作用，代词也同样.代词主要用来作主语. 宾语. 表语. 同位语。 6.介词：prep.介词是指表示动词和名次关系的词，例如：in on at of about with for to。其特征：
介词后的动词要用—ing形式。介词加代词时，代词要用宾格。例如：give up her（him）这种形式是正确的，而give up she（he）这种形式是错误的。 7.冠词：冠词是指修饰名词，表名词泛指或特指。冠词有a an the 。 8.叹词：叹词表示一种语气。例如：OH. Ya 等 9.连词：连词是指连接两个并列的成分，这两个并列的成分可以是两个词也可以是两个句子。例如：and but or so 。 10.数词：数词是指表示数量关系词，一般分为基数词和序数词 第二章节：英语句子成分 主语：动作的发出者，一般放在动词前或句首。由名词. 代词. 数词. 不定时. 动名词. 或从句充当。 谓语：指主语发出来的动作，只能由动词充当，一般紧跟在主语后面。 宾语：指动作的承受着，一般由代词. 名词. 数词. 不定时. 动名词. 或从句充当. 介词后面的成分也叫介词宾语。 定语：只对名词起限定修饰的成分，一般由形容
M A: Has the case been closed yet? B: No, the magistrate still needs to decide the outcome. magistrate n.地方行政官，地方法官，治安官 A: I am unable to read the small print in the book. B: It seems you need to magnify it. magnify vt.１．放大，扩大；２．夸大，夸张 A: That was a terrible storm. B: Indeed, but it is too early to determine the magnitude of the damage. magnitude n.１．重要性，重大；２．巨大，广大 A: A young fair maiden like you shouldn’t be single. B: That is because I am a young fair independent maiden. maiden n.少女，年轻姑娘，未婚女子 a.首次的，初次的 A: You look majestic sitting on that high chair. B: Yes, I am pretending to be the king! majestic a.雄伟的，壮丽的，庄严的，高贵的 A: Please cook me dinner now. B: Yes, your majesty, I’m at your service. majesty n.１．［Ｍ－］陛下（对帝王，王后的尊称）；２．雄伟，壮丽，庄严 A: Doctor, I traveled to Africa and I think I caught malaria. B: Did you take any medicine as a precaution? malaria n.疟疾 A: I hate you! B: Why are you so full of malice? malice n.恶意，怨恨 A: I’m afraid that the test results have come back and your lump is malignant. B: That means it’s serious, doesn’t it, doctor? malignant a.１．恶性的，致命的；２．恶意的，恶毒的 A: I’m going shopping in the mall this afternoon, want to join me? B: No, thanks, I have plans already. mall n.（由许多商店组成的）购物中心 A: That child looks very unhealthy. B: Yes, he does not have enough to eat. He is suffering from malnutrition.
意见应以事实为根据. 3 来自辞典例句 192. The bombers swooped ( down ) onthe air base. 轰炸机 突袭 空军基地. 来自辞典例句 193. He mounted their engines on a rubber base. 他把他们的发动机装在一个橡胶垫座上. 14 来自辞典例句 194. The column stands on a narrow base. 柱子竖立在狭窄的地基上. 14 来自辞典例句 195. When one stretched it, it looked like grey flakes on the carvas base. 你要是把它摊直, 看上去就象好一些灰色的粉片落在帆布底子上. 18 来自辞典例句 196. Economic growth and human well - being depend on the natural resource base that supports all living systems. 经济增长和人类的福利依赖于支持所有生命系统的自然资源. 12 1 来自辞典例句 197. The base was just a smudge onthe untouched hundred - mile coast of Manila Bay. 那基地只是马尼拉湾一百英里长安然无恙的海岸线上一个硝烟滚滚的污点. 6 来自辞典例句 198. You can't base an operation on the presumption that miracles are going to happen. 你不能把行动计划建筑在可能出现奇迹的假想基础上.
英语造句大全English sentence 在句子中，更好的记忆单词！ 1、(1)、able adj. 能 句子：We are able to live under the sea in the future. (2)、ability n. 能力 句子：Most school care for children of different abilities. (3)、enable v. 使。。。能句子：This pass enables me to travel half-price on trains. 2、(1)、accurate adj. 精确的句子：We must have the accurate calculation. (2)、accurately adv. 精确地 句子：His calculation is accurately. 3、(1)、act v. 扮演 句子：He act the interesting character. （2）、actor n. 演员 句子：He was a famous actor. (3)、actress n. 女演员 句子：She was a famous actress. (4)、active adj. 积极的 句子：He is an active boy. 4、add v. 加 句子：He adds a little sugar in the milk. 5、advantage n. 优势 句子：His advantage is fight. 6、age 年龄n. 句子：His age is 15. 7、amusing 娱人的adj. 句子：This story is amusing. 8、angry 生气的adj. 句子：He is angry. 9、America 美国n.
主语+谓语 1. 理解主谓结构 1) The students arrived. The students arrived at the park. 2) They are listening. They are listening to the music. 3) The disaster happened. 2．体会状语的位置 1) Tom always works hard. 2) Sometimes I go to the park at weekends.. 3) The girl cries very often. 4) We seldom come here. The disaster happened to the poor family. 3. 多个状语的排列次序 1) He works. 2) He works hard. 3) He always works hard. 4) He always works hard in the company. 5) He always works hard in the company recently. 6) He always works hard in the company recently because he wants to get promoted. 4. 写作常用不及物动词 1. ache My head aches. I’m aching all over. 2. agree agree with sb. about sth. agree to do sth. 3. apologize to sb. for sth. 4. appear (at the meeting, on the screen) 5. arrive at / in 6. belong to 7. chat with sb. about sth. 8. come (to …) 9. cry 10. dance 11. depend on /upon 12. die 13. fall 14. go to … 15. graduate from 16. … happen 17. laugh 18. listen to... 19. live 20. rise 21. sit 22. smile 23. swim 24. stay (at home / in a hotel) 25. work 26. wait for 汉译英： 1.昨天我去了电影院。 2.我能用英语跟外国人自由交谈。 3.晚上7点我们到达了机场。 4.暑假就要到了。 5.现在很多老人独自居住。 6.老师同意了。 7.刚才发生了一场车祸。 8.课上我们应该认真听讲。9. 我们的态度很重要。 10. 能否成功取决于你的态度。 11. 能取得多大进步取决于你付出多少努力。 12. 这个木桶能盛多少水取决于最短的一块板子的长度。
【it's time to和it's time for】 ——————这其实是一个句型,只不过后面要跟不同的东西. ——————It's time to跟的是不定式（to do）.也就是说,要跟一个动词,意思是“到做某事的时候了”.如： It's time to go home. It's time to tell him the truth. ——————It's time for 跟的是名词.也就是说,不能跟动词.如： It's time for lunch.(没必要说It's time to have lunch) It's time for class.(没必要说It's time to begin the class.) They can't wait to see you Please ask liming to study tonight. Please ask liming not to play computer games tonight. Don’t make/let me to smoke I can hear/see you dance at the stage You had better go to bed early. You had better not watch tv It’s better to go to bed early It’s best to run in the morning I am enjoy running with music. With 表伴随听音乐 I already finish studying You should keep working. You should keep on studying English Keep calm and carry on 保持冷静继续前行二战开始前英国皇家政府制造的海报名字 I have to go on studying I feel like I am flying I have to stop playing computer games and stop to go home now I forget/remember to finish my homework. I forget/remember cleaning the classroom We keep/percent/stop him from eating more chips I prefer orange to apple I prefer to walk rather than run I used to sing when I was young What’s wrong with you There have nothing to do with you I am so busy studying You are too young to na?ve I am so tired that I have to go to bed early
《The Kite Runner》追风筝的人--------------------------------美句摘抄 1.I can still see Hassan up on that tree, sunlight flickering through the leaves on his almost perfectly round face, a face like a Chinese doll chiseled from hardwood: his flat, broad nose and slanting, narrow eyes like bamboo leaves, eyes that looked, depending on the light, gold, green even sapphire 翻译：我依然能记得哈桑坐在树上的样子，阳光穿过叶子，照着他那浑圆的脸庞。他的脸很像木头刻成的中国娃娃，鼻子大而扁平，双眼眯斜如同竹叶，在不同光线下会显现出金色、绿色，甚至是宝石蓝。 E.g.: A shadow of disquiet flickering over his face. 2.Never told that the mirror, like shooting walnuts at the neighbor's dog, was always my idea. 翻译：从来不提镜子、用胡桃射狗其实都是我的鬼主意。E.g.:His secret died with him, for he never told anyone. 3.We would sit across from each other on a pair of high
一、翻译 1. The idea of consciously seeking out a special title was new to me., but not without appeal. 让我自己挑选自己最喜欢的书籍这个有意思的想法真的对我具有吸引力。 2.I was plunged into the aching tragedy of the Holocaust, the extraordinary clash of good, represented by the one decent man, and evil. 我陷入到大屠杀悲剧的痛苦之中，一个体面的人所代表的善与恶的猛烈冲击之中。 3.I was astonished by the the great power a novel could contain. I lacked the vocabulary to translate my feelings into words. 我被这部小说所包含的巨大能量感到震惊。我无法用语言来表达我的感情（心情）。 4，make sth. long to short长话短说 5.I learned that summer that reading was not the innocent(简单的) pastime(消遣) I have assumed it to be., not a breezy, instantly forgettable escape in the hammock(吊床)，( though I’ ve enjoyed many of those too ). I discovered that a book, if it arrives at the right moment, in the proper season, will change the course of all that follows. 那年夏天，我懂得了读书不是我认为的简单的娱乐消遣，也不只是躺在吊床上，一阵风吹过就忘记的消遣。我发现如果在适宜的时间、合适的季节读一本书的话，他将能改变一个人以后的人生道路。 二、词组造句 1. on purpose 特意，故意 This is especially true here, and it was ~. (这一点在这里尤其准确，并且他是故意的) 2.think up 虚构，编造，想出 She has thought up a good idea. 她想出了一个好的主意。 His story was thought up. 他的故事是编出来的。 3. in the meantime 与此同时 助记：in advance 事前in the meantime 与此同时in place 适当地... In the meantime, what can you do? 在这期间您能做什么呢？ In the meantime, we may not know how it works, but we know that it works. 在此期间，我们不知道它是如何工作的，但我们知道，它的确在发挥作用。 4.as though 好像，仿佛 It sounds as though you enjoyed Great wall. 这听起来好像你喜欢长城。 5. plunge into 使陷入 He plunged the room into darkness by switching off the light. 他把灯一关，房
The effective sentences:(improve the sentences!) 1.She hopes to spend this holiday either in Shanghai or in Suzhou. 2.Showing/to show sincerity and to keep/keeping promises are the basic requirements of a real friend. 3.I want to know the space of this house and when it was built. I want to know how big this house is and when it was built. I want to know the space of this house and the building time of the house. 4.In the past ten years,Mr.Smith has been a waiter,a tour guide,and taught English. In the past ten years,Mr.Smith has been a waiter,a tour guide,and an English teacher. 5.They are sweeping the floor wearing masks. They are sweeping the floor by wearing masks. wearing masks,They are sweeping the floor. 6.the drivers are told to drive carefully on the radio. the drivers are told on the radio to drive carefully 7.I almost spent two hours on this exercises. I spent almost two hours on this exercises. 8.Checking carefully,a serious mistake was found in the design. Checking carefully,I found a serious mistake in the design.
M1 U1 一. 把下列短语填入每个句子的空白处（注意所填短语的形式变化）： add up (to) be concerned about go through set down a series of on purpose in order to according to get along with fall in love (with) join in have got to hide away face to face 1 We’ve chatted online for some time but we have never met ___________. 2 It is nearly 11 o’clock yet he is not back. His mother ____________ him. 3 The Lius ___________ hard times before liberation. 4 ____________ get a good mark I worked very hard before the exam. 5 I think the window was broken ___________ by someone. 6 You should ___________ the language points on the blackboard. They are useful. 7 They met at Tom’s party and later on ____________ with each other. 8 You can find ____________ English reading materials in the school library. 9 I am easy to be with and _____________my classmates pretty well. 10 They __________ in a small village so that they might not be found. 11 Which of the following statements is not right ____________ the above passage? 12 It’s getting dark. I ___________ be off now. 13 More than 1,000 workers ___________ the general strike last week. 14 All her earnings _____________ about 3,000 yuan per month. 二.用以下短语造句： 1.go through 2. no longer/ not… any longer 3. on purpose 4. calm… down 5. happen to 6. set down 7. wonder if 三. 翻译： 1.曾经有段时间，我对学习丧失了兴趣。（there was a time when…） 2. 这是我第一次和她交流。（It is/was the first time that …注意时态） 3.他昨天公园里遇到的是他的一个老朋友。（强调句） 4. 他是在知道真相之后才意识到错怪女儿了。（强调句） M 1 U 2 一. 把下列短语填入每个句子的空白处（注意所填短语的形式变化）： play a …role (in) because of come up such as even if play a …part (in) 1 Dujiangyan(都江堰) is still ___________in irrigation(灌溉) today. 2 That question ___________ at yesterday’s meeting. 3 Karl Marx could speak a few foreign languages, _________Russian and English. 4 You must ask for leave first __________ you have something very important. 5 The media _________ major ________ in influencing people’s opinion s. 6 _________ years of hard work she looked like a woman in her fifties. 二.用以下短语造句： 1.make (good/full) use of 2. play a(n) important role in 3. even if 4. believe it or not 5. such as 6. because of
English sentence 1、(1)、able adj. 能 句子：We are able to live under the sea in the future. (2)、ability n. 能力 句子：Most school care for children of different abilities. (3)、enable v. 使。。。能 句子：This pass enables me to travel half-price on trains. 2、(1)、accurate adj. 精确的 句子：We must have the accurate calculation. (2)、accurately adv. 精确地 句子：His calculation is accurately. 3、(1)、act v. 扮演 句子：He act the interesting character.（2）、actor n. 演员 句子：He was a famous actor. (3)、actress n. 女演员 句子：She was a famous actress. (4)、active adj. 积极的 句子：He is an active boy. 4、add v. 加 句子：He adds a little sugar in the milk. 5、advantage n. 优势 句子：His advantage is fight. 6、age 年龄n. 句子：His age is 15. 7、amusing 娱人的adj. 句子：This story is amusing. 8、angry 生气的adj. 句子：He is angry. 9、America 美国n. 句子：He is in America. 10、appear 出现v. He appears in this place. 11. artist 艺术家n. He is an artist. 12. attract 吸引 He attracts the dog. 13. Australia 澳大利亚 He is in Australia. 14.base 基地 She is in the base now. 15.basket 篮子 His basket is nice. 16.beautiful 美丽的 She is very beautiful. 17.begin 开始 He begins writing. 18.black 黑色的 He is black. 19.bright 明亮的 His eyes are bright. 20.good 好的 He is good at basketball. 21.British 英国人 He is British. 22.building 建造物 The building is highest in this city 23.busy 忙的 He is busy now. 24.calculate 计算 He calculates this test well. 25.Canada 加拿大 He borns in Canada. 26.care 照顾 He cared she yesterday. 27.certain 无疑的 They are certain to succeed. 28.change 改变 He changes the system. 29.chemical 化学药品