Topic
6 replies Latest Post - ‏2013-08-05T11:00:02Z by BhupeshChawda
VijayGabale
VijayGabale
0 Posts
ACCEPTED ANSWER

Pinned topic Problem 4

‏2013-07-20T11:21:49Z |

Do you like being a detective? Do you like analyzing and prediction of people's behavior? Then here is a problem some of the top criminal investigation agencies in the world are facing today. Apply your detective mind and build an Android App to track the criminals.

 

Use case:Recent laws require that the positions of certain criminals be tracked using GPS devices. These GPS traces are stored as a <lat, long> pair at each time point. This gives us a set of <lat, long, time> points which we call a trajectory. Criminal research has shown that a significant percentage of the crimes committed are repeated by previous criminals. In such a scenario, these trajectories would greatly help identify the criminals or even prevent it. In addition to the trajectory data, we also have other data like list of sensitive areas, crime victims' locations and time of past crimes, which can be consolidated with the trajectory data to make sense of the crime.

 

Definitions:

Problem Space

The spatial-temporal space considered for the problem is <x1, y1, t1> to <x2, y2, t2> where <x1,y1, x2,y2> is the rectangular spatial extent within which all the gps points will lie. Let <x1,y1> be the top left corner of the rectangle and <x2,y2> is the bottom right corner of the rectangle. Also <t1, t2> is the time interval within which all the time instants will lie. This can be considered as a 3-dimensional box where x, y denote the 2-dimensional space and the third dimension denotes the time.

 

Trajectory

A set of points of the form <i, x, y, t>, where i is the trajectory identifier, x,y = are the flattened lat and long for a 2-dimensional space. t is the time instant at which (x,y) was recorded for person i. Following is a snapshot from a sample file:

1,2,3,0

1,4,5,1

2,4,3,0

...

The first point 1,2,3,0 means that the x,y position of person id 1 was recorded to be (2,3) at time instant 0. The first two points belong to trajectory of person 1, while the third point belongs to the trajectory of person 2. In real gps samples, some points may be lost, however for the sake of simplicity assume that we have the samples for all time instants.

 

Let us define a few terms for the sake of correctness.

 

Area

An area is any rectangular spatial extent of the following form: <x1,y1,x2,y2> which lies within the problem space as defined before.

 

Time interval

A time interval ti is an interval defined by start and end time <t1,t2> both inclusive.

 

Predicates and their significance

 

Point (T, A, ti) -> {True,False} - Evaluates to true when trajectory T passes through the area defined by A in time interval defined by ti. This can be used to find trajectories of all criminals which were present at the scene of crime.

 

Range (T, A, d, ti) -> {True,False} - Evaluates to true when the trajectory T passes by within a distance d in the time interval defined by ti. This can be used to find all criminals which were present near the scene of crime. For this problem, assume d to be less than 1km.

 

Patterns

 

 

Criminal research has identified certain patterns which indicate criminal tendencies. For example, hanging out in crime prone areas, presence in restricted areas at unsuitable hours etc. Identifying all trajectories indicating such patterns may help prevent crimes in many cases.

 

  1. Crime prone areas: Given a duration threshold, if a trajectory is spending more time than the threshold in a given area, then that area is marked as a crime prone area.

 

  1. Similarity pattern: You can define a distance metric and find all trajectories similar to a given trajectory. You can use the distance functions to tap into similarities.

 

A potential victim has reported anonymous phone calls/threats. This query could help identify people who are following/tracking the victim over a period of time by finding all criminal trajectories similar to the trajectory of the potential victim.

 

  1. Follower Pattern: You can find all trajectories that follow the given trajectory. This is similar to the Similarity pattern, except that the time points of the two trajectories are separated by an offset. In other words, trajectory Ti follows the same points (or areas) as trajectory T but at some later time point. For example, Ti may pass areas A1, A2 and A3 at time t1, t2 and t3. However T may pass the same areas A1, A2 and A3 but at times t1+x1, t2+x2 and t3+x3. Note that the order in which the two trajectories traverse the areas is the same; t1+x1 < t2+x2 < t3+x3. For this problem, assume a maximum offset of 30 minutes.

 

Given the availability of GPS traces and the proliferation of mobile phones, it would help to build a mobile (e.g., Android based) App to help on-field crime-investigation agencies to track down the criminals. The App can sync up with a criminal-research database to know the GPS traces and provide useful information at run-time.

 

For this problem, we will provide a region map (e.g., open street map which your App can download and use) where you will have to figure the crime-prone areas. You will be provided with the GPS traces of criminals (not real-world criminals of course!) and a few civilians. Your job will be (1) to identify criminal-prone areas, (2) predict possible crime-suspects from the civilians, (3) find out the suspects for a victim, and (4) given partial GPS traces, predict the trajectories to prevent crimes in crime-prone areas (say by deploying police force).

 

Elimination round problem:

Given a set of trajectories marked as criminal trajectories, build an App and algorithms to find out (and show or specify in the App) the top crime prone areas on the map. Make sure you rank the areas so as to distinguish a more crime-prone area with a less crime-prone area. 

 

Final round:

(1) Given a set of trajectories marked as criminals, civilians and a victim, find out the suspects and show their trajectories. (2) Given a set of partial trajectories of criminals, predict and show the top 5 suspicious crime-zones.

 

Judging criteria: The only evaluation metric would be the run-time and accuracy of your algorithm on different data sets.

 

Elimination round 20%

Final round 60%

Algorithm description in a report 20%

Attachments

Updated on 2013-08-05T12:18:04Z at 2013-08-05T12:18:04Z by BhupeshChawda
  • Key_Lime
    Key_Lime
    2 Posts
    ACCEPTED ANSWER

    Problem 4-Need clarification regarding Area and Map

    ‏2013-08-01T14:51:38Z  in response to VijayGabale
    Sir, as you have mentioned in the problem that we will be given set of areas and the region map.
     
     "For this problem, we will provide a region map (e.g., open street map which your App can download and use), a set of areas (some of them are crime prone and other are not, you will have to figure the crime-prone areas), and GPS traces of criminals (not real-world criminals of course!) and a few civilians."
     
    Can you please guide us where can we get the set of areas, and the open street map from as mentioned in the problem above?
     
    • BhupeshChawda
      BhupeshChawda
      3 Posts
      ACCEPTED ANSWER

      Re: Problem 4-Need clarification regarding Area and Map

      ‏2013-08-04T07:42:42Z  in response to Key_Lime

      Hi,

      You can use either openstreetmap or google maps API for the purpose of the Android App.

      You can look refer the following for free APIs on Android:

      https://developers.google.com/maps/

      http://wiki.openstreetmap.org/wiki/Android

       

      The set of areas which are crime prone have to be figured out by your algorithm and marked on the map. For this you can use the attached GPS data for testing your algorithms.

      • Key_Lime
        Key_Lime
        2 Posts
        ACCEPTED ANSWER

        Re: Problem 4-Need clarification regarding Area and Map

        ‏2013-08-05T10:31:08Z  in response to BhupeshChawda

        hi Bhupesh,

        1)  I would like to ask should we assume that you will provide set of areas(in some format like text or other) and from them we will have to find out         the crime prone areas,       as you have said in the problem that you will provide the set of areas.

        2) And regarding the server, 

          should we keep gpx files in the phone  itself, or download them from the server.

         

        • BhupeshChawda
          BhupeshChawda
          3 Posts
          ACCEPTED ANSWER

          Re: Problem 4-Need clarification regarding Area and Map

          ‏2013-08-05T11:00:02Z  in response to Key_Lime

          Hi,

          These areas are embedded in the given trajectories. These trajectories, all of them being criminal trajectories, you have to find out the top crime prone areas in the entire area spanned by these trajectories.

          P.S.: All these trajectories span in and around the city of New Delhi, India. You can just try projecting the given trajectories on to a map. This will help you visualize the trajectories and get the overall idea.

  • Nit.M
    Nit.M
    1 Post
    ACCEPTED ANSWER

    Help

    ‏2013-08-02T13:28:59Z  in response to VijayGabale

    Hi, 

    1.    Here you have mentioned it as an app, May i know what type of app u refer to?? Is it android? or just an java application? or can it be a simple web application? or a desktop application made using C, Java or Python?
       
    2. Should we write code to hook it up with a server? if so can we assume our own sever details or you will be providing us with? 
       
    3. The GPS trace mentioned in the question is of the form <identifier, X co-ordinate, Y co-ordinate, Time> but the sample data are not of this format?For which format of data should we code? How will the data be stored in the DataBase?
       
    4. As "Key_Lime" posted what about the Map?



    Waiting for your reply

    • BhupeshChawda
      BhupeshChawda
      3 Posts
      ACCEPTED ANSWER

      Re: Help

      ‏2013-08-04T07:52:44Z  in response to Nit.M

      Hi,

      Please find my answers below:

      1. Yes. The App should be an Android App.

      2. You can assume a server for now. For the final testing of your App, we'll use an exernal server from where the files have to be read and used by the App.

      3. Yes. The given data format is different. GPX, being a standard representation of GPS traces, the input format will be helpful for you to import it in various map tools for visualization. Please assume the given data format for your code.

      4. Please refer to the reply to Key_Lime's post.