Page 33 - 79_04

Óscar
Miguel
Rivera
Borroto
&
col.

criterios
para
reducir
el
número
de
cálculos
necesarios,
incluyendo
la
proyección

de
las
instancias
d-­-dimensionales
en
un
espacio
de
dimensión
menor,
de
forma
tal

que
varias
instancias
puedan
ser
buscadas,
o
eliminadas
desde
una
búsqueda,

simultáneamente
(108).
En
este
sentido,
varios
de
los
algoritmos
reportados

pueden
no
ser
directamente
aplicables
a
la
búsqueda
de
los
mejores
pares
en

contextos
químicos
ya
que
los
primeros
asumen
que
los
atributos
son
variables

continuas,
mientras
que
las
estructuras
químicas
son
descritas
frecuentemente
por

fragmentos
de
ocurrencia
binaria.
En
estos
casos,
cada
una
de
las
estructuras
en
un

archivo
se
representa
por
una
cadena
de
bits
en
el
que
se
establece
el
bit
i-­-ésimo
si

el
fragmento
correspondiente
está
presente
en
la
estructura.
Además,
a
menudo
se

supone
que
las
instancias
se
encuentran
en
un
espacio
de
dimensión
d
pequeña,

por
lo
general
2
o
3;
sin
embargo,
para
el
caso
de
la
representación
química

binaria,
d
puede
ser
del
orden
de
102
o
103
(el
número
de
bits
en
la
cadena
de
bits),

y
por
ende
estos
algoritmos
resultan
ser
poco
factibles.
Por
ejemplo,
el

procedimiento
O(nlog
N)
debido
a
Friedman
et
al.
(1977)
implica
una
constante
de

proporcionalidad
alrededor
de
1.6d

(107),
mientras
que
el
método
de
búsqueda
de

Bentley
et
a1.
(1980)
implica
la
inspección
de
todas
las
3d
-­-
1
celdas
adyacentes
a

una
celda
dada
en
un
espacio
d-­-dimensional
(108).

Alternativamente,
otros
investigadores
han
centrado
su
atención
en
los

algoritmos
de
búsqueda
basados
en
la
representación
binaria.
Smeaton
y
Van

Rijsbergen
(1981)
tienen
en
cuenta
que
un
archivo
invertido
puede
ser
utilizado

para
aumentar
la
eficiencia
de
la
búsqueda
de
emparejamiento
a
una
consulta
en

documentos
donde
tiene
al
menos
un
término
en
común.
A
partir
de
aquí,
estos

autores
describen
experimentos
usando
un
procedimiento
de
límite
superior
que

permite
que
la
búsqueda
de
la
mejor
pareja
se
termine
antes
de
que
todos
los

documentos
en
la
lista
de
los
ficheros
invertidos
correspondientes
a
la
consulta

hayan
sido
inspeccionados
(109).
Murtagh
(1982)
describe
una
extensión
de
este

algoritmo
en
el
que
son
calculados
otros
límites
superiores,
posibilitando
una

mayor
reducción
en
el
número
de
documentos
que
necesitan
ser
comparados
con

una
consulta
(110).

Van
Marlen
y
Van
den
Hende
(1979),
y
Rasmussen
et
al.
(1979)
han
descrito

algoritmos
de
recuperación
de
las
mejores
parejas
para
el
uso
de
ficheros

informáticos
con
espectros
de
masa,
donde
la
estructura
es
caracterizada
por
una

cadena
de
bits
correspondientes
a
los
picos
observados
en
el
espectro
de
masa

molecular
(111,
112),
mientras
que
otros
autores
han
estudiado
la
búsqueda
del

mejor
emparejamiento
en
los
sistemas
de
recuperación
de
información
molecular

(106).

Baldi
et
al.
(2008)
plantean
un
algoritmo
diferente
a
los
demás,
el
cual

consiste
en
almacenar
para
cada
molécula
A
de
la
base
de
datos,
no
solamente
su

vector
correspondiente
??
sino
también
almacenar
información
adicional
contenida

550