Bidirectional String Anchors for Improved Text Indexing and Top-K Similarity Search

Grigorios Loukidis; Solon  Pissis; Michelle Sweering

doi:10.1109/TKDE.2022.3231780

Bidirectional String Anchors for Improved Text Indexing and Top-K Similarity Search

Grigorios Loukidis, Solon Pissis, Michelle Sweering

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

98 Downloads (Pure)

Abstract

The minimizers sampling mechanism is a popular mechanism for string sampling. However, minimizers sampling mechanisms lack good guarantees on the expected size of their samples for different combinations of their input parameters. Furthermore, indexes constructed over minimizers samples lack good worst-case guarantees for on-line pattern searches. In response, we propose bidirectional string anchors (bd-anchors), a new string sampling mechanism. Given an integer ℓ, our mechanism selects the lexicographically smallest rotation in every length-ℓ fragment. We show that, like minimizers samples, bd-anchors samples are approximately uniform, locally consistent, and computable in linear time. Furthermore, our experiments demonstrate that the bd-anchors sample sizes decrease proportionally to ℓ; and that these sizes are competitive to or smaller than the minimizers sample sizes. We theoretically justify these results by analyzing the expected size of bd-anchors samples. We also prove that computing a total order on the input alphabet which minimizes the bd-anchors sample size is NP-hard. We next highlight the benefits of bd-anchors in two important applications: text indexing and top-K similarity search. For the first application, we develop an index for performing on-line pattern searches in near-optimal time, and show experimentally that a simple implementation of our index is consistently faster for on-line pattern searches than an analogous implementation of a minimizers-based index; we also show that it is substantially faster than two classic text indexes. For the second application, we develop a heuristic for top-K similarity search under edit distance, and show experimentally that it is generally as accurate as the state-of-the-art tool for the same purpose but more than one order of magnitude faster.

Original language	English
Pages (from-to)	11093-11111
Number of pages	19
Journal	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume	35
Issue number	11
DOIs	https://doi.org/10.1109/TKDE.2022.3231780
Publication status	Published - 16 Jan 2023

Keywords

string algorithms
string sampling
text indexing
top-K similarity search

Access to Document

10.1109/TKDE.2022.3231780

Bidirectional_String_Anchors-4Accepted author manuscript, 1.24 MBLicence: CC BY-ND

Cite this

