Article

Dimensionality reduction for long duration and complex spatio-temporal queries

Authors:

Ghazi Al-Naymat,

Joachim GudmundssonAuthors Info & Claims

SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Pages 393 - 397

https://doi.org/10.1145/1244002.1244095

Published: 11 March 2007 Publication History

Abstract

In this paper we present an approach to mine and query spatio-temporal data with the aim of finding interesting patterns and understanding the underlying data generating process. An important class of queries is based on the flock pattern. A flock is a large subset of objects moving along paths close to each other for a certain pre-defined time. One approach to process a "flock query" is to map spatio-temporal data into a high dimensional space and reduce the query into a sequence of standard range queries which can be presented using a spatial indexing structure. However, as is well known, the performance of spatial indexing structures drastically deteriorates in high dimensional space. In this paper we propose a preprocessing strategy which consists of using a random projection to reduce the dimensionality of the transformed space. Our experimental results show, for the first time, the possibility of breaking the curse of dimensionality in a spatio-temporal setting.

References

[1]

Porcupine caribou herd satellite collar project. http://www.taiga.net/satellite/.

[2]

D. Achlioptas. Database-friendly random projections. J. Comput. Syst. Sci., 66(4):671--687, 2003.

Digital Library

[3]

G. Al-Naymat, S. Chawla, and J. Gudmundsson. Dimensionality reduction for long duration and complex spatio-temporal queries. TR 600. ISBN 1-86487-874-6, University of Sydney, July 2006.

[4]

S. Arya, D. Mount, N. Netanyahu, and R. Silverman. An optimal algorithm for approximate nearest searching fixed dimensions. Journal of the ACM, 45(6):891--923, 1998.

Digital Library

[5]

A. Bagnall, Chotirat, E. Keogh, and G. Janacek. A bit level representation for time series data mining with shape based similarity. Data Mining and Knowledge Discovery, 13:41--65, 2006.

Digital Library

[6]

M. Benkert, J. Gudmundsson, F. Hübner, and T. Wolle. Reporting flock patterns. In Proc. of the 14th European Symposium on Algorithms. Springer-verlag, 2006.

Digital Library

[7]

E. Bingham and H. Mannila. Random projection in dimensionality reduction: applications to image and text data. In KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 245--250, New York, NY, USA, 2001. ACM Press.

Digital Library

[8]

M. T. G. D. Eppstein and J. Z. Sun. The skip quadtree: a simple dynamic data structure for multidimensional data. In 21st ACM Symp. Comp. Geom., pages 296--305, Pisa, 2005.

Digital Library

[9]

J. Gudmundsson and M. van Kreveld. Computing longest duration flocks in spatio-temporal data. In Proc. 14th ACM Symposium on Advances in GIS, 2006.

Digital Library

[10]

J. Gudmundsson, M. van Kreveld, and B. Speckmann. Efficient detection of motion patterns in spatio-temporal data sets. To appear in GeoInformatica, 2006.

Digital Library

[11]

R. Güting, M. Bohlen, M. Erwig, C. Jensen, N. Lorentzos, E. Nardelli, M. Schneider, and J. R. Viqueira. Spatio-temporal models and languages: An approach based on data types. In Spatio-Temporal Databases: The CHOROCHRONOS Approach, pages 117--176. Springer-Verlag, 2003.

[12]

W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. In Conference in modern analysis and probability, pages 189--206. Amer. Math. Soc, 1982.

[13]

P. Laube and S. Imfeld. Analyzing relative motion within groups of trackable moving point objects. In GIScience '02: Proceedings of the Second International Conference on Geographic Information Science, pages 132--144, London, UK, 2002. Springer-Verlag.

Digital Library

[14]

P. Laube, M. van Kreveld, and S. Imfeld. Finding REMO -detecting relative motion patterns in geospatial lifelines. In 11th International Symposium on Spatial Data Handling, pages 201--214, 2004.

[15]

F. Verhein and S. Chawla. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases. In Database Systems for Advanced Applications: 11th International Conference, DASFAA, pages 187--201, Singapore, 2006. Springer Berlin-Heidelberg.

Digital Library

Cited By

