article

A connectivity index for moving objects in an indoor cellular space

Authors:

Haidar Al-KhalidiAuthors Info & Claims

Personal and Ubiquitous Computing, Volume 18, Issue 2

Pages 287 - 301

https://doi.org/10.1007/s00779-013-0645-3

Published: 01 February 2014 Publication History

Abstract

With the currently available indoor positioning devices such as RFID, Bluetooth and WI-FI, the locations of moving objects constitute an important foundation for a variety of applications such as the tracking of moving objects, security and way finding. Many studies have proven that most individuals spend their lives in indoor environments. Therefore, in this paper, we propose a new index structure for moving objects in cellular space. The index is based on the connectivity (adjacency) between the indoor environment cells and can effectively respond to the spatial indoor queries and enable efficient updates of the location of a moving object in indoor space. An empirical performance study suggests that the proposed indoor-tree in terms of measurements and performance is effective, efficient and robust.

References

[1]

Alamri S, Taniar D, Safar M (2012) Indexing moving objects for directions and velocities queries. Inf Syst Front 1---14.

[2]

Andersson A, Hagerup T, Håstad J, Petersson O (1994) The complexity of searching a sorted array of strings. In: Proceedings of the twenty-sixth annual ACM symposium on theory of computing, STOC '94, pp 317---325, New York, NY, USA

[3]

Chakka VP, Everspaugh A, Patel JM (2003) Indexing large trajectory data sets with SETI. In: CIDR. http://www-db.cs.wisc.edu/cidr/cidr2003/program/p15.pdf

[4]

Chang J-W, Um J-H, LeeP W-C (2006) A new trajectory indexing scheme for moving objects on road networks. In: Bell D, Hong J (eds) Flexible and efficient information handling. Lecture notes in computer science, vol 4042. Springer, Berlin, pp 291---294

[5]

Choi Y-J, Min J-K, Chung C-W (2004) A cost model for spatio-temporal queries using the TPR-tree. J Syst Softw 73(1):101---112

[6]

Forno F, Malnati G, Portelli G (2005) Design and implementation of a Bluetooth ad hoc network for indoor positioning. IEE Proc Softw 152(5):223---228

[7]

Frentzos E (2003) Indexing objects moving on fixed networks. In: Proceedings of the 8th international symposium on spatial and temporal databases (SSTD), Springer, pp 289---305

[8]

Gibbons A (1985) Algorithmic graph theory. Cambridge University Press, Cambridge

[9]

Güting RH, Böhlen MH, Erwig M, Jensen CS, Lorentzos NA, Schneider M, Vazirgiannis M (2000) A foundation for representing and querying moving objects. ACM Trans Database Syst 25(1):1---42

[10]

Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: International conference on management of data, pp 47---57

[11]

Hsu H-H, Chen C-C (2010) Rfid-based human behavior modeling and anomaly detection for elderly care. Mobile Inf Syst 6(4):341---354

[12]

Hu H, Lee DL, Lee VCS (2006) Distance indexing on road networks. In: Proceedings of the 32nd international conference on very large data bases, VLDB '06. VLDB Endowment, pp 894---905

[13]

Jensen C, Lu H, Yang B (2009) Indexing the trajectories of moving objects in symbolic indoor space. In: Nikos M, Thomas S, Torben P, Kristian T, Ira A (eds) Advances in spatial and temporal databases. Lecture notes in computer science, vol 5644. Springer, Berlin, pp 208---227

[14]

Kamel I, Faloutsos C (1994) Hilbert r-tree: An improved r-tree using fractals. In: Proceedings of the 20th international conference on very large data bases, VLDB '94, pp 500---509, San Francisco, CA, USA

[15]

Kang H-Y, Kim J-S, Li K-J (2009) Similarity measures for trajectory of moving objects in cellular space. In: Proceedings of the 2009 ACM symposium on applied computing, SAC '09, pp 1325---1330, New York, NY, USA

[16]

Li Y, Chen H, Xie R, Wang JZ (2011) Bgn: a novel scatternet formation algorithm for bluetooth-based sensor networks. Mobile Inf Syst 7(2):93---106

[17]

Lin D (2006) Indexing and querying moving objects databases. PhD thesis, National University of Singapore, Singapore

[18]

Lin B, Su J (2004) On bulk loading TPR-tree. In: Proceedings of the international conference on mobile data management, pp 114---124

[19]

Lin D, Zhang R, Zhou A (2006) Indexing fast moving objects for knn queries based on nearest landmarks. Geoinformatica 10(4):423---445

[20]

Nascimento MA, Silva JRO (1998) Towards historical R-trees. In: Proceedings of the 1998 ACM symposium on applied computing, SAC '98, pp 235---240, New York, NY, USA

[21]

Okabe A, Boots B, Sugihara K, Chiu SN, Kendall DG (2008) Spatial tessellations: concepts and applications of Voronoi diagrams. In: Spatial tessellations. Wiley, pp 585---655.

[22]

Organero MM, Merino PJM, Kloos CD (2012) Using Bluetooth to implement a pervasive indoor positioning system with minimal requirements at the application level. Mobile Inf Syst 8(1):73---82

[23]

Pfoser D, Jensen CS, Theodoridis Y (2000) Novel approaches to the indexing of moving object trajectories. In: International conference on very large databases, pp 395---406

[24]

Ruiz-Lpez T, Garrido J, Benghazi K, Chung L (2010) A survey on indoor positioning systems: foreseeing a quality design. In: de Leon F. de Carvalho A, Rodrguez-Gonzlez S, De Paz Santana J, Rodrguez J (eds) Distributed computing and artificial intelligence. Advances in intelligent and soft computing, vol 79. Springer, Berlin, pp 373---380

[25]

Saltenis S, Jensen CS, Leutenegger ST, Lopez MA (2000) Indexing the positions of continuously moving objects. SIGMOD Rec 29(2):331---342

[26]

Tao Y, Papadias D (2001) Mv3r-tree: a spatio-temporal access method for timestamp and interval queries. In: Proceedings of the 27th international conference on very large data bases, VLDB '01, pp 431---440, San Francisco, CA, USA

[27]

Tao Y, Papadias D, Sun J (2003) The TPR*-tree: an optimized spatio-temporal access method for predictive queries. In: VLDB, pp 790---801. http://www.vldb.org/conf/2003/papers/S24P01.pdf

[28]

Theodoridis Y, Vazirgiannis M, Sellis TK (1996) Spatio-temporal indexing for large multimedia applications. In: ICMCS, pp 441---448. http://dblp.uni-trier.de

[29]

Waluyo AB, Srinivasan B, Taniar D (2005) Research in mobile database query optimization and processing. Mobile Inf Syst 1(4):225---252

[30]

Wolfson O, Xu B, Chamberlain S, Jiang L (1998) Moving objects databases: issues and solutions. In: Proceedings of tenth international conference on scientific and statistical database management, 1998, pp 111---122

[31]

Yellen J, Gross JL (2005) Graph theory and its applications. Chapman and Hall/CRC, New York, pp 585---655

[32]

Yuan W, Schneider M (2010) Supporting continuous range queries in indoor space. In: Proceedings of the 2010 eleventh international conference on mobile data management, MDM '10, pp 209---214, Washington, DC, USA. IEEE Computer Society

[33]

Zhao G, Xuan K, Rahayu W, Taniar D, Safar M, Gavrilova ML, Srinivasan B (2011) Voronoi-based continuous k nearest neighbor search in mobile navigation. IEEE Trans Ind Electron 58(6):2247---2257

Cited By

Alamri S(2022)Indoor FrameworkInternational Journal of Web Services Research10.4018/IJWSR.31463019:1(1-18)Online publication date: 25-Nov-2022
https://dl.acm.org/doi/10.4018/IJWSR.314630
Alamri S(2022)Anonymous Trajectory Method for Indoor Users for Privacy ProtectionComputational Science and Its Applications – ICCSA 202210.1007/978-3-031-10522-7_8(104-112)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-10522-7_8
Parulian JAdhinugraha KAlamri S(2018)Indoor Navigation Guidance for Mobile DeviceProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282412(345-349)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282412
Show More Cited By

Index Terms

A connectivity index for moving objects in an indoor cellular space

Recommendations

Indexing Moving Objects in Indoor Cellular Space
NBIS '12: Proceedings of the 2012 15th International Conference on Network-Based Information Systems

Researchers have proven that most individuals spend most of their lives indoors. With the current appropriate indoor positioning devices such as Bluetooth and RFID, WIFI, the locations of moving objects will be an important foundation for a variety of ...
Generating semantic-based trajectories for indoor moving objects
WAIM'11: Proceedings of the 2011 international conference on Web-Age Information Management

This paper presents a novel method to generate semantic-based trajectories for indoor moving objects. Indoor moving objects management has been a research focus in recent years. In order to get the trajectory data of indoor moving objects, we have to ...
Spatiotemporal indexing for moving objects in an indoor cellular space

To facilitate a variety of indoor applications, positioning technologies have been developed in indoor spaces (such as WI-FI and RFID). Thus, the requirement for the tracking and monitoring of moving objects in indoor spaces has increased considerably. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Personal and Ubiquitous Computing

Personal and Ubiquitous Computing Volume 18, Issue 2

February 2014

221 pages

ISSN:1617-4909

Issue’s Table of Contents

Copyright © Copyright © 2014 Springer-Verlag London.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
75
Total Downloads

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

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alamri S(2022)Indoor FrameworkInternational Journal of Web Services Research10.4018/IJWSR.31463019:1(1-18)Online publication date: 25-Nov-2022
https://dl.acm.org/doi/10.4018/IJWSR.314630
Alamri S(2022)Anonymous Trajectory Method for Indoor Users for Privacy ProtectionComputational Science and Its Applications – ICCSA 202210.1007/978-3-031-10522-7_8(104-112)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-10522-7_8
Parulian JAdhinugraha KAlamri S(2018)Indoor Navigation Guidance for Mobile DeviceProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282412(345-349)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282412
Kim YJung HJang JKim U(2016)An Efficient Grid Index for Moving Objects in Indoor EnvironmentsProceedings of the 10th International Conference on Ubiquitous Information Management and Communication10.1145/2857546.2857606(1-4)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1145/2857546.2857606
Taniar DRahayu W(2015)A taxonomy for region queries in spatial databasesJournal of Computer and System Sciences10.1016/j.jcss.2014.12.02581:8(1508-1531)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.jcss.2014.12.025
Alamri STaniar DSafarb MAl-Khalidi H(2015)Tracking moving objects using topographical indexingConcurrency and Computation: Practice & Experience10.1002/cpe.316927:8(1951-1965)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1002/cpe.3169
Al-Khalidi HTaniar DBetts JAlamri SMayrhofer RChen LSteinbauer MKotsis GKhalil I(2013)Efficient Monitoring of Moving Mobile Device Range Queries using Dynamic Safe RegionsProceedings of International Conference on Advances in Mobile Computing & Multimedia10.1145/2536853.2536899(351-360)Online publication date: 2-Dec-2013
https://dl.acm.org/doi/10.1145/2536853.2536899

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents