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

research-article

An efficient query indexing mechanism for filtering geo-textual data

Authors:

Xin CaoAuthors Info & Claims

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Pages 749 - 760

https://doi.org/10.1145/2463676.2465328

Published: 22 June 2013 Publication History

Abstract

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale. Users may want to be notified of interesting geo-textual objects during a period of time. For example, a user may want to be informed when tweets containing term "garage sale" are posted within 5 km of the user's home in the next 72 hours.

In this paper, for the first time we study the problem of matching a stream of incoming Boolean Range Continuous queries over a stream of incoming geo-textual objects in real time. We develop a new system for addressing the problem. In particular, we propose a hybrid index, called IQ-tree, and novel cost models for managing a stream of incoming Boolean Range Continuous queries. We also propose algorithms for matching the queries with incoming geo-textual objects based on the index. Results of empirical studies with implementations of the proposed techniques demonstrate that the paper's proposals offer scalability and are capable of excellent performance.

References

[1]

V. Botea, D. Mallett, M. A. Nascimento, and J. Sander. Pist: An efficient and practical indexing technique for historical spatio-temporal point data. GeoInformatica, 12(2):143--168, 2008.

Digital Library

[2]

X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu. Spatial keyword querying. In ER, pages 16--29, 2012.

Digital Library

[3]

X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In SIGMOD, pages 373--384, 2011.

Digital Library

[4]

U. Çetintemel, M. J. Franklin, and C. L. Giles. Self-adaptive user profiles for large-scale data delivery. In ICDE, pages 622--633, 2000.

Digital Library

[5]

J. Chen, D. J. DeWitt, F. Tian, and Y.Wang. Niagaracq: a scalable continuous query system for internet databases. In SIGMOD, pages 379--390, 2000.

Digital Library

[6]

S. Chen, B. C. Ooi, K.-L. Tan, and M. A. Nascimento. St2b-tree: a self-tunable spatio-temporal b+-tree index for moving objects. In SIGMOD, pages 29--42, 2008.

Digital Library

[7]

M. Christoforaki, J. He, C. Dimopoulos, A. Markowetz, and T. Suel. Text vs. space: efficient geo-search query processing. In CIKM, pages 423--432, 2011.

Digital Library

[8]

G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2(1):337--348, 2009.

Digital Library

[9]

P. Cudré-Mauroux, E.Wu, and S. Madden. Trajstore: An adaptive storage system for very large trajectory data sets. In ICDE, pages 109--120, 2010.

[10]

F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe systems. In SIGMOD, pages 115--126, 2001.

Digital Library

[11]

I. D. Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, pages 656--665, 2008.

Digital Library

[12]

P. W. Foltz and S. T. Dumais. Personalized information delivery: an analysis of information filtering methods. Commun. ACM, 35(12):51--60, Dec. 1992.

Digital Library

[13]

M. F. Mokbel, X. Xiong, and W. G. Aref. Sina: scalable incremental processing of continuous queries in spatio-temporal databases. In SIGMOD, pages 623--634, 2004.

Digital Library

[14]

K. Mouratidis and H. Pang. Efficient evaluation of continuous text search queries. IEEE Trans. Knowl. Data Eng., 23(10):1469--1482, 2011.

Digital Library

[15]

K. Mouratidis, D. Papadias, and M. Hadjieleftheriou. Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring. In SIGMOD, pages 634--645, 2005.

Digital Library

[16]

J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvåg. Efficient processing of top-k spatial keyword queries. In SSTD, pages 205--222, 2011.

Digital Library

[17]

M. Singh, Q. Zhu, and H. V. Jagadish. Swst: A disk based index for sliding window spatio-temporal data. In ICDE, pages 342--353, 2012.

Digital Library

[18]

Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In VLDB, pages 790--801, 2003.

Digital Library

[19]

S. Vaid, C. B. Jones, H. Joho, and M. Sanderson. Spatio-textual indexing for geographical search on the web. In SSTD, pages 218--235, 2005.

Digital Library

[20]

D. Wu, M. L. Yiu, C. S. Jensen, and G. Cong. Efficient continuously moving top-k spatial keyword query processing. In ICDE, pages 541--552, 2011.

Digital Library

[21]

X. Xiong and W. G. Aref. R-trees with update memos. In ICDE, page 22, 2006.

Digital Library

[22]

T. W. Yan and H. García-Molina. Index structures for selective dissemination of information under the boolean model. ACM Trans. Database Syst., 19(2):332--364, June 1994.

Digital Library

[23]

T. W. Yan and H. Garcia-Molina. Duplicate removal in information system dissemination. In VLDB, pages 66--77, 1995.

Digital Library

[24]

