Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Spatio-Temporal Data Mining for Location-Based Services
Geomatic ApS - Center for Geoinformatics.ORCID iD: 0000-0003-1164-8403
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Largely driven by advances in communication and information technology, such as the increasing availability and accuracy of GPS technology and the miniaturization of wireless communication devices, Location–Based Services (LBS) are continuously gaining popularity. Innovative LBSes integrate knowledge about the users into the service. Such knowledge can be derived by analyzing the location data of users. Such data contain two unique dimensions, space and time, which need to be analyzed.

The objectives of this thesis are three–fold. First, to extend popular data mining methods to the spatio–temporal domain. Second, to demonstrate the usefulness of the extended methods and the derived knowledge in two promising LBS examples. Finally, to eliminate privacy concerns in connection with spatio–temporal data mining by devising systems for privacy–preserving location data collection and mining.

 

To this extent, Chapter 2 presents a general methodology, pivoting, to extend a popular data mining method, namely rule mining, to the spatio–temporal domain. By considering the characteristics of a number of real–world data sources, Chapter 2 also derives a taxonomy of spatio–temporal data, and demonstrates the usefulness of the rules that the extended spatio–temporal rule mining method can discover. In Chapter 4 the proposed spatio–temporal extension is applied to find long, sharable patterns in trajectories of moving objects. Empirical evaluations show that the extended method and its variants, using high–level SQL implementations, are effective tools for analyzing trajectories of moving objects.

Real–world trajectory data about a large population of objects moving over extended periods within a limited geographical space is difficult to obtain. To aid the development in spatio–temporal data management and data mining, Chapter 3 develops a Spatio–Temporal ACTivity Simulator (ST–ACTS). ST–ACTS uses a number of real–world geo–statistical data sources and intuitive principles to effectively generate realistic spatio–temporal activities of mobile users.

 

Chapter 5 proposes an LBS in the transportation domain, namely cab–sharing. To deliver an effective service, a unique spatio–temporal grouping algorithm is presented and implemented as a sequence of SQL statements. Chapter 6 identifies ascalability bottleneck in the grouping algorithm. To eliminate the bottleneck, the chapter expresses the grouping algorithm as a continuous stream query in a data stream management system, and then devises simple but effective spatio–temporal partitioning methods for streams to parallelize the computation. Experimental results show that parallelization through adaptive partitioning methods leads to speed–ups of orders of magnitude without significantly effecting the quality of the grouping. Spatio–temporal stream partitioning is expected to be an effective method to scale computation–intensive spatial queries and spatial analysis methods for streams.

 

Location–Based Advertising (LBA), the delivery of relevant commercial information to mobile consumers, is considered to be one of the most promising business opportunities amongst LBSes. To this extent, Chapter 7 describes an LBA framework and an LBA database that can be used for the management of mobile ads. Using a simulated but realistic mobile consumer population and a set of mobile ads, the LBA database is used to estimate the capacity of the mobile advertising channel. The estimates show that the channel capacity is extremely large, which is evidence for a strong business case, but it also necessitates adequate user controls.

 

When data about users is collected and analyzed, privacy naturally becomes a concern. To eliminate the concerns, Chapter 8 first presents a grid–based framework in which location data is anonymized through spatio–temporal generalization, and then proposes a system for collecting and mining anonymous location data. Experimental results show that the privacy–preserving data mining component discovers patterns that, while probabilistic, are accurate enough to be useful for many LBSes.

 

To eliminate any uncertainty in the mining results, Chapter 9 proposes a system for collecting exact trajectories of moving objects in a privacy–preserving manner. In the proposed system there are no trusted components and anonymization is performed by the clients in a P2P network via data cloaking and data swapping. Realistic simulations show that under reasonable conditions and privacy/anonymity settings the proposed system is effective.

