Online Detection of Congregation Arrangement over Trajectories

DOI : 10.17577/IJERTV4IS020318

Download Full-Text PDF Cite this Publication

Text Only Version

Online Detection of Congregation Arrangement over Trajectories

Carmel Lourdes Preethi1, Sumathy 2, Joe Phino. M 3

Department of Information Technology Jeppiaar engineering college

Chennai, India

Abstract: – The increasing pervasiveness of location- acquisition technologies has enabled collection of huge amount of trajectories for almost any kind of moving objects. In this light, we propose a novel concept, called gathering, which is a trajectory pattern modeling various group incidents such as celebrations, parades, protests, traffic jams and so on. These incidents typically involve large congregations of individuals, which form durable and stable areas with high density. These techniques, including effective indexing structures, fast pattern detection algorithms implemented with bit vectors, and incremental algorithms for handling new trajectory arrivals, collectively constitute an efficient solution for this challenging task. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on a real taxicab trajectory dataset.

Keyword: Gathering-trajectory pattern-location-acquisition technologies.


The main objective of this paper is to track a group of moving object. The pattern for the existence of such group is saved in a large scale trajectory database. Any changes in the regular existing pattern are observed keenly. This observation leads to the type of action to be performed on the object. Any non-trivial incidents can be analyzed easily. The type of incidents can be identified earlier based on the pattern gathering technique. The tracking output of particular pattern gathering will be more efficient than previous system.


  1. Clustering algorithm

    Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an

    appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 bench-mark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLARANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency. There are two basic types of clustering algorithms (Kaufman& Rousseau 1990): partitioning and hierarchical algorithms. Partitioning algorithms construct a partition of a database D of n objects into a set of k clusters. K is an input parameter for these algorithms, i.e. some domain knowledge is required which unfortunately is not available for many applications. The partitioning algorithm typically starts with an initial partition of D and then uses an iterative control strategy to optimize an objective function. Each cluster is represented by the gravity center of the cluster (k-means algorithms) or by one of the objects of the cluster located near its center (k- medoid algorithms). Consequently, partitioning algorithms use a two-step procedure. First, determine k representatives minimizing the objective function. Second, assign each object to the cluster with its representative closest to the considered object. The second step implies that a partition is equivalent to a voronoi diagram and each cluster is contained in one of the voronoi cells. Thus, the shape of all clusters found by a partitioning algorithm is convex which is very restrictive.

  2. Effective Density Queries On Continuously Moving Objects

This paper assumes a setting where a population of objects moves continuously in the Euclidean plane. The position of each object, modeled as a linear function from time to points, is assumed known. In this setting, the paper studies the querying for dense regions. In particular, the paper defines a particular type of density query with desirable properties and then proceeds to propose an algorithm for the efficient computation of density queries. While the algorithm may exploit any existing index for the current and near-future positions of moving objects, the Bx-tree is used. The paper reports on an extensive empirical study, which elicits the performance properties of the algorithm.

C.On-Line Discovery of Dense Areas in Spatio-temporal Databases

