Revision: | 1.2 |

Committed: | Sun May 6 17:28:23 2001 UTC (23 years, 3 months ago) by root |

Branch: | MAIN |

Changes since 1.1: |
+76 -11 lines |

Log Message: | *** empty log message *** |

# | Content |
---|---|

1 | package Tree::M; |

2 | |

3 | use Carp; |

4 | use DynaLoader; |

5 | |

6 | BEGIN { |

7 | $VERSION = 0.01; |

8 | @ISA = qw(DynaLoader); |

9 | bootstrap Tree::M, $VERSION; |

10 | } |

11 | |

12 | =head1 NAME |

13 | |

14 | Tree::M - implement M-trees for efficient "multimedia-searched" |

15 | |

16 | =head1 SYNOPSIS |

17 | |

18 | use Tree::M; |

19 | |

20 | $M = new Tree::M |

21 | |

22 | =head1 DESCRIPTION |

23 | |

24 | (not yet) |

25 | |

26 | Ever had the problem of managing multi-dimensional (spatial) data but your |

27 | database only had one-dimensional indices (b-tree etc.)? Queries like |

28 | |

29 | select data from table where latitude > 40 and latitude < 50 |

30 | and longitude> 50 and longitude< 60; |

31 | |

32 | are quite inefficient, unless longitude and latitude are part of the same |

33 | spatial index (e.g. an R-tree). |

34 | |

35 | An M-tree is an index tree that does not directly look at the stored keys |

36 | but rather requires a I<distance> (a metric, e.g. a vector norm) function |

37 | to be defined that sorts keys according to their distance. In the example |

38 | above the distance function could be the maximum norm (C<max(x1-x2, |

39 | y1-y2)>). The lookup above would then be something like this: |

40 | |

41 | my $res = $M->range([45,55], 5); |

42 | |

43 | This module implements an M-tree. Although the data structure and the |

44 | distance function is arbitrary, the current version only implements |

45 | n-dimensional discrete vectors and hardwires the distance function to the |

46 | suared euclidean metric (i.e. C<(x1-x2)**2 + (y1-y2)**2 + (z1-z2)**2 + |

47 | ...>). Evolution towards more freedom is expected ;) |

48 | |

49 | =head2 THE Tree::M CLASS |

50 | |

51 | =over 4 |

52 | |

53 | =item $M = new Tree::M ndims, min, max, steps |

54 | |

55 | Creates a new M-Tree. Before it can be used you have to call one of the |

56 | C<create> or C<open> methods. |

57 | |

58 | ndims the number of dimensions each vector has |

59 | min the lowest allowable scalar value in each dimension |

60 | max the maximum allowable number |

61 | steps the number of discrete steps (used when stored externally) |

62 | |

63 | Example: create an M-Tree that stores 8-bit rgb-values: |

64 | |

65 | $M = new Tree::M 3, 0, 255, 256; |

66 | |

67 | Example: create an M-Tree that stores coordinates from -1..1 with 100 different steps: |

68 | |

69 | $M = new Tree::M 2, -1, 1, 100; |

70 | |

71 | =item $M->open(path) |

72 | |

73 | =item $M->create($path) |

74 | |

75 | Open or create the external storage file C<$path> and associate it with the tree. |

76 | |

77 | [this braindamaged API will go away ;)] |

78 | |

79 | =item $M->insert(\@v, $data) |

80 | |

81 | Insert a vector (given by an array reference) into the index and associate |

82 | it with the value C<$data> (a 32-bit integer). |

83 | |

84 | =item $res = $M->range(\@v, $radius) |

85 | |

86 | Search all entries not farther away from C<@v> then C<$radius> and return |

87 | an arrayref containing the searchresults. |

88 | |

89 | Each result is again anarrayref composed like this: |

90 | |

91 | [\@v, $data] |

92 | |

93 | e.g. the same as given to the C<insert> method. |

94 | |

95 | =item $res = $M->top(\@v, $n) |

96 | |

97 | Return the C<$n> "nearest neighbours". The results arrayref (see C<range>) |

98 | contains the C<$n> index values nearest to C<@v>, sorted for distance. |

99 | |

100 | =item $distance = $M->distance(\@v1, \@v2) |

101 | |

102 | Calculcate the distance between two vectors, just as they databse engine |

103 | would do it. |

104 | |

105 | =item $depth = $M->maxlevel |

106 | |

107 | Return the maximum height of the tree (usually a small integer specifying |

108 | the length of the path from the root to the farthest leaf) |

109 | |

110 | =cut |

111 | |

112 | =back |

113 | |

114 | =head1 BUGS |

115 | |

116 | Inserting too many duplicate keys into the tree cause the C++ library to |

117 | die, so don't do that. |

118 | |

119 | =head1 AUTHOR |

120 | |

121 | Marc Lehmann <pcg@goof.com>. |

122 | |

123 | =head1 SEE ALSO |

124 | |

125 | perl(1), L<DBIx::SpatialKeys>. |

126 | |

127 | =cut |

128 | |

129 | 1; |

130 |