Place, publisher, year, edition, pages
Department of Computer Science, Aalborg University , 2008. , 198 p.
Series
Ph.D. Thesis, ISSN 1601-0590 ; 44
Keyword [en]
spatio-temporal data mining; location-based services; location and trajectory anonymization
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-86310OAI: oai:DiVA.org:kth-86310DiVA: diva2:501531
Public defence
2008-03-11, 0.2.13, Aalborg University, Selma Lagerløfs vej 300, Aalborg, 14:00 (English)
Opponent
Supervisors
Note
QC 20120215Available from: 2012-02-15 Created: 2012-02-13 Last updated: 2012-02-15Bibliographically approved
List of papers
1. Spatio-temporal Rule Mining: Issues and Techniques
Open this publication in new window or tab >>Spatio-temporal Rule Mining: Issues and Techniques
2005 (English)In: DATA WAREHOUSING AND KNOWLEDGE DISCOVERY, PROCEEDINGS / [ed] A. Min Tjoa and Juan Trujillo, Springer, 2005, Vol. 3589, 275-284 p.Conference paper, Published paper (Refereed)
Abstract [en]

Recent advances in communication and information technology, such as the increasing accuracy of GPS technology and the miniaturization of wireless communication devices pave the road for Location–Based Services (LBS). To achieve high quality for such services, spatio–temporal data mining techniques are needed. In this paper, we describe experiences with spatio–temporal rule mining in a Danish data mining company. First, a number of real world spatio–temporal data sets are described, leading to a taxonomy of spatio–temporal data. Second, the paper describes a general methodology that transforms the spatio–temporal rule mining task to the traditional market basket analysis task and applies it to the described data sets, enabling traditional association rule mining methods to discover spatio–temporal rules for LBS. Finally, unique issues in spatio–temporal rule mining are identified and discussed.

Place, publisher, year, edition, pages
Springer, 2005
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3589
Keyword
spatio-temporal data mining
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81988 (URN)10.1007/11546849_27 (DOI)000231850500027 ()3-540-28558-X (ISBN)
Conference
Data Warehousing and Knowledge Discovery, 7th International Conference, DaWaK 2005, Copenhagen, Denmark, August 22-26, 2005
Note
QC 20120228Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-28Bibliographically approved
2. ST-ACTS: a spatio-temporal activity simulator
Open this publication in new window or tab >>ST-ACTS: a spatio-temporal activity simulator
2006 (English)In: GIS '06 Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems / [ed] Rolf A. de By and Silvia Nittel, ACM Press, 2006, 155-162 p.Conference paper, Published paper (Refereed)
Abstract [en]

Creating complex spatio–temporal simulation models is a hot issue in the area of spatio–temporal databases [7]. While existing Moving Object Simulators (MOSs) address different physical aspects of mobility, they neglect the important social and geo–demographical aspects of it. This paper presents ST–ACTS, a Spatio–Temporal ACTivity Simulator that, using various geo–statistical data sources and intuitive principles, models the so far neglected aspects. ST–ACTS considers that (1) objects (representing mobile users) move from one spatio–temporal location to another with the objective of performing a certain activity at the latter location; (2) not all users are equally likely to perform a given activity; (3) certain activities are performed at certain locations and times; and (4) activities exhibit regularities that can be specific to a single user or to groups of users. Experimental results show that ST-ACTS is able to effectively generate realistic spatio–temporal distributions of activities, which make it essential for the development of adequate spatio–temporal data management and data mining techniques.

Place, publisher, year, edition, pages
ACM Press, 2006
Keyword
spatio–temporal data, data generation, moving object simulation, activity simulator, data mining
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81990 (URN)10.1145/1183471.1183498 (DOI)1-59593-529-0 (ISBN)
Conference
14th Annual ACM International Symposium on Advances in Geographic Information Systems, ACM-GIS'06; Arlington, VA; 6 November 2006 through 11 November 2006
Note
QC 20120228Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-28Bibliographically approved
3. Mining Long, Sharable Patterns in Trajectories of Moving Objects
Open this publication in new window or tab >>Mining Long, Sharable Patterns in Trajectories of Moving Objects
2009 (English)In: Geoinformatica, ISSN 1384-6175, E-ISSN 1573-7624, Vol. 13, no 1, 27-55 p.Article in journal (Refereed) Published
Abstract [en]

The efficient analysis of spatio-temporal data, generated by moving objects, is an essential requirement for intelligent location-based services. Spatio-temporal rules can be found by constructing spatio-temporal baskets, from which traditional association rule mining methods can discover spatio-temporal rules. When the items in the baskets are spatio-temporal identifiers and are derived from trajectories of moving objects, the discovered rules represent frequently travelled routes. For some applications, e.g., an intelligent ridesharing application, these frequent routes are only interesting if they are long and sharable, i.e., can potentially be shared by several users. This paper presents a database projection based method for efficiently extracting such long, sharable frequent routes. The method prunes the search space by making use of the minimum length and sharable requirements and avoids the generation of the exponential number of sub-routes of long routes. Considering alternative modelling options for trajectories, leads to the development of two effective variants of the method. SQL-based implementations are described, and extensive experiments on both real life- and large-scale synthetic data show the effectiveness of the method and its variants.

Keyword
intelligent transportation systems, ride-sharing, moving object trajectories, spatio-temporal data, mining, frequent itemset mining, SQL-based pattern mining
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-82001 (URN)10.1007/s10707-007-0042-z (DOI)000262396900002 ()
Note
QC 20120217Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2017-12-07Bibliographically approved
4. Highly scalable trip grouping for large-scale collective transportation systems
Open this publication in new window or tab >>Highly scalable trip grouping for large-scale collective transportation systems
2008 (English)In: Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings / [ed] Alfons Kemper and Patrick Valduriez and Noureddine Mouaddib and Jens Teubner and Mokrane Bouzeghoub and Volker Markl and Laurent Amsaleg and Ioana Manolescu, ACM Press, 2008, Vol. 261, 678-689 p.Conference paper, Published paper (Refereed)
Abstract [en]

Transportation–related problems, like road congestion, parking, and pollution, are increasing in most cities. In order to reduce traffic, recent work has proposed methods for vehicle sharing, for example for sharing cabs by grouping “closeby” cab requests and thus minimizing transportation cost and utilizing cab space. However, the methods published so far do not scale to large data volumes, which is necessary to facilitate large–scale collective transportation systems, e.g., ride–sharing systems for large cities.

This paper presents highly scalable trip grouping algorithms, which generalize previous techniques and support input rates that can be orders of magnitude larger. The following three contributions make the grouping algorithms scalable. First, the basic grouping algorithm is expressed as a continuous stream query in a data stream management system to allow for a very large flow of requests. Second, following the divide–and–conquer paradigm, four space–partitioning policies for dividing the input data stream into sub–streams are developed and implemented using continuous stream queries. Third, using the partitioning policies, parallel implementations of the grouping algorithm in a parallel computing environment are described. Extensive experimental results show that the parallel implementation using simple adaptive partitioning methods can achieve speed–ups of several orders of magnitude without significantly degrading the quality of the grouping.

Place, publisher, year, edition, pages
ACM Press, 2008
Series
ACM International Conference Proceeding Series, 261
Keyword
spatio-temporal data stream processing; spatio-temporal data mining, LBS, ITS
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81999 (URN)10.1145/1353343.1353425 (DOI)978-1-59593-926-5 (ISBN)
Conference
EDBT 2008, 11th International Conference on Extending Database Technology, Nantes, France, March 25-29, 2008
Note
QC 20120217Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-17Bibliographically approved
5. Estimating the capacity of the Location-Based Advertising channel
Open this publication in new window or tab >>Estimating the capacity of the Location-Based Advertising channel
2008 (English)In: International Journal of Mobile Communications, ISSN 1470-949X, E-ISSN 1741-5217, Vol. 6, no 3, 357-375 p.Article in journal (Refereed) Published
Abstract [en]

Delivering ‘relevant’ advertisements to consumers carrying mobile devices is regarded by many as one of the most promising mobile business opportunities. The relevance of a mobile ad depends on at least two factors: (1) the proximity of the mobile consumer to the product or service being advertised, and (2) the match between the product or service and the interest of the mobile consumer. The interest of the mobile consumer can be either explicit (expressed by the mobile consumer) or implicit (inferred from user characteristics). This paper tries to empirically estimate the capacity of the Mobile Advertising channel, i.e. the number of relevant ads that can be delivered to mobile consumers. The estimations are based on a simulated mobile consumer population and simulated mobile ads. Both of the simulated data sets are realistic and derived based on real-world data sources about population geo-demographics, businesses offering products or services, and related consumer surveys. The estimations take into consideration both the proximity and interest requirements of mobile ads, i.e. ads are delivered only to mobile consumers that are close-by and are interested, where interest is either explicit or implicit. Results show that the capacity of the Location-Based Advertising channel is rather large, which is evidence for a strong business case, but it also indicates the need for user-control of the received mobile ads.

