More Web Proxy on the site http://driver.im/

Article

Efficient constraint processing for location-aware computing

Authors:

Hans-Arno JacobsenAuthors Info & Claims

MDM '05: Proceedings of the 6th international conference on Mobile data management

Pages 3 - 12

https://doi.org/10.1145/1071246.1071248

Published: 09 May 2005 Publication History

Abstract

For many applications, such as friend finder, buddy tracking, and location mapping in mobile wireless networks or information sharing and cooperative caching in mobile ad hoc networks, it is often important to be able to identify whether a given set of moving objects is close to each other or close to a given point of demarcation. To achieve this, continuously available location position information of thousands of mobile objects must be correlated against each other to identify whether a fixed set of objects is in a certain proximity relation, which, if satisfied, would be signaled to the objects or any interested party. In this paper, we state this problem, referring to it as the location constraint matching problem and present and evaluate solutions for solving it. We introduce two types of location constraints to model the proximity relations and experimentally validate that our solution scales to the processing of hundreds of thousands of constraints and moving objects.

References

[1]

New and enhanced features of fedex insight. http://www.fedex.com/us/.

[2]

Radio frequency identification systems (RFID). http://www.ti.com/tiris/docs/solutions/animal/livestock.shtml.

[3]

Pankaj K. Agarwal, Lars Arge, and Jeff Erickson. Indexing moving points. In Symposium on Principles of Database Systems, pages 175--186, 2000.

Digital Library

[4]

Basch, Guibas, and Hershberger. Data structures for mobile data. In SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), 1997.

Digital Library

[5]

Jon Louis Bentley. Multidimensional binary search trees used for associative searching. In Communications of the ACM., pages 18:509--517, 1975.

Digital Library

[6]

Mark De Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational geometry. Springer-Verlag New York, 2000.

[7]

Alexander Brodsky and Yoram Kornatzky. The lyric language: Querying constraint objects. In SIGMOD Conference, pages 35--46, 1995.

Digital Library

[8]