@article{8e9eea594fc54ca5a8c5fd74a6991bec,

title = "Bidirectional String Anchors for Improved Text Indexing and Top-K Similarity Search",

abstract = "The minimizers sampling mechanism is a popular mechanism for string sampling. However, minimizers sampling mechanisms lack good guarantees on the expected size of their samples for different combinations of their input parameters. Furthermore, indexes constructed over minimizers samples lack good worst-case guarantees for on-line pattern searches. In response, we propose bidirectional string anchors (bd-anchors), a new string sampling mechanism. Given an integer ℓ, our mechanism selects the lexicographically smallest rotation in every length-ℓ fragment. We show that, like minimizers samples, bd-anchors samples are approximately uniform, locally consistent, and computable in linear time. Furthermore, our experiments demonstrate that the bd-anchors sample sizes decrease proportionally to ℓ; and that these sizes are competitive to or smaller than the minimizers sample sizes. We theoretically justify these results by analyzing the expected size of bd-anchors samples. We also prove that computing a total order on the input alphabet which minimizes the bd-anchors sample size is NP-hard. We next highlight the benefits of bd-anchors in two important applications: text indexing and top-K similarity search. For the first application, we develop an index for performing on-line pattern searches in near-optimal time, and show experimentally that a simple implementation of our index is consistently faster for on-line pattern searches than an analogous implementation of a minimizers-based index; we also show that it is substantially faster than two classic text indexes. For the second application, we develop a heuristic for top-K similarity search under edit distance, and show experimentally that it is generally as accurate as the state-of-the-art tool for the same purpose but more than one order of magnitude faster.",

keywords = "string algorithms, string sampling, text indexing, top-K similarity search",

author = "Grigorios Loukidis and Solon Pissis and Michelle Sweering",

note = "Publisher Copyright: {\textcopyright} 1989-2012 IEEE.",

year = "2023",

month = jan,

day = "16",

doi = "10.1109/TKDE.2022.3231780",

language = "English",

volume = "35",

pages = "11093--11111",

journal = "IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - Bidirectional String Anchors for Improved Text Indexing and Top-K Similarity Search

AU - Loukidis, Grigorios

AU - Pissis, Solon

AU - Sweering, Michelle

PY - 2023/1/16

Y1 - 2023/1/16

N2 - The minimizers sampling mechanism is a popular mechanism for string sampling. However, minimizers sampling mechanisms lack good guarantees on the expected size of their samples for different combinations of their input parameters. Furthermore, indexes constructed over minimizers samples lack good worst-case guarantees for on-line pattern searches. In response, we propose bidirectional string anchors (bd-anchors), a new string sampling mechanism. Given an integer ℓ, our mechanism selects the lexicographically smallest rotation in every length-ℓ fragment. We show that, like minimizers samples, bd-anchors samples are approximately uniform, locally consistent, and computable in linear time. Furthermore, our experiments demonstrate that the bd-anchors sample sizes decrease proportionally to ℓ; and that these sizes are competitive to or smaller than the minimizers sample sizes. We theoretically justify these results by analyzing the expected size of bd-anchors samples. We also prove that computing a total order on the input alphabet which minimizes the bd-anchors sample size is NP-hard. We next highlight the benefits of bd-anchors in two important applications: text indexing and top-K similarity search. For the first application, we develop an index for performing on-line pattern searches in near-optimal time, and show experimentally that a simple implementation of our index is consistently faster for on-line pattern searches than an analogous implementation of a minimizers-based index; we also show that it is substantially faster than two classic text indexes. For the second application, we develop a heuristic for top-K similarity search under edit distance, and show experimentally that it is generally as accurate as the state-of-the-art tool for the same purpose but more than one order of magnitude faster.

AB - The minimizers sampling mechanism is a popular mechanism for string sampling. However, minimizers sampling mechanisms lack good guarantees on the expected size of their samples for different combinations of their input parameters. Furthermore, indexes constructed over minimizers samples lack good worst-case guarantees for on-line pattern searches. In response, we propose bidirectional string anchors (bd-anchors), a new string sampling mechanism. Given an integer ℓ, our mechanism selects the lexicographically smallest rotation in every length-ℓ fragment. We show that, like minimizers samples, bd-anchors samples are approximately uniform, locally consistent, and computable in linear time. Furthermore, our experiments demonstrate that the bd-anchors sample sizes decrease proportionally to ℓ; and that these sizes are competitive to or smaller than the minimizers sample sizes. We theoretically justify these results by analyzing the expected size of bd-anchors samples. We also prove that computing a total order on the input alphabet which minimizes the bd-anchors sample size is NP-hard. We next highlight the benefits of bd-anchors in two important applications: text indexing and top-K similarity search. For the first application, we develop an index for performing on-line pattern searches in near-optimal time, and show experimentally that a simple implementation of our index is consistently faster for on-line pattern searches than an analogous implementation of a minimizers-based index; we also show that it is substantially faster than two classic text indexes. For the second application, we develop a heuristic for top-K similarity search under edit distance, and show experimentally that it is generally as accurate as the state-of-the-art tool for the same purpose but more than one order of magnitude faster.

KW - string algorithms

KW - string sampling

KW - text indexing

KW - top-K similarity search

UR - http://www.scopus.com/inward/record.url?scp=85147273495&partnerID=8YFLogxK

U2 - 10.1109/TKDE.2022.3231780

DO - 10.1109/TKDE.2022.3231780

M3 - Article

SN - 1041-4347

VL - 35

SP - 11093

EP - 11111

JO - IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING

JF - IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING

IS - 11

ER -

Bidirectional String Anchors for Improved Text Indexing and Top-K Similarity Search

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this