 Open Access
 Total Downloads : 856
 Authors : P. Sathish Saravanan
 Paper ID : IJERTV1IS9006
 Volume & Issue : Volume 01, Issue 09 (November 2012)
 Published (First Online): 29112012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Survey On Spatial & Temporal Reasoning In Computer Science Using Data Mining(Strcsdm)
P.Sathish Saravanan , APDepartment Of Information Technology , Velammal Institute of Technology ,
Chennai India .
Abstract
Nowadays Data Mining in Geospatial data extracted from spatiotemporal data will help us to have better prediction of spatial processes or events.Research area that started in Computer Science and information technology in the last decade and now penetrates into almost all datarich environments like spatiotemporal data mining[1][3][5] here refers to the extraction of implicit knowledge, spatial and temporal relationships, or other patterns not explicitly stored in spatiotemporal databases. It is a subfield of data mining and knowledge discovery in databases.
This paper provides an overview of spatial and temporal reasoning in computer science and analyze a few research areas and their issues about the spatiotemporal importance.We have also listed a few techniques and comments for developing useful applications for future usage of spatiotemporal data mining in computer science specialization[1].
Keywords: SpatioTemporal Data Mining, Data Mining Process and Tasks,SpatioTemporal Database, Constraint Networks and Qualitative Temporal,Spatio Temporal Reasoning and Modelling, Region Connection Calculus,Geospatial Data Repositories, Algorithms Analyzation(PathConsistency & Back Track)

Introduction
Qualitative spatialtemporal reasoning which is based on qualitative abstractions of temporal and spatial aspects of the commonsense background knowledge on which our human perspective of physical reality is based.We analyze spatiotemporal database[6] is a database that manages both space and time information.

1.Tracking of moving objects, which typically can occupy only a single position at a given time.

2.A Database of wireless communication networks, which may exist only for a short timespan within a geographic region.

3.An index of species in a given geographic region, where over time additional species may be introduced or existing species migrate or die out.
Spatiotemporal databases are an extension of spatial databases. A spatio temporal database embodies spatial, temporal, and spatiotemporal database concepts, and captures spatial and temporal aspects of data and deals with

geometry changing over time

location of objects moving over invariant geometry

Data Mining Techniques used in Spatialization & Temporalization
Data Mining includes spatio temporal databases, machine learning systems, statistics, geographic visualization, and information theory.

Spatial and Temporal relationships exist among spatial entities at various levels.

The spatial relations, both metric (such as distance) and nonmetric (such as topology, directions, shape, etc.), and temporal relations (such as before or after) may be explicit or implicit in the geographic databases.

Spatial and temporal dependency and heterogeneity are intrinsic characteristic of spatiotemporal databases.

Scale effect in space and time is a challenging research issue in geographic analysis.


Data Representation in SpatialTemporal
Four broad categories of temporality within data are classified in a review of temporal knowledge discovery

Like Static[13] Time has to be traced by external information such as database construction,

Like Sequences[13] Ordered list of events, reveals relationships such as before and after, or the richer relationships described as meets, overlaps,contemporary,

Timestamped[14] a timed sequence of static data taken at more or less regular intervals,

Fully temporal[14] Integrated spatiotemporal data, e.g. via events,processes.





Constraints used in Qualitative Temporal
Using the steps to accomplished this model QT[14]

the selection of a model that allows a trade off(Time & Space Tradeoff)between efficiency and representation

a preprocessing step for adapting the input to the model

a data mining algorithm able to deal with the properties provided by the model for generating a representative output


Representing Temporal Information
Temporal reasoning is an essential part of many artificial intelligence tasks. To develop a temporal reasoning component that is useful across applications such as planning and scheduling. Most of these calculi can be formalized as abstract relation algebras, such that reasoning can be carried out at a symbolic level. For computing solutions of a constraint network, a Path Consistency Algorithm[8] and BackTracking algorithm[9] are important for two fundamental tasks: For that determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information.
3.1 Analization with Constraint Networks
A constraint network[10] represents a mathematical relationship between several variables, and is able to compute the value of any one of these variables given the values of all the others.There differed in 2 ways in the nodes constraint are cells and constraints. Cells represent variables (readonly cells represent constants) and constraints represent primitive mathematical relationships such as z = x + y and z = x * y. The neighbors of a constraint are the cells that it constrains. The neighbors of a cell are the constraints that constrain it.
A number can be saved to or erased from a cell. In either case, the cell's neighboring constraints will be notified. Upon notification that a neighboring cell has been erased, a constraint erases all of its neighbors. Upon notification that a number has been stored in a neighboring cell, a constraint attempts to compute new values for its remaining neighbors. In either case, cells updated by a constraint notify the other constraints they are connected to. In this way cell updates cascade through the network.
For assume a, b, and c are cells connected to an addition constraint. If a number is stored in a, and if b already holds a number, then the adder constraint stores a + b in

