Range Queries in Natural Language Dictionaries with Recursive Lists of Clusters

Margarida Paula Neves Mamede; Fernanda Maria Barquinha Tavares Vieira Barbosa

doi:10.1109/ISCIS.2007.4456857

Range Queries in Natural Language Dictionaries with Recursive Lists of Clusters

Margarida Paula Neves Mamede, Fernanda Maria Barquinha Tavares Vieira Barbosa

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

4 Citations (Scopus)

Abstract

We evaluate the performance of range queries in the Recursive List of Clusters (RLC) metric data structure, when the metric spaces are natural language dictionaries with the Levenshtein distance. The study compares RLC with five data structures (GNAT, H-Dsatl, LAESA, LC, and vp-trees) and comprises six dictionaries. The natural language dictionaries (in English, French, German, Italian, Portuguese, and Spanish), are characterised according to the mean and the variance of the histograms of distances.

The experimental results show that RLC has a good performance in all tested cases and, in some of them, it outperforms all the other data structures. In addition, RLC is the only data structure that always keeps its good performance, whether the space dimension is lower or higher, and whether the query radius is smaller or larger.

Original language	Unknown
Title of host publication	INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES
Pages	174-179
DOIs	https://doi.org/10.1109/ISCIS.2007.4456857
Publication status	Published - 1 Jan 2007
Event	22nd International Symposium on Computer and Information Sciences - Duration: 1 Jan 2007 → …

Conference

Conference	22nd International Symposium on Computer and Information Sciences
Period	1/01/07 → …

Access to Document

10.1109/ISCIS.2007.4456857

Cite this

@inproceedings{399fda06f6514726b1efd781b517eac1,

title = "Range Queries in Natural Language Dictionaries with Recursive Lists of Clusters",

abstract = "We evaluate the performance of range queries in the Recursive List of Clusters (RLC) metric data structure, when the metric spaces are natural language dictionaries with the Levenshtein distance. The study compares RLC with five data structures (GNAT, H-Dsatl, LAESA, LC, and vp-trees) and comprises six dictionaries. The natural language dictionaries (in English, French, German, Italian, Portuguese, and Spanish), are characterised according to the mean and the variance of the histograms of distances. The experimental results show that RLC has a good performance in all tested cases and, in some of them, it outperforms all the other data structures. In addition, RLC is the only data structure that always keeps its good performance, whether the space dimension is lower or higher, and whether the query radius is smaller or larger.",

keywords = "dictionaries, query processing., Data structures, natural languages",

author = "Mamede, {Margarida Paula Neves} and Barbosa, {Fernanda Maria Barquinha Tavares Vieira}",

year = "2007",

month = jan,

day = "1",

doi = "10.1109/ISCIS.2007.4456857",

language = "Unknown",

isbn = "978-1-4244-1363-8",

pages = "174--179",

booktitle = "INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES",

note = "22nd International Symposium on Computer and Information Sciences ; Conference date: 01-01-2007",

}

TY - GEN

T1 - Range Queries in Natural Language Dictionaries with Recursive Lists of Clusters

AU - Mamede, Margarida Paula Neves

AU - Barbosa, Fernanda Maria Barquinha Tavares Vieira

PY - 2007/1/1

Y1 - 2007/1/1

N2 - We evaluate the performance of range queries in the Recursive List of Clusters (RLC) metric data structure, when the metric spaces are natural language dictionaries with the Levenshtein distance. The study compares RLC with five data structures (GNAT, H-Dsatl, LAESA, LC, and vp-trees) and comprises six dictionaries. The natural language dictionaries (in English, French, German, Italian, Portuguese, and Spanish), are characterised according to the mean and the variance of the histograms of distances. The experimental results show that RLC has a good performance in all tested cases and, in some of them, it outperforms all the other data structures. In addition, RLC is the only data structure that always keeps its good performance, whether the space dimension is lower or higher, and whether the query radius is smaller or larger.

AB - We evaluate the performance of range queries in the Recursive List of Clusters (RLC) metric data structure, when the metric spaces are natural language dictionaries with the Levenshtein distance. The study compares RLC with five data structures (GNAT, H-Dsatl, LAESA, LC, and vp-trees) and comprises six dictionaries. The natural language dictionaries (in English, French, German, Italian, Portuguese, and Spanish), are characterised according to the mean and the variance of the histograms of distances. The experimental results show that RLC has a good performance in all tested cases and, in some of them, it outperforms all the other data structures. In addition, RLC is the only data structure that always keeps its good performance, whether the space dimension is lower or higher, and whether the query radius is smaller or larger.

KW - dictionaries

KW - query processing.

KW - Data structures

KW - natural languages

U2 - 10.1109/ISCIS.2007.4456857

DO - 10.1109/ISCIS.2007.4456857

M3 - Conference contribution

SN - 978-1-4244-1363-8

SP - 174

EP - 179

BT - INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES

T2 - 22nd International Symposium on Computer and Information Sciences

Y2 - 1 January 2007

ER -