ESPM: Efficient Spatial Pattern Matching

Chen, H; Fang, Y; Zhang, Y; Zhang, W; Wang, L

ESPM: Efficient Spatial Pattern Matching

Chen, H Fang, Y Zhang, Y

Zhang, W Wang, L

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2020, 32, (6), pp. 1227-1233
Issue Date:: 2020-06-01

Closed Access

	Filename	Description	Size
	TKDE_20_ESPM.pdf		763.48 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chen, H
dc.contributor.author	Fang, Y
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Zhang, W
dc.contributor.author	Wang, L
dc.date.accessioned	2020-11-03T00:44:37Z
dc.date.available	2020-11-03T00:44:37Z
dc.date.issued	2020-06-01
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2020, 32, (6), pp. 1227-1233
dc.identifier.issn	1041-4347
dc.identifier.issn	1558-2191
dc.identifier.uri	http://hdl.handle.net/10453/143699
dc.description.abstract	© 1989-2012 IEEE. With recent advances in information technologies such as global position system and mobile internet, a huge volume of spatio-textual objects have been generated from location-based services, which enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture the user's intention. It has been demonstrated to be fundamental and useful for many real applications. Despite its usefulness, the SPM problem is computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. We experimentally evaluate the performance of ESPM on real large datasets. Our results show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2019.2947505
dc.rights	© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.	en_US
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.title	ESPM: Efficient Spatial Pattern Matching
dc.type	Journal Article
utslib.citation.volume	32
utslib.for	08 Information and Computing Sciences
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	closed_access	*
dc.date.updated	2020-11-03T00:44:32Z
pubs.issue	6
pubs.publication-status	Published
pubs.volume	32
utslib.citation.issue	6

Abstract:

© 1989-2012 IEEE. With recent advances in information technologies such as global position system and mobile internet, a huge volume of spatio-textual objects have been generated from location-based services, which enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture the user's intention. It has been demonstrated to be fundamental and useful for many real applications. Despite its usefulness, the SPM problem is computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. We experimentally evaluate the performance of ESPM on real large datasets. Our results show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/143699