However, if b doesn't hold a value, but c does, then the adder constraint stores c ( a in b). Contrast this "bi directional" behavior with the "unidirectional" behavior of the ordinary assignment statement:

c = a + b;which only assigns a + b to c

z = 5x + 3y Representation of this constraint network consist of 3 constraints & 7 cells:

Fig.1 Constraint Network for Complex Relationship
In this network the cells labeled 5 and 3 are constant or readonly cells. The cells labeled 5x and 3y hold 5 * x and 3* y. The nodes labeled + and * are constraints.
3.1.1 Analyze CONNNET constraint network
For an example CONNNET is an constraint network and executes the following console level commands:
help
help (displays this message) quit (terminates session)
set NAME VALUE (update a variable cell) addVar NAME (add a variable cell)
addConst NAME VALUE (add a constant cell) display NAME (display a cell)
undisplay NAME (undisplay a cell)
addAdder ARG1 ARG2 RESULT (add an adder constraint)
addMult ARG1 ARG2 RESULT (add a multiplier constraint)
clear (getrid of all cells & constraints) forgetAll (forget all cell values)
forget NAME (forget a cell value)
Let an example the program CONNNET to solve the equation: z = 3x + 4y
Before that we create 3 cells representing the variables x, y, and z: addVar x,addVar y,addVar z
Next, we create 2 cells that hold the constants 3 and 4, as well as 2 cells to hold the intermediate values of 3x and 4y:
addConst 3 3, addConst 4 4,addVar 3x, addVar 4y
We create three constraints. The first asserts that 4y holds the product of 4 and y, the second asserts that 3x holds the product of 3 and x, and the third asserts that z holds the sum of 3x and 4y:
addMult y 4 4y, addMult x 3 3x, addAdder 3x 4y z
usually cells are updated quietly. If we want a cell to display itself when it is updated, we must explicitly ask it to do so. In our example, we are only interested in the values held by x, y, and z:
display x, display y, display z
For an example, a constraint network representing the equation z = x + y and their memory organization :
Fig.2 Memory Organization of an Constraint Network
Fig.3 Sequence Diagram

Path Consistency Algorithm
Path consistency[8] is a property similar to arc consistency, but considers pairs of variables instead of only one. A pair of variables is pathconsistent with a third variable if each consistent evaluation of the pair can be extended to the other variable in such a way that all binary constraints are satisfied. Formally, and are path consistent with if, for every pair of that satisfies the binary constraint between and , there exists a value in the domain of such and satisfy the
constraint between and and between and
, respectively.
Fig.4 Path Consistency Diagram
x1 and x2 are not pathconsistent with x3. They can be made path consistent by removing the blue values from R12.

Back Tracking Approach(BT)
The backtracking algorithm[9] enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.The partial candidates are the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.The backtracking algorithm traverses this search tree recursively, from the root down, in depthfirst order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole subtree rooted at c is skipped (pruned). Otherwise, the algorithm (1) checks whether c itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all subtrees of
c. The two tests and the children of each node are defined by usergiven procedures.

Pseudocode
To apply the backtracking[9] to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

root(P): return the partial candidate at the root of the search tree.

reject(P,c): return true only if the partial candidate c is not worth completing.

accept(P,c): return true if c is a solution of P, and false otherwise.

first(P,c): generate the first extension of candidate c.

next(P,s): generate the next alternative extension of a candidate, after the extension s.

output(P,c): use the solution c of P, as appropriate to the application.

BT algorithm reduces and call bt(root(P)), where bt having recursive procedure:
procedure bt(c)
if reject(P,c) then return
if accept(P,c) then output(P,c)
s first(P,c) while s do bt(s)
s next(P,s)


SpatioTemporal Reasoning and Modelling
It encompasses the work done or in progress in the following broad subareas:
(1)SpatioTemporal Continuity,(2)Qualitative Modelling,(3)SpatioTemporal Ontology
4.1 SpatioTemporal Continuity
To formalize the intuitive notion of spatiotemporal continuity[11] for a qualitative theory of motion for describing how the relationships between regions change with time is necessary for modelling realworld processes. The generation of continuity network that demonstrates the allowed transitions between spatial relationships for the basic eight relation of RCC logic. This is shown in the figure on the left. Similar networks for extended forms of RCC have also been developed. The image on the right is actually a 3dimensional depiction of a continuity network for an extended 15 relation form of RCC.
Fig.5 Spatial relationship Diagram
systems.QSSIM is then able to generate successive
`envisionments' of the stages of the device's operation.
4.3 SpatioTemporal Ontology
Taking spacetime as primitive, we are working on an axiomatic theory for physical objects. We introduce and characterize by means of logical axioms the basic ontological distinctions needed to reason about physical objects for this ontology[12].
The most important spatialtemporal calculus is region connection calculi(RCC), spatio temporal constraint calculus (STCC), and qualitative trajectory calculus (QTC) allows for reasoning about moving objects.

Region Connection Calculus
The region connection calculus (RCC)[12] serves for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidean space, or in a topological space) by their possible relations to each other. RCC8 consists of 8 basic relations that are possible between two regions:Like disconnected (DC),externally connected (EC),equal (EQ),partially overlapping (PO),tangential proper part (TPP),tangential proper part inverse (TPPi),non tangential proper part (NTPP),nontangential proper part inverse (NTPPi)
Fig.7 Diagramatic View of Relations, Combinations for Proper Part (PP) is the union of TPP and NTPP
DC,
DC,
DC,
DC,
EC,
EC,
EC,
EC,
DC
*
PO,
PO,
PO,
PO,
DC
DC
DC
TPP,
TPP,
TPP,
TPP,
NTPP
NTPP
NTPP
NTPP
The composition table of RCC8 are as follows: "*" denotes the universal relation.
Fig.6 A 3dimensional depiction of a continuity network
4.2 Qualitative Modelling
An important application of RCC[12] has been to
Examples
Tab.1 The Composition Table of RCC8
produce a Qualitative Spatial Simulation program (QSSIM) for modelling physical and biological
The RCC8 calculus can be used for reasoning about spatial configurations. Consider the following example: two houses are connected via a road. Each house is
located on an own property. The first house possibly touches the boundary of the property; the second one surely does not. What can we infer about the relation of the second property to the road?
The spatial configuration can be formalized in RCC8 as the following constraint network:
house1 DC house2,house1 {TPP, NTPP} property1,house1{DC, EC} property2,house1 EC road,house2 { DC, EC } property1,house2 NTPP property2,house2 EC road,property1 { DC, EC } property2,road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property1,road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property2
Using the RCC8 composition table and the path consistency algorithm, we can refine the network in the following way:
road { PO, EC } property1,road { PO, TPP } property2
That is the road either overlaps with the second property, or is even (tangential) part of it.

Data Mining
Data mining[13] (the analysis step of the "Knowledge Discovery in Databases" process, or KDD), a field at the intersection of computer science and statistics, is the process that attempts to discover patterns in large data sets. It utilizes methods at the intersection of artificial intelligence, machine learning, statistics, and database systems. The Goal of the data mining process is to extract information from a data set and transform it into an understandable structure for further use.
6.1 Mining Process
The Knowledge Discovery in Databases (KDD)
[13]process is commonly defined with the stages:(1) Selection (2) Preprocessing (3) Transformation
(4) Data Mining (5) Interpretation/Evaluation.
KDD process simplified knowledge discovery as
(1) preprocessing, (2) data mining, and (3) results validation.

Preprocessing
Data mining can only uncover patterns actually present in the data, the target dataset must be large enough to contain these patterns while remaining concise enough to be mined within an acceptable time limit. A common source for data is a data mart or data warehouse. Pre processing is essential to analyze the multivariate datasets before data mining. The target set is then cleaned. Data cleaning removes the observations containing noise and those with missing data.

Data Mining Tasks
Data mining involves six common classes of tasks:

Deviation detection(OR) Anomaly detection The identification of unusual data records, that might be interesting or data errors and require further investigation.

Dependency modeling(OR)Association rule learning Searches for relationships between variables.

Clustering is the task of discovering groups and structures in the data that are in some way or another "similar", without using known structures in the data.

Classification is the task of generalizing known structure to apply to new data. For example, an email program might attempt to classify an e mail as "legitimate" or as "spam".

Regression Attempts to find a function which models the data with the least error.

Summarization providing a more compact representation of the data set, including visualization and report generation.


Results Validation
The missing information about nonclassification tasks in data mining, it only covers machine learning.
It is common for the data mining algorithms to find patterns in the training set which are not present in the general data set. This is called overfitting. To overcome this, the evaluation uses a test set of data on which the data mining algorithm was not trained.


Spatial Data Mining
Spatial data mining is the application of data mining methods to spatial data. The end objective of spatial data mining is to find patterns in data with respect to geography. So far, data mining and Geographic Information Systems (GIS)[2][4][5][6] have existed as two separate technologies, each with its own methods, traditions, and approaches to visualization and data analysis. The results for those organizations are:

offices requiring analysis or dissemination of georeferenced statistical data

public health services searching for explanations of disease clustering

environmental agencies assessing the impact of changing landuse patterns on climate change

geomarketing companies doing customer segmentation based on spatial location.

Challenges in Geospatial Data Repositories
Geographic Information Systems(GIS)[2][5][6] datasets are often splintered into feature and attribute components that are conventionally archived in hybrid data management systems. Algorithmic requirements differ substantially for relational (attribute) data management and for topological (feature) data management.

Research Areas for Geospatial Data Repositories

Developing and supporting geographic data warehouses (GDW's)

Better spatiotemporal representations in geographic knowledge discovery

Geographic knowledge discovery using diverse data types

And also used in Sensor data mining, Visual data mining, Music data mining



Pattern Mining
Pattern mining is a data mining method that involves finding existing patterns in data. In this context patterns often means association rules. The "Patternbased data mining[15] looks for patterns (including anomalous data patterns) that might be associated with terrorist activity these patterns might be regarded as small signals in a large ocean of noise.



Conclusion & Future Work
In this paper, we propose various computational activities to obtain Qualitative spatialtemporal reasoning with Computer Science.SpatioTemporal data mining is a promising research frontier for developing applications on Computational techniques in both Geographical Information Systems and Data Mining. Its not sufficient with manual data analyzation in spatiotemporal data mining with computer science Arena.So that we provide useful tools and technology for improving spatiotemporal activities in computational devices with increasing computerization in many fields, these days vast amounts of data are routinely collected.Here which we have listed few issues on which research can be done in future. Since many research challenges exist so scope of exploration in this field is quite vast. Hence there is always a need for efficient algorithms. . Future efforts will be needed to refine the parameters in this approach.Incrementally update or approximate computing techniques can be applied to improve the computational efficiency with time space trade off system.
References

Gennady Andrienko & Donato Malerba & Michael May & Maguelonne Teisseire Mining spatiotemporal data.

Buttenfield, B., Gahegan, M., Miller, H., Yuan, M. (2001), Geospatial data mining and Knowledge Discovery. UCGIS white paper on Emergent Research Themes.

Koperski, K., Adhikary, J., and Han, J. (1996), Spatial Data Mining: Progress and challenges. Proceedings of the ACM SIGMOD Workshop on Research Issues on Data Miining and Knowledge Discovery. Montreal, Canada: 5570.

Miller, H.J. and Han, J. (2001), Geographic data mining and knowledge discovery: an overview. In Miller, H.J. and Han, J. (eds) Geographic data mining and knowledge discovery. London, New York : Taylor & Francis, 332.

Roddick, J.F. and Lees, B.G. (2001), Paradigms for spatial and spatiotemporal data mining. In H.G. Miller and J. Han (eds), Geographic Data Mining and Knowledge Discovery. London: Taylor & Francis.

Tamas Abraham and John F. Roddick, Survey of SpaioTemporal Databases, GeoInformatica 3:1, 6199 (1999).

Xiaobai YaoResearch Issues in Spatiotemporal Data Mining A white paper submitted to the University Consortium for Geographic Information Science (UCGIS) workshop on Geospatial Visualization and Knowledge Discovery,Lansdowne, Virginia, Nov. 18 20, 2003.

Moninder SinghEfficient Path Consistency Algorithms for Constraint Satisfaction Problems in niversity of Pennsylvania.

Gurari, Eitan (1999). Backtracking algorithms "CIS 680:Datastructures:Chapter19:BacktrackingAlgorithms.

Rina Dechter,Itay Meiri and Judea PearlTemporal Constraint networks from Computer science Department,Haifa 32000,Israel & USA NOV 1989,1990.

Brandon Bennett, and Derek R. Magee and Anthony G. Cohn and David C. Hogg Using Spatio Temporal Continuity Constraints to Enhance Visual Tracking of Moving Objects.

Randell, D. A., Cui, Z. and Cohn, A. G.: A spatial logic based on regions and connection, Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, pp. 165176, 1992.

Introduction to Data Mining and Knowledge Discovery, Third Edition ISBN: 1892095025, Two Crows Corporation, 10500 Falls Road.

A. Cohn, and S. Hazarika. Qualitative Spatial Representation and Reasoning: An Overview". In Lecture Notes in Computer Science, Springer Berlin/Heidelberg, Qualitative Spatial Reasoning with Topological Information, Vol 2293/2002 , pp. 179182, 2001.

Taneli MielikÂ¨ainen Summarization Techniques for Pattern Collections in Data Mining Department of Computer Science Series of Publications A Report A 20051.