Range Queries in Natural Language Dictionaries with Recursive Lists of Clusters

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 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 languageUnknown
Title of host publicationINTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES
Pages174-179
DOIs
Publication statusPublished - 1 Jan 2007
Event22nd International Symposium on Computer and Information Sciences -
Duration: 1 Jan 2007 → …

Conference

Conference22nd International Symposium on Computer and Information Sciences
Period1/01/07 → …

Cite this