Privacy leaks in spatio-temporal trajectory publishing

Abstract

Hareket yörüngeleri, hareketli objelerin içerisinde degerli bilgiler içeren zaman-mekan izleridir. Bu bilgiler çesitli veri madenciligi uygulamalarında kullanılmak üzere toplanırlar. Sehir trafiginin planlanması, acil ulasım yollarının belirlenmesi ve akım takibi gibi bir çok uygulama hareket yörüngesi madenciliginden faydalanır. Kisilere ait hareket yörüngeleri sık sık kisiye özel ve hassas bilgiler içermektedir. Bu bilgilere sahip kisiler, veriler açıklanmadan önce gerekli özeni göstermelidir. Kisisel belirteçlerin, bu veriler açıklanmadan önce temizlenmesi de baglaç tipi saldırılara karsı zayıf kalmaktadır ve zengin arka-plan bilgileri ile bu zayıflık daha da belirginlesmektedir. Bu konuda bir alternatif, bilgileri açıklamadan önce dönüsüm teknikleri kullanarak, verilen bir küme hareket yörüngesini, ikili uzaklıkları korunacak sekilde bir baska kümeye dönüstürmektir. Bu sekilde gerçek hareket yörüngeleri açıklanmamakta fakat ikili uzaklık bilgileri hala kümeleme gibi veri madenciligi uygulamalarında kullanılabilmektedir. Bu çalısmada, bilinmeyen ve özel bir hareket yörüngesinin, veri madenciliginde kullanılmak üzere açıklanan ikili uzaklık bilgileri ve kullanıma müsait arka-plan bilgileri ile çözülebilecegi gösterilmektedir. Bahsedilen arka-plan bilgisi, bilinen bazı hareket yörüngeleri ve hız sınırı ek bilgileri biçimindedir. Çalısmada ayrıca, özel hareket yörüngelerini çözmek için bilinmesi gereken hareket yörüngeleri sayısı hakkında analitik sonuçlar da sunulmaktadır. Gerçek hareket yörüngesi veritabanlarında yapılan deneyler bilinmesi gereken hareket yörüngeleri sayısının olması gereken teorik sınırlardan sasırtıcı derecede küçük oldugunu göstermektedir.

Trajectories are spatio-temporal traces of moving objects which contain valuable information to be harvested by spatio-temporal data mining techniques. Applications like city traffic planning, identification of evacuation routes, trend detection, and many more can benefit from trajectory mining. However, the trajectories of individuals often contain private and sensitive information, so anyone who possess trajectory data must take special care when disclosing this data. Removing identifiers from trajectories before the release is not effective against linkage type attacks, and rich sources of background information make it even worse. An alternative is to apply transformation techniques to map the given set of trajectories into another set where the distances are preserved. This way, the actual trajectories are not released, but the distance information can still be used for data mining techniques such as clustering. In this thesis, we show that an unknown private trajectory can be reconstructed using the available background information together with the mutual distances released for data mining purposes. The background knowledge is in the form of known trajectories and extra information such as the speed limit. We provide analytical results which bound the number of the known trajectories needed to reconstruct private trajectories. Experiments performed on real trajectory data sets show that the number of known samples is surprisingly smaller than the actual theoretical bounds.