Glake DSchmidt MKiehn FPanse FLenfers UClemen TRitter N(2022)Operator Placement for Spatio-temporal Tasks2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020279(281-290)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020279
Atluri GKarpatne AKumar V(2018)Spatio-Temporal Data MiningACM Computing Surveys10.1145/316160251:4(1-41)Online publication date: 22-Aug-2018
https://dl.acm.org/doi/10.1145/3161602
Al-Naymat G(2015)Mitigating the influence of the curse of dimensionality on time series similarity measuresInternational Journal of Computer Applications in Technology10.1504/IJCAT.2015.07142452:1(94-105)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1504/IJCAT.2015.071424
Show More Cited By

Index Terms

Dimensionality reduction for long duration and complex spatio-temporal queries
1. Information systems
  1. Information retrieval

Recommendations

Dimensionality reduction-based spoken emotion recognition

To improve effectively the performance on spoken emotion recognition, it is needed to perform nonlinear dimensionality reduction for speech data lying on a nonlinear manifold embedded in a high-dimensional acoustic space. In this paper, a new supervised ...
A unified framework for semi-supervised dimensionality reduction

In practice, many applications require a dimensionality reduction method to deal with the partially labeled problem. In this paper, we propose a semi-supervised dimensionality reduction framework, which can efficiently handle the unlabeled data. Under ...
Stable local dimensionality reduction approaches

Dimensionality reduction is a big challenge in many areas. A large number of local approaches, stemming from statistics or geometry, have been developed. However, in practice these local approaches are often in lack of robustness, since in contrast to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

March 2007

1688 pages

ISBN:1595934804

DOI:10.1145/1244002

Conference Chairs:
Yookun Cho
Seoul National University, Seoul, Korea
,
Roger L. Wainwright
University of Tulsa, Tulsa, Oklahoma
,
Hisham M. Haddad
Kennesaw State University, Kennesaw, Georgia
,
Sung Y. Shin
South Dakota State University, Brookings, South Dakota
,
Program Chair:
Yong Wan Koo
The University of Suwon, Gyeongggi-do, Korea

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC07

Sponsor:

SIGAPP

SAC07: The 2007 ACM Symposium on Applied Computing

March 11 - 15, 2007

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Glake DSchmidt MKiehn FPanse FLenfers UClemen TRitter N(2022)Operator Placement for Spatio-temporal Tasks2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020279(281-290)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020279
Atluri GKarpatne AKumar V(2018)Spatio-Temporal Data MiningACM Computing Surveys10.1145/316160251:4(1-41)Online publication date: 22-Aug-2018
https://dl.acm.org/doi/10.1145/3161602
Al-Naymat G(2015)Mitigating the influence of the curse of dimensionality on time series similarity measuresInternational Journal of Computer Applications in Technology10.1504/IJCAT.2015.07142452:1(94-105)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1504/IJCAT.2015.071424
Guan TWang K(2015)PGST: Using Personal and Global Factors in the Spatio-Temporal Domain for Mobility Relationship Measurement2015 International Conference on Computer Science and Applications (CSA)10.1109/CSA.2015.28(204-207)Online publication date: Nov-2015
https://doi.org/10.1109/CSA.2015.28
Shaham ESarne DBen-Moshe B(2015)Co-clustering of fuzzy lagged dataKnowledge and Information Systems10.1007/s10115-014-0758-744:1(217-252)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10115-014-0758-7
Zheng KZheng YYuan NShang SZhou X(2014)Online Discovery of Gathering Patterns over TrajectoriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2013.16026:8(1974-1988)Online publication date: Aug-2014
https://doi.org/10.1109/TKDE.2013.160
Wang HLi ZLee W(2014)PGTProceedings of the 2014 IEEE International Conference on Data Mining10.1109/ICDM.2014.111(570-579)Online publication date: 14-Dec-2014
https://dl.acm.org/doi/10.1109/ICDM.2014.111
Guo LHuang GDing Z(2014)Efficient Detection of Emergency Event from Moving Object Data StreamsDatabase Systems for Advanced Applications10.1007/978-3-319-05813-9_28(422-437)Online publication date: 2014
https://doi.org/10.1007/978-3-319-05813-9_28
Li ZDing BWu FLei TKays RCrofoot M(2013)Attraction and avoidance detection from movementsProceedings of the VLDB Endowment10.14778/2732232.27322357:3(157-168)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.14778/2732232.2732235
Li XCeikute VJensen CTan K(2013)Effective Online Group Discovery in Trajectory DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2012.19325:12(2752-2766)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TKDE.2012.193
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten