Efficient Algorithms for Mining Maximal Valid Groups

Publication Type

Journal Article

Publication Date

9-2006

Abstract

A valid group is defined as a group of moving users that are within a distance threshold from one another for at least a minimum time duration. Unlike grouping of users determined by traditional clustering algorithms, members of a valid group are expected to stay close to one another during their movement. Each valid group suggests some social grouping that can be used in targeted marketing and social network analysis. The existing valid group mining algorithms are designed to mine a complete set of valid groups from time series of user location data, known as the user movement database. Unfortunately, there are considerable redundancy in the complete set of valid groups. In this paper, we therefore address this problem of mining the set of maximal valid groups. We first extend our previous valid group mining algorithms to mine maximal valid groups, leading to AMG and VGMax algorithms. We further propose the VGBK algorithm based on maximal clique enumeration to mine the maximal valid groups. The performance results of these algorithms under different sets of mining parameters are also reported.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

VLDB Journal

Volume

17

Issue

3

First Page

515

Last Page

535

ISSN

1066-8888

Identifier

10.1007/s00778-006-0019-9

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s00778-006-0019-9

Link to Full Text

Share

COinS