research-article

An RFID and particle filter-based indoor spatial query evaluation system

Authors:

Hua LuAuthors Info & Claims

EDBT '13: Proceedings of the 16th International Conference on Extending Database Technology

Pages 263 - 274

https://doi.org/10.1145/2452376.2452408

Published: 18 March 2013 Publication History

Abstract

People spend a significant amount of time in indoor spaces (e.g., office buildings, subway systems, etc.) in their daily lives. Therefore, it is important to develop efficient indoor spatial query algorithms for supporting various location-based applications. However, indoor spaces differ from outdoor spaces because users have to follow the indoor floor plan for their movements. In addition, positioning in indoor environments is mainly based on sensing devices (e.g., RFID readers) rather than GPS devices. Consequently, we cannot apply existing spatial query evaluation techniques devised for outdoor environments for this new challenge. Because particle filters can be employed to estimate the state of a system that changes over time using a sequence of noisy measurements made on the system, in this research, we propose the particle filter-based location inference method as the basis for evaluating indoor spatial queries with noisy RFID raw data. Furthermore, two novel models, indoor walking graph model and anchor point indexing model, are created for tracking object locations in indoor environments. Based on the inference method and tracking models, we develop innovative indoor range and k nearest neighbor (kNN) query algorithms. We validate our solution through extensive simulations with real-world parameters. Our experimental results show that the proposed algorithms can evaluate indoor spatial queries effectively and efficiently.

References

[1]

M. S. Arulampalam, S. Maskell, N. J. Gordon, and T. Clapp. A tutorial on particle filters for online nonlinear/non-gaussian bayesian tracking. IEEE Transactions on Signal Processing, 50(2):174--188, 2002.

Digital Library

[2]

L. Carlone, M. E. K. Ng, J. Du, B. Bona, and M. Indri. Rao-Blackwellized Particle Filters multi robot SLAM with unknown initial correspondences and limited communication. In ICRA, pages 243--249, 2010.

[3]

H. Chen, W.-S. Ku, H. Wang, and M.-T. Sun. Leveraging spatio-temporal redundancy for RFID data cleansing. In SIGMOD Conference, pages 51--62, 2010.

Digital Library

[4]

R. Cheng, L. Chen, J. Chen, and X. Xie. Evaluating probability threshold k-nearest-neighbor queries over uncertain data. In EDBT, pages 672--683, 2009.

Digital Library

[5]

N. Gordon, D. Salmond, and A. Smith. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F on Radar and Signal Processing, 140(2):107--113, apr 1993.

[6]

G. R. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. ACM Trans. Database Syst., 24(2):265--318, 1999.

Digital Library

[7]

S. R. Jeffery, M. J. Franklin, and M. N. Garofalakis. An Adaptive RFID Middleware for Supporting Metaphysical Data Independence. VLDB J., 17(2):265--289, 2008.

Digital Library

[8]

S. R. Jeffery, M. N. Garofalakis, and M. J. Franklin. Adaptive Cleaning for RFID Data Streams. In VLDB, pages 163--174, 2006.

Digital Library

[9]

C. S. Jensen, H. Lu, and B. Yang. Graph Model Based Indoor Tracking. In Mobile Data Management, pages 122--131, 2009.

Digital Library

[10]

W.-S. Ku, H. Chen, H. Wang, and M.-T. Sun. A Bayesian Inference-Based Framework for RFID Data Cleansing. IEEE Trans. Knowl. Data Eng., In press, 2012.

[11]

S. Kullback and R. A. Leibler. On Information and Sufficiency. Annals of Mathematical Statistics, 22:49--86, 1951.

[12]

K. C. K. Lee, W.-C. Lee, B. Zheng, and Y. Tian. ROAD: A New Spatial Object Search Framework for Road Networks. IEEE Trans. Knowl. Data Eng., 24(3):547--560, 2012.

Digital Library

[13]

J. Letchner, C. Ré, M. Balazinska, and M. Philipose. Access Methods for Markovian Streams. In ICDE, pages 246--257, 2009.

Digital Library

[14]

D. Li and D. L. Lee. A Lattice-Based Semantic Location Model for Indoor Navigation. In MDM, pages 17--24, 2008.

Digital Library

[15]

