1 comment
17th Apr 10
cheng xu1.1.2 EXCELL [Tamminen 1982]( Extendible CELL)
the EXCELL method decomposes the universe regularly: all grid cells are of equal size.( In order to maintain this property in the presence of insertions, each new split results in the halving of all cells and therefore in the doubling of the directory size.)
1.1.3 The Two-Level Grid File [Hinrichs 1985]
The basic idea of the two level grid file is to use a second grid file to manage the grid directory.( The first of the two levels is called the root directory,which is a coarsened version of the second level, the actual grid directory.)个人觉得就是一级索引而二级索引的意思，问题是两个level可能会相互影响造成麻烦
1.1.4 The Twin Grid File [Hutflesz et al. 1988b]
(目的是提高空间利用率相对于original grid file，to increase space utilization)twin 意味着这两个grid file不是层次结构，两个grid file都要span整个空间，对于两个file ，P和S，如果increase in the number一方大于另一个方的时候才会造成point的转移，（P转移point到S，S overflow了而P可能反过来merge了）
1.1.5 Multidimensional Linear Hashing
uses no or only a very small directory(occupy relatively little storage compared to extendible hashing and usually possible to keep all relevant information in main memory) Early proposals failed to support the range queries,
MOLHPE ：a variant of linear hashing called multidimensional order-preserving linear hashing with partial expansions [Kriegel and Seeger 1986] guarantee a modest file growth,缺点是对于nonuniform distributions data，它不能gracefully adapt to them，（question 1）这是由于hashing function的缺点造成的，但是对于uniform distribution，它outperform其他的对手
quantile hashing [Kriegel and Seeger 1987, 1989].
利用a-quantiles来解决question1，将不是均匀分布的transformed into uniformly
distributed values for a，该作者提出了linear order-preserving (PLOP) hashing来适应extended objects
dynamic z-hashing [Hutflesz et al.1988a]
它有更好的order preserving properties，uses a space-filling technique called z-ordering（disadvantage 是会generate 一些无用的block，这点与interpolation-based grid file [Ouksel 1985]相似）也不是对于不同的分布有影响
1.2 Hierarchical Access Methods
PAM based on binary or multiway tree structure,除了混合结构BANG file 和buddy tree，其他都不需要地址计算，而是通过buckets来组织数据，overlapping regions和partial coverage这两种技术可以用来提高SAM的性能
1.2.1 The k-d-B-Tree [Robinson 1981]
Balanced，没有最小的空间开销可以确保，leaf node存储 data points located in the responding partition，类似于adaptive k-d-tree和B-tree
1.2.2 LSD-Tree [Henrich et al.1989]( Local Split Decision)
adapts well to data that are nonuniformly distributed and that it is therefore well-suited for use in connection with the transformation technique;组织结构如adaptive k-d-tree,整个universe被partition到各种不同大小的disjoint cell.用特别的paging算法来保证preserve external balancing property；
用两种策略来accommodate skewed data，
two split strategies ：
·data-dependent(SP1) local decision,equal number of objects on both sizes of the splits
·distribution-dependent (SP2):split is done at fixed dimension and position,assumed an underlying distribution
SP = aSP1 +(1-a) SP2 . a 是由一个经验获得的因素，it vary as deleted and inserted operation.
提高storage utilization的策略就是redistribute data among buckets.improve search performance for nonpoint data and range queries,auxiliary informantion on the existing data regions along with the index entries.
1.2.3 The Buddy Tree [Seeger and Kriegel 1990].
dynamic hashing scheme with structured directory: The tree is constructed by consecutive insertion,cutting the universe recursively into two parts of equal size with iso-oriented hyperplanes
properties：
(1) each directory node contains at least two entries;（not be balanced,leaves maybe not in the same level）
(2) whenever a node n is split, the MBBs Id(ni) and Id(nj) of the two resulting subnodes ni and nj are recomputed to reflect the current situation;and(achieve a high selectivity at the directory level,)
(3) except for the root of the directory, there is exactly one pointer referring to each directory page.
Property1,3保证了linear的growth of the directory，use k-d-tree to avoid deadlock of grid file,Only restrict is the number of buddies.
1.2.4 The BANG File [Freeston 1987]
(Balanced And Nested Grid) difference from grid file : bucket regions may intersect form nonrectangular bucket regions. nested interpolation- based grid file close to the BANG tree,the major difference is the organized directory.BANG 用 spanning split 来取得 high storage utilization这样可能会造成 整目录的traversal in depth-first manner，Freeston [1989a]采用了不同的spitting strategys ，对于extended objects，用centrorid 来确定重心。Freeston [1989b]
1.2.5 The hB-Tree [Lomet and Salzberg 1989, 1990]
（holey brick tree）和k-d-B tree 的相似点是两者都采用了k-d-trees来用内部节点来组织空间，两者最显著的区别是 node spitting是基于multiple attributes ，与BANG file相似，它也是fractal structure (a hole brick) with an external enclosing region and several cavities called extracted regions（萃取空间）.这种结构避免了cascadding of split（瀑布式的）.严格意思上说，非tree结构而是而是有向无圈图directed acyclic graphs
Searching is similar to the k-d-B-tree.Insertiong is carried out analogously to the k-d—B-tree.
