A two-tire index structure for approximate string matching with block moves

Bin Wang; Long Xie; Guoren Wang

doi:10.1007/978-3-642-04205-8_17

A two-tire index structure for approximate string matching with block moves

Bin Wang^*
, Long Xie
, Guoren Wang

^*Corresponding author for this work

Northeastern University
Northeastern University China
Liaoning University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

Many applications need to solve the problem of approximate string matching with block moves. It is an NP-Complete problem to compute block edit distance between two strings. Our goal is to filter non-candidate strings as much as possible. Based on the two matured filter strategies, frequency distance and positional q-gram, we propose a two-tire index structure to make the use of the two filters more efficiently. We give a full specification of the index structure, including how to choose character order to achieve a better filterability and how to balance number of strings in different clusters. We present our experiments on real data sets to evaluate our technique and show the proposed index structure can provide a good performance.

Original language	English
Title of host publication	Database Systems for Advanced Applications - DASFAA 2009 International Workshops
Subtitle of host publication	BenchmarX, MCIS, WDPP, PPDA, MBC, PhD
Pages	197-211
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-04205-8_17
Publication status	Published - 2009
Externally published	Yes
Event	International Workshops on Database Systems for Advanced Applications, DASFAA 2009: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD - Brisbane, QLD, Australia Duration: 20 Apr 2009 → 23 Apr 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5667 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Workshops on Database Systems for Advanced Applications, DASFAA 2009: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD
Country/Territory	Australia
City	Brisbane, QLD
Period	20/04/09 → 23/04/09

Access to Document

10.1007/978-3-642-04205-8_17

Cite this

Wang, B., Xie, L., & Wang, G. (2009). A two-tire index structure for approximate string matching with block moves. In Database Systems for Advanced Applications - DASFAA 2009 International Workshops: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD (pp. 197-211). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5667 LNCS). https://doi.org/10.1007/978-3-642-04205-8_17

Wang, Bin ; Xie, Long ; Wang, Guoren. / A two-tire index structure for approximate string matching with block moves. Database Systems for Advanced Applications - DASFAA 2009 International Workshops: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD. 2009. pp. 197-211 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ee6adc104dcf4ab790324c39d2ff675a,

title = "A two-tire index structure for approximate string matching with block moves",

abstract = "Many applications need to solve the problem of approximate string matching with block moves. It is an NP-Complete problem to compute block edit distance between two strings. Our goal is to filter non-candidate strings as much as possible. Based on the two matured filter strategies, frequency distance and positional q-gram, we propose a two-tire index structure to make the use of the two filters more efficiently. We give a full specification of the index structure, including how to choose character order to achieve a better filterability and how to balance number of strings in different clusters. We present our experiments on real data sets to evaluate our technique and show the proposed index structure can provide a good performance.",

author = "Bin Wang and Long Xie and Guoren Wang",

year = "2009",

doi = "10.1007/978-3-642-04205-8\_17",

language = "English",

isbn = "364204204X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "197--211",

booktitle = "Database Systems for Advanced Applications - DASFAA 2009 International Workshops",

note = "International Workshops on Database Systems for Advanced Applications, DASFAA 2009: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD ; Conference date: 20-04-2009 Through 23-04-2009",

}

Wang, B, Xie, L & Wang, G 2009, A two-tire index structure for approximate string matching with block moves. in Database Systems for Advanced Applications - DASFAA 2009 International Workshops: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5667 LNCS, pp. 197-211, International Workshops on Database Systems for Advanced Applications, DASFAA 2009: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD, Brisbane, QLD, Australia, 20/04/09. https://doi.org/10.1007/978-3-642-04205-8_17

A two-tire index structure for approximate string matching with block moves. / Wang, Bin; Xie, Long; Wang, Guoren.
Database Systems for Advanced Applications - DASFAA 2009 International Workshops: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD. 2009. p. 197-211 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5667 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A two-tire index structure for approximate string matching with block moves

AU - Wang, Bin

AU - Xie, Long

AU - Wang, Guoren

PY - 2009

Y1 - 2009

N2 - Many applications need to solve the problem of approximate string matching with block moves. It is an NP-Complete problem to compute block edit distance between two strings. Our goal is to filter non-candidate strings as much as possible. Based on the two matured filter strategies, frequency distance and positional q-gram, we propose a two-tire index structure to make the use of the two filters more efficiently. We give a full specification of the index structure, including how to choose character order to achieve a better filterability and how to balance number of strings in different clusters. We present our experiments on real data sets to evaluate our technique and show the proposed index structure can provide a good performance.

AB - Many applications need to solve the problem of approximate string matching with block moves. It is an NP-Complete problem to compute block edit distance between two strings. Our goal is to filter non-candidate strings as much as possible. Based on the two matured filter strategies, frequency distance and positional q-gram, we propose a two-tire index structure to make the use of the two filters more efficiently. We give a full specification of the index structure, including how to choose character order to achieve a better filterability and how to balance number of strings in different clusters. We present our experiments on real data sets to evaluate our technique and show the proposed index structure can provide a good performance.

UR - https://www.scopus.com/pages/publications/70349330017

U2 - 10.1007/978-3-642-04205-8_17

DO - 10.1007/978-3-642-04205-8_17

M3 - Conference contribution

AN - SCOPUS:70349330017

SN - 364204204X

SN - 9783642042041

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 211

BT - Database Systems for Advanced Applications - DASFAA 2009 International Workshops

T2 - International Workshops on Database Systems for Advanced Applications, DASFAA 2009: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD

Y2 - 20 April 2009 through 23 April 2009

ER -

Wang B, Xie L, Wang G. A two-tire index structure for approximate string matching with block moves. In Database Systems for Advanced Applications - DASFAA 2009 International Workshops: BenchmarX, MCIS, WDPP, PPDA, MBC, PhD. 2009. p. 197-211. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04205-8_17

A two-tire index structure for approximate string matching with block moves

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this