Metropolitan Transportation Authority. Subway and Bus Ridership Statistics 2011. http://mta.info/nyct/facts/ridership/index.htm. Retrieved on October 22, 2012.

[16]

D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query Processing in Spatial Network Databases. In VLDB, pages 802--813, 2003.

Digital Library

[17]

C. Ré, J. Letchner, M. Balazinska, and D. Suciu. Event queries on correlated probabilistic streams. In SIGMOD Conference, pages 715--728, 2008.

Digital Library

[18]

N. Roussopoulos, S. Kelley, and F. Vincent. Nearest Neighbor Queries. In SIGMOD Conference, pages 71--79, 1995.

Digital Library

[19]

H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In SIGMOD Conference, pages 43--54, 2008.

Digital Library

[20]

B. L. D. Santos and L. S. Smith. RFID in the Supply Chain: Panacea or Pandora's Box? Commun. ACM, 51(10):127--131, 2008.

Digital Library

[21]

L. Sullivan. RFID Implementation Challenges Persist, All This Time Later. InformationWeek, October 2005.

[22]

T. T. L. Tran, C. Sutton, R. Cocci, Y. Nie, Y. Diao, and P. J. Shenoy. Probabilistic Inference over RFID Streams in Mobile Environments. In ICDE, pages 1096--1107, 2009.

Digital Library

[23]

R. Want. The Magic of RFID. ACM Queue, 2(7):40--48, 2004.

Digital Library

[24]

E. Welbourne, L. Battle, G. Cole, K. Gould, K. Rector, S. Raymer, M. Balazinska, and G. Borriello. Building the Internet of Things Using RFID: The RFID Ecosystem Experience. IEEE Internet Computing, 13(3):48--55, 2009.

Digital Library

[25]

E. Welbourne, N. Khoussainova, J. Letchner, Y. Li, M. Balazinska, G. Borriello, and D. Suciu. Cascadia: a system for specifying, detecting, and managing rfid events. In MobiSys, pages 281--294, 2008.

Digital Library

[26]

E. Welbourne, K. Koscher, E. Soroush, M. Balazinska, and G. Borriello. Longitudinal study of a building-scale rfid ecosystem. In MobiSys, pages 69--82, 2009.

Digital Library

[27]

J. Welle, D. Schulz, T. Bachran, and A. B. Cremers. Optimization techniques for laser-based 3D particle filter SLAM. In ICRA, pages 3525--3530, 2010.

[28]

Wikipedia. New York City Subway. http://en.wikipedia.org/wiki/New_York_City_Subway. Retrieved on October 22, 2012.

[29]

B. Yang, H. Lu, and C. S. Jensen. Scalable continuous range monitoring of moving objects in symbolic indoor space. In CIKM, pages 671--680, 2009.

Digital Library

[30]

B. Yang, H. Lu, and C. S. Jensen. Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space. In EDBT, pages 335--346, 2010.

Digital Library

[31]

L. Yang, J. Cao, W. Zhu, and S. Tang. A hybrid method for achieving high accuracy and efficiency in object tracking using passive rfid. In PerCom, pages 109--115, 2012.

Cited By

Li HLiu TChan HLu H(2022)Spatial data analysis for intelligent buildings: Awareness of context and data uncertaintyFrontiers in Big Data10.3389/fdata.2022.10491985Online publication date: 7-Nov-2022
https://doi.org/10.3389/fdata.2022.1049198
Chan HLi HLi XLu H(2022)Continuous social distance monitoring in indoor spaceProceedings of the VLDB Endowment10.14778/3523210.352321715:7(1390-1402)Online publication date: Mar-2022
https://doi.org/10.14778/3523210.3523217
Li HTang BLu HCheema MJensen CIves ZBonifati AEl Abbadi A(2022)Spatial Data Quality in the IoT Era: Management and ExploitationProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3522568(2474-2482)Online publication date: 11-Jun-2022
https://doi.org/10.1145/3514221.3522568
Show More Cited By

Index Terms

An RFID and particle filter-based indoor spatial query evaluation system
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

Indoor Localization Based on Beacons and Calculated by Particle Filter
CompSysTech '16: Proceedings of the 17th International Conference on Computer Systems and Technologies 2016

