Listas de salto deterministas fuertemente equilibradas en peso

11

En la sección 2.2 de Cache-Ajeno B-Trees , Fuertemente Peso equilibrado de la búsqueda árboles se definen como:

Para alguna constante , cada nodo en altura tiene descendientes .dvhΘ(dh)

Ellos reclaman:

Los árboles de búsqueda que satisfacen las Propiedades 1 y 2 incluyen árboles B con equilibrio de peso, listas de omisión deterministas y listas de omisión en el sentido esperado.

Otros papeles también afirman que las listas de salto deterministas son fuertemente peso equilibrado, incluyendo concurrente Cache-Ajeno B-Trees y Cache-Ignorancia Streaming árboles B .

No puedo entender por qué las listas de salto deterministas tienen esta propiedad. El documento original sobre listas de omisión deterministas señala que

Como vemos en la Fig. 1, existe una correspondencia uno a uno entre 1-2 listas de omisión y 2-3 árboles.

Me parece, sin embargo, que 2-3 árboles no son fuertemente equilibrada de peso, ya que un nodo a la altura puede tener en cualquier lugar de a descendientes.h2h3h

jbapple
fuente
1
Eso suena como un problema legítimo. Todos los documentos mencionados comparten un coautor, por lo que podría ser un descuido constante. ¿Has enviado un correo electrónico a los autores?
Según Vognsen el
¿Qué tan crítico para las pruebas es el rango estrecho para el número de descendientes?
Suresh Venkat
@Per: ahora he enviado un correo electrónico al coautor compartido. @Suresh: no estoy seguro, pero los autores eligen basar sus estructuras en árboles B con equilibrio de peso, por lo que mi pregunta no es sobre la validez de los resultados principales.
jbapple
Tenga cuidado de no someter a un autor a una vergüenza pública sin darse cuenta. cf. meta.cstheory.stackexchange.com/questions/214/…
Tsuyoshi Ito
@ Tsuyoshi: Dado que la importancia de este posible error es muy pequeña (por lo que puedo decir, no afecta los resultados reclamados de los documentos citados de ninguna manera), y dado que la mayoría de los "errores" que encuentro publicados el trabajo son solo errores en mi propio entendimiento, pensé que sería mejor preguntar aquí primero. Incluso si esto es un error, es tan leve que sospecho que no conduciría a ninguna vergüenza del autor.
jbapple

Respuestas:

5

He estado en contacto con uno de los autores. Confirmó que esto era un error.

Como se indicó anteriormente, esto no afecta, de ninguna manera, ninguno de los resultados del documento.

jbapple
fuente