Idioma:

On the Least Cost for Proximity Searching in Metric Spaces

Figueroa, Karina ; Chávez, Edgar ; Navarro, Gonzalo ; Paredes, Rodrigo

Experimental Algorithms, 2006, p.279-290 [Periódico revisado por pares]

Berlin, Heidelberg: Springer Berlin Heidelberg

Sem texto completo

Citações Citado por

Enviar para

Título:
On the Least Cost for Proximity Searching in Metric Spaces
Autor: Figueroa, Karina ; Chávez, Edgar ; Navarro, Gonzalo ; Paredes, Rodrigo
Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Computer science; control theory; systems ; Distance Computation ; Exact Algorithm ; Exact sciences and technology ; Face Image ; Information systems. Data bases ; Memory organisation. Data processing ; Probabilistic Algorithm ; Range Query ; Software ; Theoretical computing
É parte de: Experimental Algorithms, 2006, p.279-290
Notas: Supported by CONACyT (Mexico) and Millennium Nucleus Center for Web Research, Grant P04-067-F, Mideplan, (Chile).
Descrição: Proximity searching consists in retrieving from a database those elements that are similar to a query. As the distance is usually expensive to compute, the goal is to use as few distance computations as possible to satisfy queries. Indexes use precomputed distances among database elements to speed up queries. As such, a baseline is AESA, which stores all the distances among database objects, but has been unbeaten in query performance for 20 years. In this paper we show that it is possible to improve upon AESA by using a radically different method to select promising database elements to compare against the query. Our experiments show improvements of up to 75% in document databases. We also explore the usage of our method as a probabilistic algorithm that may lose relevant answers. On a database of faces where any exact algorithm must examine virtually all elements, our probabilistic version obtains 85% of the correct answers by scanning only 10% of the database.
Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Anterior Resultado 9 Avançar Ir para próxima página

Realização: Logos de Redes Sociais:

On the Least Cost for Proximity Searching in Metric Spaces

Figueroa, Karina ; Chávez, Edgar ; Navarro, Gonzalo ; Paredes, Rodrigo

Berlin, Heidelberg: Springer Berlin Heidelberg

Buscando em bases de dados remotas. Favor aguardar.