In this paper we discuss a usage of particle filter for the purpose of indoor localization based on signal strength. We used beacons - Bluetooth Low Energy (BLE) transmitters - as a source of signal. Received signal strength (RSS) fluctuates over time ...
Performance Evaluation of Real-Time Indoor Positioning with Active-RFID and CSS-Based Nano Lock System
NCM '09: Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDC

Various indoor positioning methods have been proposed both in theory and practice. Each method has different degree of accuracy. Due to the smaller indoor venues, the torrent for error is also smaller. Therefore, indoor positioning system requires more ...
Kalman filter vs. particle filter in improving K-NN indoor positioning
KES'11: Proceedings of the 15th international conference on Knowledge-based and intelligent information and engineering systems - Volume Part II

The Kalman filter has been widely used in estimating the state of a process and it is well known that no other algorithm can out-perform it if the assumptions of the Kalman filter hold. For a non-Gaussian estimation problem, both the extended Kalman ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

EDBT '13: Proceedings of the 16th International Conference on Extending Database Technology

March 2013

793 pages

ISBN:9781450315975

DOI:10.1145/2452376

General Chair:
Giovanna Guerrini
Università di Genova, Italy
,
Program Chair:
Norman W. Paton
University of Manchester, UK

Copyright © 2013 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EDBT/ICDT '13

EDBT/ICDT '13: Joint 2013 EDBT/ICDT Conferences

March 18 - 22, 2013

Genoa, Italy

Acceptance Rates

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
315
Total Downloads

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

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li HLiu TChan HLu H(2022)Spatial data analysis for intelligent buildings: Awareness of context and data uncertaintyFrontiers in Big Data10.3389/fdata.2022.10491985Online publication date: 7-Nov-2022
https://doi.org/10.3389/fdata.2022.1049198
Chan HLi HLi XLu H(2022)Continuous social distance monitoring in indoor spaceProceedings of the VLDB Endowment10.14778/3523210.352321715:7(1390-1402)Online publication date: Mar-2022
https://doi.org/10.14778/3523210.3523217
Li HTang BLu HCheema MJensen CIves ZBonifati AEl Abbadi A(2022)Spatial Data Quality in the IoT Era: Management and ExploitationProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3522568(2474-2482)Online publication date: 11-Jun-2022
https://doi.org/10.1145/3514221.3522568
Li HLu HJensen CTang BCheema M(2022)Spatial Data Quality in the Internet of Things: Management, Exploitation, and ProspectsACM Computing Surveys10.1145/349833855:3(1-41)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3498338
Hui BJiang CAnkireddy PWang WKu W(2021)Indoor Navigation for Users with Mobility Aids Using Smartphones and Neighborhood Networks2021 17th International Conference on Mobility, Sensing and Networking (MSN)10.1109/MSN53354.2021.00103(681-682)Online publication date: Dec-2021
https://doi.org/10.1109/MSN53354.2021.00103
Sakai KSun MKu WLu HLai T(2019)Data Verification in Integrated RFID SystemsIEEE Systems Journal10.1109/JSYST.2018.286557113:2(1969-1980)Online publication date: Jun-2019
https://doi.org/10.1109/JSYST.2018.2865571
Li HLu HShou LChen GChen K(2018)Finding Most Popular Indoor Semantic Locations Using Uncertain Mobility DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.2875096(1-1)Online publication date: 2018
https://doi.org/10.1109/TKDE.2018.2875096
Li HLu HShou LChen GChen K(2018)In Search of Indoor Dense Regions: An Approach Using Indoor Positioning DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.279921530:8(1481-1495)Online publication date: 1-Aug-2018
https://doi.org/10.1109/TKDE.2018.2799215
Teng SOu CChuang K(2018)On the discovery of spatial-temporal fluctuating patternsInternational Journal of Data Science and Analytics10.1007/s41060-018-0159-18:1(57-75)Online publication date: 4-Dec-2018
https://doi.org/10.1007/s41060-018-0159-1
Fazzinga BFlesca SFurfaro FParisi F(2017)Using integrity constraints to guide the interpretation of RFID-trajectory dataSIGSPATIAL Special10.1145/3151123.31511289:2(28-35)Online publication date: 10-Oct-2017
https://dl.acm.org/doi/10.1145/3151123.3151128
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.

Media

Figures

Other

Tables

View Table of Contents