Moving object databases have received considerable attention recently. Previous work has concentrated mainly on modeling and indexing problems, as well as query selectivity estimation. Here we introduce a novel problem, that of addressing density-based queries in the spatio-temporal domain. For example: Find all regions that will contain more than 500 objects, ten minutes from now. The user may also be interested in finding the time period (interval) that the query answer remains valid. We formally define a new class of density-based queries and give approximate, on-line techniques that answer them efficiently. Typically the threshold above which a region is considered to be dense is part of the query. The difficulty of the problem lies in the fact that the spatial and temporal predicates are not specified by the query. The techniques we introduce find all candidate dense regions at any time in the future. To make them more scalable we subdivide the spatial universe using a grid and limit queries within a pre- specified time horizon. Finally, we validate our approaches with a thorough experimental evaluation.

    1. omputing with Spatial Trajectories

      The advances in location positioning and wireless communication technologies have led to a myriad of user- generated spatial trajectories, which imply rich information about user behavior, interests, and preferences. Recently, people have started sharing their trajectory data via online social networking services for a variety of purposes, fostering a number of trajectory-centric LBSNs (location- based social networks). For example, users can record travel routes with GPS trajectories to share travel experiences in an online community (e.g., GeoLife), or log jogging and bicycle trails for sports analysis and experience sharing. In addition, the check-ins of an individual in Foursquare and the photo trips of a user in Flicker can be regarded as spatial trajectories. These trajectory-centric LBSNs enable us to understand users and locations respectively, and explore the relationship between them.

      On the one hand, we can understand an individual and the similarity between two different users with user- generated trajectories, thereby providing a user with personalized services and enabling friend recommendation and community discovery. On the other hand, we are able to understand a location and the correlation between two different locations based upon the information from users, thereby offering users better travel recommendations.

      Under the circumstances of a trajectory-centric LBSN, this chapter explores two fundamental research points concerned with understanding users in terms of their locatons. One is modeling the location history of an individual using the individuals trajectory data. The other is estimating the similarity between two different people

      according to their location histories. The similarity represents the strength of connection between two users in a location-based social network, and can enable friend recommendations and community discovery. Some possible methods for evaluation of these applications have been discussed, and a number of publically available datasets have been listed in Chapter 8 as well.

      While chapter 8 studies the research philosophy behind a location-based social network from the point of view of users, Chapter 9 gradually explores the research into LBSNs from the perspective of locations. A series of research topics is presented with respect to mining the collective social knowledge from many users GPS trajectories to facilitate travel. First, the generic travel recommendations provide a user with the most interesting locations, travel sequences and travel experts in a region, as well as an effective itinerary conditioned by a users start location and available time length. Second, the personalized travel recommendations discover the locations matching an individuals interests, which can be gleaned from the individuals historical data. We hope you will find this book provides a useful overview of and a practical tutorial on the young and evolving field of computing with spatial trajectories.


      1. Snapshot

A snapshot of the existing crowd is been taken. An algorithm called density based algorithm is used to find the snapshot. By, replacing direct object instead of snapshots the process will be more efficient.

B.Crowd Detecting

In this step, we will present our framework for discovering all closed gatherings from a trajectory database. In this phase we perform a density-based clustering on the trajectory of objects should be maintained for each point of time. To do so, two types of algorithm is been used

Indexing cluster with R-tree – By using density based clusters the output may have arbitrary sleep and the R-tree maintains each point.

Indexing cluster with grid – Grid based clusters helps us more efficiently in affective pruning process.

C.Gathering Discovery

Test and Divide algorithm(TAD) – Used to detect a closed gathering in a crowd. Identifies invalid clusters, which doesnt have enough participants to test and divide. This process is efficient with bit vector signature algorithm.

Bit Vector Signature algorithm – In this algorithm, for each object and all subsequent objects the process such as test and divide can be performed in a bitwise operations.

D.Monitoring And Updation

The monitoring process can be done efficiently using travelling baddy method that helps to speed up the clustering process in order to keep updates. Then the online closed crowd detection, pruning of unwanted clusters and refinement is done. The updating process is known as incremental gathering update in order to find an update of newly formed closed gathering.


Since the whole discovery process with straightforward solutions can be very lengthy in a practical dataset, we propose a series of techniques which address the Indexing, searching and updating issues respectively. In future, the improvised tracking techniques can be used and the behavior of the object can be analyzed or monitored from the type of gathering pattern obtained.


  1. Kai Zheng1, Yu Zheng2, Nicholas Jing Yuan2, Shuo Shang3, On Discovery of Gathering Patterns from Trajectories,2014

  2. Y. Zheng and X. Zhou, Computing with spatial trajectories. Springer, 2011.

  3. M. Hadjieleftheriou, G. Kollios, D.,Gunopulos, and V. Tsotras, Online discovery of dense areas in spatio-temporal databases, Advances in Spatial and Temporal Databases, pp. 306324, 2003.

  4. C. Jensen, D. Lin, B. Ooi, and R. Zhang, Effective density queries on continuously moving objects, in ICDE, 2006, pp. 7171.

  5. M. Ester, H. Kriegel, J. Sander, and X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in SIGKDD, vol. 96, 1996, pp. 226231.


First author Carmel Lourdes Preethi ,is currently doing her fourth year B. Tech Information Technology at Jeppiaar Engineering College in Chennai, Tamil Nadu. she has attended many workshops.

Second author – Sumathy .G is currently doing her PhD in the area of Vision Technology & Image Processing and is Assistant Professor in Jeppiaar Engineering college in Chennai, Tamil Nadu.

Third author Joe Phino. M is currently doing her fourth year B. Tech Information Technology at Jeppiaar Engineering College in Chennai, Tamil Nadu. She has attended many workshops.

Leave a Reply