Keyword
capacity, estimation, Location-Based Advertising LBA, Mobile Advertising MA, simulation
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81996 (URN)10.1504/IJMC.2008.017516 (DOI)000261773800007 ()
Note
QC 20120217Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2017-12-07Bibliographically approved
6. Privacy-Preserving Data Mining on Moving Object Trajectories
Open this publication in new window or tab >>Privacy-Preserving Data Mining on Moving Object Trajectories
2007 (English)In: 2007 International Conference on Mobile Data Management / [ed] Christian Becker and Christian S. Jensen and Jianwen Su and Daniela Nicklas, IEEE conference proceedings, 2007, 60-68 p.Conference paper, Published paper (Refereed)
Abstract [en]

The popularity of embedded positioning technologies in mobile devices and the development of mobile communication technology have paved the way for powerful location-based services (LBSs). To make LBSs useful and user–friendly, heavy use is made of context information, including patterns in user location data which are extracted by data mining methods. However, there is a potential conflict of interest: the data mining methods want as precise data as possible, while the users want to protect their privacy by not disclosing their exact movements. This paper aims to resolve this conflict by proposing a general framework that allows user location data to be anonymized, thus preserving privacy, while still allowing interesting patterns to be discovered. The framework allows users to specify individual desired levels of privacy that the data collection and mining system will then meet. Privacy-preserving methods are proposed for a core data mining task, namely finding dense spatio–temporal regions. An extensive set of experiments evaluate the methods, comparing them to their non-privacy-preserving equivalents. The experiments show that the framework still allows most patterns to be found, even when privacy is preserved.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2007
Series
IEEE International Conference on Mobile Data Management. Proceedings, ISSN 1551-6245
Keyword
location privacy, location and trajectory anonymization, spatio-temporal data mining, dense regions
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81992 (URN)10.1109/MDM.2007.18 (DOI)1-4244-1240-4 (ISBN)
Conference
8th International Conference on Mobile Data Management (MDM 2007), Mannheim, Germany, May 7-11, 2007
Note
QC 20120228Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-28Bibliographically approved
7. Privacy-preserving trajectory collection
Open this publication in new window or tab >>Privacy-preserving trajectory collection
2008 (English)In: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems / [ed] Walid G. Aref and Mohamed F. Mokbel and Markus Schneider, ACM Press, 2008, 387-390 p.Conference paper, Published paper (Refereed)
Abstract [en]

In order to provide context–aware Location–Based Services, real location data of mobile users must be collected and analyzed by spatio–temporal data mining methods. However, the data mining methods need precise location data, while the mobile users want to protect their location privacy. To remedy this situation, this paper first formally defines novel location privacy requirements. Then, it briefly presents a system for privacy–preserving trajectory collection that meets these requirements. The system is composed of an untrusted server and clients communicating in a P2P network. Location data is anonymized in the system using data cloaking and data swapping techniques. Finally, the paper empirically demonstrates that the proposed system is effective and feasible.

Place, publisher, year, edition, pages
ACM Press, 2008
Keyword
Privacy, anonymity, diversity, data swapping, data cloaking, data mining, moving object trajectories, LBS, P2P
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81997 (URN)10.1145/1463434.1463491 (DOI)978-1-60558-323-5 (ISBN)
Conference
16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM GIS 2008; Irvine, CA; 5 November 2008 through 7 November 2008
Note
This work was, in large part, performed during a period when the first author’s primary affiliation was with Geomatic ApS / Aalborg University, and was supported in part by the Danish Ministry of Science, Technology, and Innovation. QC 20120217Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-17Bibliographically approved
8. Mining Long, Sharable Patterns in Trajectories of Moving Objects
Open this publication in new window or tab >>Mining Long, Sharable Patterns in Trajectories of Moving Objects
2006 (English)In: Proceedings of the Third Workshop on Spatio-Temporal Database Management, STDBM 06, September 11, 2006, Seoul, South Korea / [ed] Christophe Claramunt and Ki-Joune Li and Simonas Šaltenis, CEUR , 2006, 49-58 p.Conference paper, Published paper (Refereed)
Abstract [en]

The efficient analysis of spatio–temporal data, generated by moving objects, is an es-sential requirement for intelligent locationbased services. Spatio-temporal rules can befound by constructing spatio–temporal baskets, from which traditional association rulemining methods can discover spatio–temporal rules. When the items in the baskets arespatio–temporal identifiers and are derived from trajectories of moving objects, the discovered rules represent frequently travelled routes. For some applications, e.g., an intelligent ridesharing application, these frequent routes are only interesting if they are long and sharable, i.e., can potentially be shared by several users. This paper presents a database projection based method for efficiently extracting such long, sharable requent routes.The method prunes the search space by making use of the minimum length and sharable requirements and avoids the generation of the exponential number of subroutes of long routes. A SQL–based implementation is described, and experiments on real life data show the effectiveness of the method.

Place, publisher, year, edition, pages
CEUR, 2006
Series
CEUR Workshop Proceedings, ISSN 1613-0073 ; 174
Keyword
spatio-temporal data mining, sharable frequent routes, SQL-based itemset mining
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-86103 (URN)
Conference
The Third Workshop on Spatio-Temporal Database Management, STDBM 06, September 11, 2006, Seoul, South Korea
Note
QC 20120228Available from: 2012-02-13 Created: 2012-02-13 Last updated: 2012-02-28Bibliographically approved
9. Estimating the Capacity of the Location: Based Advertising Channel
Open this publication in new window or tab >>Estimating the Capacity of the Location: Based Advertising Channel
2007 (English)In: Conference Proceedings - 6th International Conference on the Management of Mobile Business, ICMB 2007, IEEE Computer Society, 2007, 4278546- p.Conference paper, Published paper (Refereed)
Abstract [en]

Delivering “relevant” advertisements to consumers carrying mobile devices is regarded by many as one of the most promising mobile business opportunities. The relevance of a mobile ad depends on at least two factors: (1) the proximity of the mobile consumer to the product or service being advertised, and (2) the match between the product or service and the interest of the mobile consumer. The interest of the mobile consumer can be either explicit (expressed by the mobile consumer) or implicit (inferred from user characteristics). This paper tries to empirically estimate the capacity of the mobile advertising channel, i.e., the number of relevant ads that can be delivered to mobile consumers. The estimations are based on a simulated mobile consumer population and simulated mobile ads. Both of the simulated data sets are realistic and derived based on real world data sources about population geo–demographics, businesses offering products or services, and related consumer surveys. The estimations take into consideration both the proximity and interest requirements of mobile ads, i.e., ads are only delivered to mobile consumers that are close-by and are interested, where interest is either explicit or implicit. Results show that the capacity of the LBA channel is rather large, which is evidence for a strong business case, but also indicate the need for user–control of the received mobile ads.

Place, publisher, year, edition, pages
IEEE Computer Society, 2007
Keyword
capacity estimation, Location-Based Advertising LBA, Mobile Advertising MA, simulation
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-81994 (URN)10.1109/ICMB.2007.28 (DOI)0769528031 (ISBN)9780769528038 (ISBN)
Conference
6th International Conference on the Management of Mobile Business, ICMB 2007; Toronto, ON; 9 July 2007 through 11 July 2007
Note
QC 20120228Available from: 2012-02-13 Created: 2012-02-11 Last updated: 2012-02-28Bibliographically approved

Open Access in DiVA

fulltext(3696 kB)799 downloads
File information
File name FULLTEXT01.pdfFile size 3696 kBChecksum SHA-512
77db64bc805ad7ebe2c59548bdb2664e1b9f0f6b9904c40c19082bdd2b960c684cf108557edf027f24c77be5e628ab058472f191c809be5489ff48078775afb1
Type fulltextMimetype application/pdf

Authority records BETA

Gidofalvi, Gyözö

Search in DiVA

By author/editor
Gidofalvi, Gyözö
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 799 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 460 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf