ETI: an efficient index for set similarity queries
| Autor: | Lianying Jia, Yong Liu, Decheng Miao, Jianqing Xi, Mengjuan Li |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Structure (mathematical logic)
Containment (computer programming) General Computer Science Computer science computer.software_genre Inverted index Theoretical Computer Science Set (abstract data type) Similarity (network science) Trie Node (computer science) Cardinality (SQL statements) Data mining computer |
| Zdroj: | Frontiers of Computer Science. |
| ISSN: | 2095-2236 2095-2228 |
| Popis: | Set queries are an important topic and have attracted a lot of attention. Earlier research mainly concentrated on set containment queries. In this paper we focus on the T-Overlap query which is the foundation of the set similarity query. To address this issue, unlike traditional algorithms that are based on an inverted index, we design a new paradigm based on the prefix tree (trie) called the expanded trie index (ETI) which expands the trie node structure by adding some new properties. Based on ETI, we convert the TOverlap problem to finding query nodes with specific query depth equaling to T and propose a new algorithm called TSimilarity to solve T-Overlap efficiently. Then we carry out a three-step framework to extend T-Overlap to other similarity predicates. Extensive experiments are carried out to compare T-Similarity with other inverted index based algorithms from cardinality of query, overlap threshold, dataset size, the number of distinct elements and so on. Results show that T-Similarity outperforms the state-of-the-art algorithms in many aspects. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink