ESPM: Efficient spatial pattern matching (Extended Abstract)

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

ESPM: Efficient spatial pattern matching (Extended Abstract)

Chen, H Fang, Y Zhang, Y

Zhang, W Wang, L

Permalink

Publisher:: IEEE
Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2020, 2020-April, pp. 2038-2039
Issue Date:: 2020-04-01

Closed Access

	Filename	Description	Size
	ICDE_extend.pdf	Accepted version	171.97 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	2020-04-20
dc.date.accessioned	2020-11-03T01:36:19Z
dc.date.available	2020-11-03T01:36:19Z
dc.date.issued	2020-04-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2020, 2020-April, pp. 2038-2039
dc.identifier.isbn	9781728129037
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/143718
dc.description.abstract	© 2020 IEEE. A huge volume of spatio-textual objects generated from location-based services 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 users' intention. It has been demonstrated to be useful but 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. Our experimental results on real large datasets 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	IEEE
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	Proceedings - International Conference on Data Engineering
dc.relation.ispartof	2020 IEEE 36th International Conference on Data Engineering (ICDE)
dc.relation.isbasedon	10.1109/ICDE48307.2020.00238
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.title	ESPM: Efficient spatial pattern matching (Extended Abstract)
dc.type	Conference Proceeding
utslib.citation.volume	2020-April
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-03T01:36:10Z
pubs.finish-date	2020-04-24
pubs.publication-status	Published
pubs.start-date	2020-04-20
pubs.volume	2020-April

Abstract:

© 2020 IEEE. A huge volume of spatio-textual objects generated from location-based services 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 users' intention. It has been demonstrated to be useful but 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. Our experimental results on real large datasets 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/143718