04-10-2016, 09:01 AM
1457544881-SATHYAMANUSCRIPT.docx (Size: 543.2 KB / Downloads: 3)
ABSTRACT
In spatio-temporal applications, moving objects identify their particular locations and needs to update the locations continuously to the server for future retrieval. Due tothe enormouscollections of moving objects, many spatio-temporal access techniques are developed to process user queries efficiently. Spatial objects whose position changes for every seconds. To achieve this past, present and future,frequentdata indexing hasto be done at all points of time [1].Introducing an innovative indexing type entitled as Adaptive Multi Linked R* tree (AMLR* tree)bounded with probability clustering approaches extracted objects by querying to increase the accessing speed as well as to reduce over dump of obsoleted and redundant data. The experimental results show that to obtain exact object with short time interval with minimal storage capacity and also outperform of increasing throughput.
1. INTRODUCTION
One of the emerging trends and technologies such as wireless communications and hardware, global positioning systems and personal locator software enables a range of new personal information services to be available. Most of those are related to the user’s geo-location. Example services include searching process applications that allow mobile phone users to locate any person or landmark. Services may also deliver maps, directions, or traffic reports commonly known as environmental monitoring, real-time navigational systems [2]. These new features are supported by location-basedserviceslike traffic management systems, mobile communication systems, sensor-based surveillance system and the like. The location-based services necessities are growing very rapidly. It could be elaborately categorized into 4 major types: informational, tracking, emergency and employee services [3].
Spatio-temporal databases involve moving objects that updating locations over time to time. Usually Moving objects catch their locations obtained through location-aware devices to a spatio-temporal database server. The server stores all the particulars about moving objects because of replying the queries of historical (storing facts of past) and current information. So the data stored in the server contains dynamically varied information. The supporting indexing techniques should be dynamic indexing methods. In earlier works it was found only historical data of Static location update techniques [4].Many of the existing indexing techniques are derived from the famous and well known structures like R-tree, Quad trees and Grid file.
Additionally, introducing the unfussyclustering algorithm like Probability distributionis used to classify the given data objects into different clusters through the iterative method. So the effects of generated clusters are dense and independent of each other. This greatly increases the clustering speed.
The main contributions of the paper are:
• A spatio-temporal data management system that can support extraordinary updating data using AMLR* tree to the most recent versions of the data.
• The cluster of systems have the complete updated kinds of all information’s and supporting varieties of queries with different retrieving patterns.
• Probability clustering algorithm for allocating data efficiently across the cluster of hosts in order to minimize response times and data duplication.
• Performance metrics is measured based on cost, throughput and clustering approaches.
Our framework utilizes a Master-host whose significant aim is to index the up-to-date version of the spatio-temporal data in a moving object. We attain this goal by using AdaptiveMulti Linked R*-Tree (AMLR*- Tree) [12], [24]. Among the groups of hosts, one system acts as a master-host. The AMLR*-Tree is implemented for accessing the spatio-temporal data at all the cluster of hosts. It achieves by splitting long rectangles into multiple smaller ones (Minimum Bounding Rectangles i.e., MBR) by implementing AMLR*-Tree that guarantees efficient clustering. We appoint a Master-host among the clusters whose responsibility is to make load-sharing decisions so that data is distributed cleverly across the cluster of hosts by increasing concurrent query processing rates. The rest of the hosts act as a storage systems, whose responsibility is to handle queries about data exist in in their jurisdiction. We do not use an R-Tree on the Master-host because of long time intervals that are updated infrequently.
This paper is organized as follows. Section 2 describes the related works. Section 3 discussesin detail about spatio-temporal access methods in an entirely different approaches and exhibits drawbacks in the existing approaches. In addition having separate indexing techniques for historical, current and future data for spatio-temporal mode be moving objects for uncertain data. Some of the accessing techniques have been proposed to work with data accessing at Euclidian spaces as well as threedimensional spatial environments for example road networks.
2. RELATED WORKS
Indexing future trajectories increases several problems when compared to the indexing past trajectories. The objective is to capably retrieve objects that will satisfy some spatial condition at a future time given their present motion vectors. A.Guttman. et. al [5]proposedR-tree is an extension of B-tree and also height-balanced indexing structure in the multi-dimensional space. Then some other familiar index techniques drawn-out from this are R*-Tree, packed R-Tree, CR-Tree, and R+-tree, etc. [6], [7] are designed to be the disk-oriented indexing techniques.R*-tree is differentfrom R-tree where characterization of overlapped rectangles and splitting algorithmoperate [8].Efficient pruning are used to decrease the number of routes visited by the consequent searches. Due to overlapping of multiple rectangles there are high possibilities to create duplicate objects existing in more than one nodes.Need for frequent updating of moving objects simultaneously is a must, and then only the latest positions are extracted though the implementation cost is fairlyhigh.
Pfoser et al. [10]proposed the Fixed Network R-tree (FNR) [9], separates spatial and temporal modules of the trajectories and indexes with in the time intervals during which any moving object is on a given network link. It can be only applied in a three-dimensional fixed network. The fixed network is a set of connected multiple line segments that is polylines instead of just one line segment. Since FNR uses 3D R-tree to index static objects alone, the Moving Object Network (MON-tree) [11] approach further expands the performance of the FNR-tree by revealing each edge by multiple line segments (i.e., polylines) instead of just single line segment.FNR and MON tree has the ability to retrieve with in a particular time slot. In this outdated methods, the object’s movements are not retrieved in the middle of a line segment and also their speeds or directions cannot be changed in between a line segment. If the time intervals exceeds simultaneously the bounding rectangle may get elapsed.
Papadias et al. [13] proposed the TPR and its extension TPR* tree,where TPR tree proficiently indexes the current and predicted future indexes of moving objects network. These structures use the linear prediction model to support predictive queries and to reduce the number of index updates. These methodscan maintain recent update history of continuously moving object in a future trajectories due to time parameterized accessing techniques. It maintains most recent locations and also can review its motion function. The server can easily locate the objects havingthe same motion functions. These trees come into the types of time parameterized access methods. Whereas TPR* also includes two opposite corner of the bounding rectangle in order to avoid the enlargement of d-space rectangles.The drawbacks of TPR [12] is objects moving within MBR can divert opposite directionsat different speeds. As a result, the MBR may expand rapidly, which may create large overlap with other MBRs,for every moment of query accessing need to update the entry and exit time as well as corners of rectangle.
Sun et.al. [19]Proposed MVR-treeis optimized from the original multi-versioned framework, taking into account spatial properties. It is helpful to index historical data -that is past data retrieval and based on this tree more number of extensions are inherited.MVR tree [16] maintains small fragment of spatio-temporal data at the server at the most recent updates and distribute obsoleted data sets to other sites. Tree nodes containing expired data sets can be easily removed over the network to other sites. Using this tree can achieve high update rates. MVR tree is a better indexing structure with stretched time intervals that are updated infrequently and creates long bounded rectangles for efficient clustering [17]. In contrast it forms excessive harmful redundancy.Space consumption is increased.
Chen et al. [14] suggested the ANRtreeavoids the aforementioned problem by grouping objects having similar moving patterns. It is a two level indexing methodology adopted and comes under the future trajectories of moving objects in a constrained network. At the top level layer 2D R-tree to indexes the moving objects and at the lower layer another 1D R-tree are used to index adaptive groupings. Each adaptive unit has a collection of moving objects with time parameter of similar direction and speed [18].So greatly reduced the updation cost and effective query accessing are possible.At one particular stage the grouping objects have to, in situation to get come out due to the directiondivert, and every time the user has to revise the speed and direction of the vehicle or any moving objects. So this type of indexing methods need very frequent updation with minimal cost consumption of grouping objects which is mandatory.
Ngai et al states the similar problem in [22] using clustering algorithm based on the outdated K-mean algorithm. It calculates the farthest distance of the nearest from the selection node. Due to large area covered by this k-means algorithm, our proposal of Probability based clustering is implemented. The following tabulation shows the comparison of proposed method i.e., AMLR* tree against other related indexing techniques:
ALGORITHM 1:Basic operations of AMLR* tree
Input : objSetID is the groups of object’s identifier, enterTime and exitTime as thresholdVal, position and velocity are its position and velocity,edgeID is the edge identifier for the object’s position.
(i) Insert, Delete and Update algorithms
InsertObjBound(id,set,maxBound,minBound,Eid,Tstart,Tend)
If (ObjBound is Full) then
call nodeSplit(OB.id);
else
Insert ObjBound register (id,pt,velocity,OB)
Delete (ObjBound(id,set,maxBound,minBound,Eid,Tstart,T-ends)
If(`ObjBound.set>maxNo) then
Remove ObjBound((id,loc,velocity,OB)
Update(id,loc,velocity,Eid)
Calculate ObjBound where id inserted
if ObjBound.Eid ≠ Eid or (id ≠ ObjBound)
loc<ObjBound or loc>ObjBound then
object moves to a new edge or exceeds bounds of its ObjBound.
Calculate nearest ObjBound OB1 for Eid.id;
if read(OB1.set < maxNo and exact match(id,loc,velocity,OB1) then
insert new obj(id,OB1.id,OB1.Eid);
else
create new OB2(id,Eid);
if read(OB.set)>1then
remove existingObj(id,OB.id,OB.Eid)
else
remove ObjBound(OB.Eid,OB.id);
else if (id(minBound of OB and loc) – OB.minBound >= threshold value.
acceptObjbound(OB,loc);
ALGORITHM 2 –Node splitting of AMLR* tree indexing method
1. Sort (Eid) to its Tstart
2. for(i=0 to y+1-2x)
3. allocate the first i+x entries into Bound1 and the remaining as Bound2.
4. if (Eid<minBound)
minBound=Eid; register allocation
5. Sort(Eid) of its every entries upto Tends then goto Step 2
6. return allocate minBound.
ALGORITHM 3 - Cluster formation with querying data sets.
Procedure : (i) Createn prob.cluster
1. While(ObjSetID!=NULL)
2. begin
3. if(ObjSetID<Velocity) && (ObjSetID<thresholdVal)
4. begin
//probability clustering begins
5. P=centre(ObjSetID)
6. Group the nearest thresholdVal by using clustering algorithm
7. end
8. end
The above algorithm shows the creation and modification of adaptive objects sets. Creation deals with the clustering of objects sets and the modification explains the adding and removing of objects sets those which solve the criteria otherwise it continues the same.
CONCLUSION
In this paper we propose a new index structure AMLR* for moving objects on networks. It is not only retrieve past, present and also foretells future locations of moving objects. This paper also addresses solutionfor the problem of efficient indexing of moving objects in spatial networks for assisting heavy load updates of data sets. Toachieve the limitations of the network and the performance of the real traffic to succeed both high update rates even in cost wise as well as querying efficiency.