B. Yao, F. Li, M. Hadjieleftheriou, and K. Hou. Approximate string search in spatial databases. In ICDE, pages 545--556, 2010.

[25]

D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, pages 688--699, 2009.

Digital Library

Cited By

Keller SMueller R(2024)Individual Dynamic Real-Time Range Queries in Adaptive Quad Streaming2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637619(1-9)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637619
Chen ZCong GAref W(2023)STAR: A Cache-based Stream Warehouse System for Spatial DataACM Transactions on Spatial Algorithms and Systems10.1145/36059449:4(1-27)Online publication date: 27-Jun-2023
https://dl.acm.org/doi/10.1145/3605944
Teng XTrajcevski GZüfle A(2023)Distance, Origin and Category Constrained PathsACM Transactions on Spatial Algorithms and Systems10.1145/3596601Online publication date: 8-May-2023
https://doi.org/10.1145/3596601
Show More Cited By

Index Terms

An efficient query indexing mechanism for filtering geo-textual data
1. Information systems
  1. Information retrieval
    1. Document representation
    2. Search engine architectures and scalability
      1. Search engine indexing

Recommendations

Querying Geo-Textual Data: Spatial Keyword Queries and Beyond
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Over the past decade, we have moved from a predominantly desktop based web to a predominantly mobile web, where users most often access the web from mobile devices such as smartphones. In addition, we are witnessing a proliferation of geo-located, ...
Efficient filtering query indexing in data stream
WISE'06: Proceedings of the 7th international conference on Web Information Systems

Filtering queries are widely used in data stream applications. As more and more filtering queries are registered in high-speed data stream management system, the processing efficiency becomes crucial. This paper presents an efficient query index ...
Interval query indexing for efficient stream processing
CIKM '04: Proceedings of the thirteenth ACM international conference on Information and knowledge management

A large number of continual range queries can be issued against a data stream. Usually, a main memory-based query index with a small storage cost and a fast search time is needed, especially if the stream is rapid. In this paper, we present a CEI-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

June 2013

1322 pages

ISBN:9781450320375

DOI:10.1145/2463676

General Chairs:
Kenneth Ross
Columbia University
,
Divesh Srivastava
AT&T Research
,
Program Chair:
Dimitris Papadias
HKUST

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]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
1,406
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)5

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Keller SMueller R(2024)Individual Dynamic Real-Time Range Queries in Adaptive Quad Streaming2024 33rd International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN61486.2024.10637619(1-9)Online publication date: 29-Jul-2024
https://doi.org/10.1109/ICCCN61486.2024.10637619
Chen ZCong GAref W(2023)STAR: A Cache-based Stream Warehouse System for Spatial DataACM Transactions on Spatial Algorithms and Systems10.1145/36059449:4(1-27)Online publication date: 27-Jun-2023
https://dl.acm.org/doi/10.1145/3605944
Teng XTrajcevski GZüfle A(2023)Distance, Origin and Category Constrained PathsACM Transactions on Spatial Algorithms and Systems10.1145/3596601Online publication date: 8-May-2023
https://doi.org/10.1145/3596601
Li YGu HChen RXu JGuo SXue JXu M(2023) Efficient Top- k Matching for Publish/Subscribe Ride Hitching IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.312423235:4(3808-3821)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TKDE.2021.3124232
Chen YFeng KCong GKiah H(2022)Example-based spatial pattern matchingProceedings of the VLDB Endowment10.14778/3551793.355181515:11(2572-2584)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551815
Wu DKeles IWu SZhou HSaltenis SJensen CLu K(2022)Density-Based Top-K Spatial Textual Clusters RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.304978534:11(5263-5277)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TKDE.2021.3049785
Deng ZWang YLiu TDustdar SRanjan RZomaya ALiu YWang L(2022)Spatial-Keyword Skyline Publish/Subscribe Query Processing Over Distributed Sliding Window Streaming DataIEEE Transactions on Computers10.1109/TC.2022.314088471:10(2659-2674)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TC.2022.3140884
Patil M(2022)Learning to Process Topic Aware Queries on Geo-Textual Streaming Data2022 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00063(443-450)Online publication date: Dec-2022
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00063
Zhong YLi JZhu S(2022)Continuous spatial keyword search with query result diversificationsWorld Wide Web10.1007/s11280-022-01118-y26:4(1935-1948)Online publication date: 25-Nov-2022
https://doi.org/10.1007/s11280-022-01118-y
Liu HSun YWang G(2022)Continuous similarity join over geo-textual data streamsWorld Wide Web10.1007/s11280-022-01063-w26:3(933-947)Online publication date: 2-Jun-2022
https://doi.org/10.1007/s11280-022-01063-w
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