Ioana Burcea and Hans-Arno Jacobsen. L-ToPSS - Push-oriented Location-based Services. In 4th VLDB Workshop on Technologies for E-Services (TES'03), 2003.

[9]

Ioana Burcea, Hans-Arno Jacobsen, Eyal de Lara, Vinod Muthusamy, and Milenko Petrovic. Disconnected Operation in Publish/Subscribe Middleware. 2004 IEEE International Conference on Mobile Data Management.

[10]

Françoise Fabret, H. Arno Jacobsen, François Llirbat, João Pereira, Kenneth A. Ross, and Dennis Shasha. Filtering algorithms and implementation for very fast publish/subscribe systems. SIGMOD, 30(2):115--126, 2001.

Digital Library

[11]

Leonid Libkin Gabriel Kuper and Jan Paredaens. Constraint databases. Springer Verlag, 2000.

[12]

Volker Gaede and Oliver Günther. Multidimensional access methods. ACM Computing Surveys, 30(2):170--231, 1998.

Digital Library

[13]

James Kaufman Jussi Myllymaki and Jared Jackson. City Simulator. IBM alphaworks emerging technologies toolkit, http://www.alphaworks.ibm.com/tech/citysimulator, November 2001.

[14]

Ibrahim Kamel and Christos Faloutsos. Hilbert R-tree: An Improved R-tree using Fractals. In Proceedings of the Twentieth International Conference on Very Large Databases, pages 500--509, Santiago, Chile, 1994.

Digital Library

[15]

David R. Karger. Finding nearest neighbors in growth-restricted metrics. In In Proc. ACM Symposium on Theory of Computing (STOC '02), 2002.

Digital Library

[16]

George Kollios, Dimitrios Gunopulos, and Vassilis J. Tsotras. On indexing mobile objects. In Proceedings of the 18th ACM PODS Conference, May 31 - June 2, 1999, Philadelphia, Pennsylvania, pages 261--272. ACM Press, 1999.

Digital Library

[17]

Gouli Li, Shuang Hou, and Hans-Arno Jacobsen. A Unified Approach to Routing, Covering and Merging in Publish/Subscribe Systems based on Modified Binary Decision Diagrams. International Conference on Distributed Computing Systems (ICDCS'05).

Digital Library

[18]

Haifeng Liu and H-Arno Jacobsen. Modeling uncertainties in Publish/Subscribe System. In In Proceedings of ICDE, 2004.

Digital Library

[19]

David B. Lomet and Betty Salzberg. A robust multiattribute search structure. In Proc. 5th ICDE, pages 296--304, 1989.

Digital Library

[20]

Jussi Myllymaki and James Kaufman. Location Transponder. IBM alphaworks emerging technologies toolkit, http://www.alphaworks.ibm.com/tech/transponder, April 2002.

[21]

Hinterberger H. Nievergelt, J. and K. C. Sevcik. The grid file: An adaptable, symmetric multikey file structure. In ACM Trans. Database systems 9, 1984.

Digital Library

[22]

Jeff Erickson Pankaj K. Agarwal, Lars Arge. Indexing moving points. In In Proc. 19th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.

Digital Library

[23]

Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. Towards a theory of spatial database queries (extended abstract). In Proc. ACM PODS, 1994.

Digital Library

[24]

Milenko Petrovic, Ioana Burcea, and H.-Arno Jacobsen. S-ToPSS - a semantic publish/subscribe system. In Very Large Databases (VLDB '03), Berlin, Germany, September 2003.

Digital Library

[25]

Milenko Petrovic, Haifeng Liu, and Hans-Arno Jacobsen. G-ToPSS - fast filtering of graph-based metadata. In the 14th International World Wide Web Conference (WWW2005, Chiba, Japan, May 2005.

Digital Library

[26]

Elizabeth M. Royer. P. Michael Melliar-Smith, and Louise E. Moser. An analysis of the optimum node density for ad hoc mobile networks. In Proceedings of the IEEE International Conference on Communications, pages 857--861, June 2001.

[27]

Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, and Mario A. Lopez. Indexing the positions of continuously moving objects. In Proceedings of the 2000 ACM SIGMOD, Dallas, Texas, USA.

Digital Library

[28]

Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. The R-Tree: A dynamic index for multi-dimensional objects. In The VLDB Journal, pages 507--518, 1987.

Digital Library

[29]

Dimitri Kalashnikov Walid Aref Susanne E. Hambrusch Sunil Prabhakar, Yuni Xia. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Transactions on Computers, 51(10):1124--1140, October 2002.

Digital Library

[30]

Arnon Amir. Alon Efrat. Jussi Myllymaki. Lingeshwaran Palaniappan. Kevin Wampler. Buddy tracking - efficient proximity detection among mobile friends. In Infocom 2004.

[31]

Roy Want, Andy Hopper, Veronica Falcão, and Jonathan Gibbons. The active badge location system. Technical Report 92.1, Olivetti Research Ltd. (ORL), 24a Trumpington Street, Cambridge CB2 1QA, 1992.

Digital Library

[32]

Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, LNCS. Springer, 1991.

[33]

Zhengdao Xu and H. Arno Jacobsen. Efficient constraint processing for highly personalized location based services. In 30th International Conference on Very Large Data Bases (VLDB04) Toronto, Canada, 2004.

Digital Library

[34]

Zhengdao Xu and H. Arno Jacobsen. A framework for location information processing. In 6th International Conference on Mobile Data Management (MDM'05), Ayia Napa, Cyprus, 2005.

Digital Library

[35]

Jun Zhang, Manli Zhu, Dimitris Papadias, Yufei Tao, and Dik Lun Lee. Location-based spatial queries. In SIGMOD Conference, 2003.

Digital Library

[36]

Yilin Zhao. Standardization of mobile phone positioning for 3G systems. IEEE Communication Magazine, July 2002.

Digital Library

Cited By

Yan DZhao ZNg W(2020)Efficient algorithms for finding optimal meeting point on road networksProceedings of the VLDB Endowment10.14778/3402707.34027344:11(968-979)Online publication date: 3-Jun-2020
https://doi.org/10.14778/3402707.3402734
Treu GKüpper AWilder T(2019)Extending the LBS-framework TraXComputer Communications10.1016/j.comcom.2007.12.01331:5(1040-1051)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2007.12.013
Fu KAlencar PBlanco RBarrenechea ECowan D(2012)Spatial Subscriptions in Distributed Event-Based SystemsHandbook of Research on Mobile Software Engineering10.4018/978-1-61520-655-1.ch044(809-823)Online publication date: 2012
https://doi.org/10.4018/978-1-61520-655-1.ch044
Show More Cited By

Index Terms

Efficient constraint processing for location-aware computing
1. Information systems
  1. Information retrieval
  2. Information systems applications

Recommendations

Expressive Location-Based Continuous Query Evaluation with Binary Decision Diagrams
ICDE '09: Proceedings of the 2009 IEEE International Conference on Data Engineering

Many location-based services require rich and expressive query language support for filtering large amounts of information over thousands of concurrently executing continuous queries. Parts of these queries may overlap or logically depend on each other ...
Adaptive location constraint processing
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

An important problem for many location-based applications is the continuous evaluation of proximity relations among moving objects. These relations express whether a given set of objects is in a spatial constellation or in a spatial constellation ...
Personalized Location Recommendation System Personalized Location Recommendation System: A Review

Location acquisition and wireless communication technologies are growing in location-based social networks. With the rapid development of location-based social networks LBSNs, location recommendation has become an important for helping users to discover ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MDM '05: Proceedings of the 6th international conference on Mobile data management

May 2005

329 pages

ISBN:1595930418

DOI:10.1145/1071246

Conference Chairs:
Panos K. Chrysanthis
U. of Pittsburgh, USA
,
George Samaras
U. of Cyprus, Cyprus

Copyright © 2005 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MDM05

Sponsor:

MDM05: International Conference on mobile Data Management

May 9 - 13, 2005

Ayia Napa, Cyprus

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
582
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yan DZhao ZNg W(2020)Efficient algorithms for finding optimal meeting point on road networksProceedings of the VLDB Endowment10.14778/3402707.34027344:11(968-979)Online publication date: 3-Jun-2020
https://doi.org/10.14778/3402707.3402734
Treu GKüpper AWilder T(2019)Extending the LBS-framework TraXComputer Communications10.1016/j.comcom.2007.12.01331:5(1040-1051)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2007.12.013
Fu KAlencar PBlanco RBarrenechea ECowan D(2012)Spatial Subscriptions in Distributed Event-Based SystemsHandbook of Research on Mobile Software Engineering10.4018/978-1-61520-655-1.ch044(809-823)Online publication date: 2012
https://doi.org/10.4018/978-1-61520-655-1.ch044
Xu ZJacobsen HElmagarmid AAgrawal D(2010)Processing proximity relations in road networksProceedings of the 2010 ACM SIGMOD International Conference on Management of data10.1145/1807167.1807196(243-254)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807167.1807196
Decker MStürzel PKlink SOberweis A(2009)Location Constraints for Mobile WorkflowsProceedings of the 2009 conference on Techniques and Applications for Mobile Commerce: Proceedings of TAMoCo 200910.5555/1659364.1659377(93-102)Online publication date: 21-Jul-2009
https://dl.acm.org/doi/10.5555/1659364.1659377
Romsaiyud WPremchaisawasdi W(2009)Intelligent switching method using Cell-ID/GPS positioning on mobile application2009 7th International Conference on ICT and Knowledge Engineering10.1109/ICTKE.2009.5397330(83-88)Online publication date: Dec-2009
https://doi.org/10.1109/ICTKE.2009.5397330
Treu GKüpper ANeukum OLinnhoff-Popien CLin JChao HChong P(2008)Efficient clique detection among mobile targetsProceedings of the International Conference on Mobile Technology, Applications, and Systems10.1145/1506270.1506308(1-8)Online publication date: 10-Sep-2008
https://dl.acm.org/doi/10.1145/1506270.1506308
Xu ZJacobsen AZhou LLing TOoi B(2007)Adaptive location constraint processingProceedings of the 2007 ACM SIGMOD international conference on Management of data10.1145/1247480.1247545(581-592)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1247480.1247545
Deblauwe NRuppel P(2007)Combining GPS and GSM Cell-ID positioning for Proactive Location-based ServicesProceedings of the 2007 Fourth Annual International Conference on Mobile and Ubiquitous Systems: Networking&Services (MobiQuitous)10.1109/MOBIQ.2007.4450985(1-7)Online publication date: 6-Aug-2007
https://dl.acm.org/doi/10.1109/MOBIQ.2007.4450985
Xu ZJacobsen H(2007)Evaluating Proximity Relations Under Uncertainty2007 IEEE 23rd International Conference on Data Engineering10.1109/ICDE.2007.367933(876-885)Online publication date: Apr-2007
https://doi.org/10.1109/ICDE.2007.367933
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