|
 ABSTRACT
Search operations in databases require special support at the physical level. This is true for conventional databases as well as spatial databases, where typical search operations include the point query (find all objects that contain a given search point) and the region query (find all objects that overlap a given search region). More than ten years of spatial database research have resulted in a great variety of multidimensional access methods to support such operations. We give an overview of that work. After a brief survey of spatial data management in general, we first present the class of point access methods, which are used to search sets of points in two or more dimensions. The second part of the paper is devoted to spatial access methods to handle extended objects, such as rectangles or polyhedra. We conclude with a discussion of theoretical and experimental results concerning the relative performance of various approaches.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
ABEL, D. J. AND MARK, D.M. 1990. A comparative analysis of some two-dimensional orderings. Int. J. Geograph. Inf. Syst. 4, 1, 21-31.
|
| |
2
|
ABEL, D. J. AND SMITH, J.L. 1983. A data structure and algorithm based on a linear key for a rectangle retrieval problem. Comput. Vis. 24, 1-13.
|
| |
3
|
|
| |
4
|
AREF, W. G. AND SAMET, H. 1994. The spatial filter revisited. In Proceedings of the Sixth International Symposium on Spatial Data Handling, 190-208.
|
| |
5
|
BAYER, R. 1996. The universal B-tree for multidimensional indexing. Tech. Rep. I9639, Technische Universit~it Mfinchen, Munich, Germany. http://www.leo.org/pub/comp/doc/ techre po rts/tu m/info rm a tik/re port/ 1996/TUM- I9639.ps.gz.
|
| |
6
|
BAYER, R. AND MCCREIGHT, E.M. 1972. Organization and maintenance of large ordered indices. Acta Inf. 1, 3, 173-189.
|
| |
7
|
BAYER, R. AND SCHKOLNICK, M. 1977. Concurrency of operations on B-trees. Acta Inf. 9, 1-21.
|
| |
8
|
Bruno Becker , Paolo Giulio Franciosa , Stephan Gschwind , Thomas Ohler , Gerald Thiemt , Peter Widmayer, Enclosing Many Boxes by an Optimal Pair of Boxes, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.475-486, February 13-15, 1992
|
| |
9
|
BECKER, L. 1992. A new algorithm and a cost model for join processing with the grid file. Ph.D. thesis, Universit~it-Gesamthochschule Siegen, Germany.
|
 |
10
|
Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
|
| |
11
|
|
| |
12
|
|
| |
13
|
BENTLEY, J. L. 1979. Multidimensional binary search in database applications. IEEE Trans. Softw. Eng. 4, 5, 333-340.
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
BRINKHOFF, T. 1994. Der spatial join in geodatenbanksystemen. Ph.D. Thesis, Ludwig- Maximilians-Universit~it Mfinchen. Germany (in German).
|
| |
18
|
|
| |
19
|
|
| |
20
|
Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
|
| |
21
|
Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
|
| |
22
|
Alexander Brodsky , Catherine Lassez , Jean-Louis Lassez , Michael J. Maher, Separability of polyhedra for optimal filtering of spatial and constraint data, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.54-65, May 22-25, 1995, San Jose, California, United States
[doi> 10.1145/212433.212449]
|
| |
23
|
|
| |
24
|
BURKHARD, W.A. 1983. Interpolation-based index maintenance. BIT 23, 274-294.
|
| |
25
|
L. T. Chen , R. Drach , M. Keating , S. Louis , D. Rotem , A. Shoshani, Efficient organization and access of multi-dimensional datasets on tertiary storage systems, Information Systems, v.20 n.2, p.155-183, April 1995
[doi> 10.1016/0306-4379(95)98559-V]
|
| |
26
|
|
| |
27
|
|
| |
28
|
|
| |
29
|
EGENHOFER, M. 1989. Spatial query languages. Ph.D. Thesis, University of Maine, Orono, ME.
|
| |
30
|
|
| |
31
|
EVANGELIDIS, G. 1994. The hBn-tree: A concurrent and recoverable multi-attribute index structure. Ph.D. Thesis, Northeastern University, Boston, MA.
|
| |
32
|
|
| |
33
|
|
| |
34
|
|
| |
35
|
|
| |
36
|
|
| |
37
|
|
| |
38
|
|
| |
39
|
|
| |
40
|
Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
|
| |
41
|
FINKEL, R. AND BENTLEY, J. L. 1974. Quad trees: A data structure for retrieval of composite keys. Acta Inf. 4, 1, 1-9.
|
| |
42
|
FLAJOLET, P. 1983. On the performance evaluation of extendible hashing and trie searching. Acta Inf. 20, 345-369.
|
| |
43
|
|
| |
44
|
|
| |
45
|
|
| |
46
|
|
| |
47
|
|
| |
48
|
|
| |
49
|
|
| |
50
|
|
| |
51
|
GAEDE, V. 1995a. Geometric information makes spatial query processing more efficient. In Proceedings of the Third ACM International Workshop on Advances in Geographic Information Systems (ACM-GIS'95) (Baltimore, MD) 45-52.
|
| |
52
|
|
| |
53
|
GAEDE, V. AND RIEKERT, W.-F. 1994. Spatial access methods and query processing in the object-oriented GIS GODOT. In Proceedings of the AGDM'94 Workshop (Delft, The Netherlands), Netherlands Geodetic Commission, 40-52.
|
| |
54
|
|
| |
55
|
|
| |
56
|
|
| |
57
|
|
| |
58
|
|
| |
59
|
GUNTHER, O. 1991. Evaluation of spatial access methods with oversize shelves. In Geographic Database Management Systems, G. Gambosi, M. Scholl, and H.-W. Six, Eds., Springer-Verlag, Berlin/Heidelberg/New York, 177-193.
|
| |
60
|
|
| |
61
|
|
| |
62
|
|
| |
63
|
GUNTHER, O. AND GAEDE, V. 1997. Oversize shelves: A storage management technique for large spatial data objects. Int. J. Geog. Inf. Syst. 11, 1, 5-32.
|
| |
64
|
|
| |
65
|
|
| |
66
|
|
| |
67
|
|
| |
68
|
|
| |
69
|
|
| |
70
|
HELLERSTEIN, J. M., KOUTSOUPIAS, E., AND PAPAD- IMITRIOU, C.H. 1997. Towards a theory of indexability. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.
|
| |
71
|
|
| |
72
|
HENRICH, A. 1995. Adapting the transformation technique to maintain multidimensional nonpoint objects in k-d-tree based access structures. In Proceedings of the Third ACM International Workshop on Advances in Geographic Information Systems (ACM-GIS'95) (Baltimore, MD) ACM Press, New York.
|
| |
73
|
|
| |
74
|
HENRICH, A. AND SIX, H.-W. 1991. How to split buckets in spatial data structures. In Geographic Database Management Systems, G. Gambosi, M. Scholl, and H.-W. Six, Eds., Springer-Verlag, Berlin/Heidelberg/New York, 212-244.
|
| |
75
|
|
| |
76
|
|
| |
77
|
|
| |
78
|
|
| |
79
|
|
| |
80
|
Andreas Hutflesz , Hans-Werner Six , Peter Widmayer, Twin grid files: space optimizing access schemes, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.183-190, June 01-03, 1988, Chicago, Illinois, United States
|
| |
81
|
|
| |
82
|
HUTFLESZ, A., WIDMAYER, P., AND ZIMMERMANN, C. 1991. Global order makes spatial access faster. In Geographic Database Management Systems, G. Gambosi, M. Scholl, and H.-W. Six, Eds., Springer-Verlag, Berlin/Heidelberg/ New York, 161-176.
|
| |
83
|
INFORMIX INC. 1997. The DataBlade architecture. URL http://www.informix.com.
|
| |
84
|
|
| |
85
|
|
| |
86
|
|
| |
87
|
|
| |
88
|
|
| |
89
|
|
| |
90
|
KAMEL, I., KHALIL, M., AND KOURAMAJIAN, V. 1996. Bulk insertion in dynamic R-trees. In Proceedings of the Seventh International Symposium on Spatial Data Handling (Delft, The Netherlands), 3B.31-3B.42.
|
| |
91
|
Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States
[doi> 10.1145/153850.153884]
|
| |
92
|
|
| |
93
|
|
| |
94
|
KLINGER, A. 1971. Pattern and search statistics. In Optimizing Methods in Statistics, S. Rustagi, Ed., 303-337.
|
| |
95
|
KNOTT, G. 1975. Hashing functions. Comput. J. 18, 3, 265-278.
|
| |
96
|
|
| |
97
|
|
| |
98
|
|
| |
99
|
KRIEGEL, H.-P., HELP, P., HELP, S., SCHIWIETZ, M., AND SCHNEIDER, R. 1991. An access method based query processor for spatial database systems. In Geographic Database Management Systems, G. Gambosi, M. Scholl, and H.-W. Six, Eds., Springer-Verlag, Berlin/Heidelberg/New York, 273-292.
|
| |
100
|
H. -P. Kriegel , M. Schiwietz , R. Schneider , B. Seeger, Performance comparison of point and spatial access methods, Proceedings of the first symposium on Design and implementation of large spatial databases, p.89-114, February 1990, Santa Barbara, California, United States
|
| |
101
|
|
| |
102
|
|
| |
103
|
|
| |
104
|
|
| |
105
|
|
| |
106
|
|
| |
107
|
|
| |
108
|
LARSON, P.A. 1980. Linear hashing with partial expansions. In Proceedings of the Sixth International Conference on Very Large Data Bases, 224-232.
|
| |
109
|
|
| |
110
|
|
| |
111
|
LITWIN, W. 1980. Linear hashing: A new tool for file and table addressing. In Proceedings of the Sixth International Conference on Very Large Data Bases, 212-223.
|
| |
112
|
|
| |
113
|
|
| |
114
|
|
| |
115
|
|
| |
116
|
|
| |
117
|
|
| |
118
|
Lu, H. AND OoI, B.-C. 1993. Spatial indexing: Past and future. IEEE Data Eng. Bull. 16, 3, 16-21.
|
| |
119
|
MATSUYAMA, T., HAO, L. V., AND NAGAO, M. 1984. A file organization for geographic information systems based on spatial proximity. Int. J. Comput. Vis. Graph. Image Process. 26, 3, 303-318.
|
| |
120
|
MORTON, G. 1966. A computer oriented geodetic data base and a new technique in file sequencing. IBM Ltd.
|
| |
121
|
|
| |
122
|
NEWELL, R. G. AND DOE, M. 1997. Discrete geometry with seamless topology in a GIS. URL http://www.smallworld-us.com.
|
| |
123
|
|
| |
124
|
|
| |
125
|
|
| |
126
|
|
| |
127
|
NIEVERGELT, g. AND HINRICHS, K. 1987. Storage and access structures for geometric data bases. In Proceedings of the International Conference on Foundations of Data Organization, S. Ghosh, Y. Kambayashi, and K. Tanaka, Eds., Plenum, New York.
|
| |
128
|
|
| |
129
|
|
| |
130
|
OHSAWA, Y. AND SAKAUCHI, M. 1983. BD-tree: A new n-dimensional data structure with efficient dynamic characteristics. In Proceedings of the Ninth World Computer Congress, IFIP 1983, 539-544.
|
| |
131
|
|
| |
132
|
|
| |
133
|
OoI, B. C., MCDONELL, K. J., AND SACKS-DAVIS, R. 1987. Spatial kd-tree: An indexing mechanism for spatial databases. In Proceedings of the IEEE Computer Software and Applications Conference, 433-438.
|
| |
134
|
|
| |
135
|
OOSTEROM, P. 1990. Reactive data structures for geographic information systems. Ph.D. Thesis, University of Leiden, The Netherlands.
|
| |
136
|
ORACLE INC. 1995. Oracle 7 multidimension: Advances in relational database technology for spatial data management. White paper.
|
| |
137
|
ORENSTEIN, J. 1982. Multidimensional tries used for associative searching. Inf. Process. Lett. 14, 4, 150-157.
|
| |
138
|
|
| |
139
|
|
| |
140
|
|
| |
141
|
|
| |
142
|
|
| |
143
|
|
| |
144
|
|
| |
145
|
OTOO, E. J. 1985. Symmetric dynamic index maintenance scheme. In Proceedings of the International Conference on Foundations of Data Organization, Plenum, New York, 283- 296.{
|
| |
146
|
|
| |
147
|
|
| |
148
|
|
| |
149
|
|
| |
150
|
|
| |
151
|
|
| |
152
|
Bernd-Uwe Pagel , Hans-Werner Six , Mario Winter, Window query-optimal clustering of spatial objects, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.86-94, May 22-25, 1995, San Jose, California, United States
[doi> 10.1145/212433.212458]
|
| |
153
|
Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States
[doi> 10.1145/153850.153878]
|
| |
154
|
Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States
|
| |
155
|
|
| |
156
|
PELOUX, J., REYNAL, G., AND SCHOLL, M. 1994. Evaluation of spatial indices implemented with the 02 DBMS. Ingdni~rie des Syst~mes d'Information 6.
|
| |
157
|
|
| |
158
|
|
| |
159
|
|
| |
160
|
|
| |
161
|
ROUSSOPOULOS, N. AND LEIFKER, D. 1984. An introduction to PSQL: A pictorial structured query language. In Proceedings of the IEEE Workshop on Visual Languages.
|
| |
162
|
|
| |
163
|
SAGAN, H. 1994. Space-Filling Curves. Springer-Verlag, Berlin/Heidelberg/New York.
|
| |
164
|
|
| |
165
|
|
| |
166
|
|
| |
167
|
|
| |
168
|
|
| |
169
|
SCHIWIETZ, M. 1993. Speicherung und anfragebearbeitung komplexer geo-objekte. Ph.D. Thesis, Ludwig-Maximilians-Universit~it Mtinchen, Germany (in German).
|
| |
170
|
|
| |
171
|
|
| |
172
|
|
| |
173
|
|
| |
174
|
|
| |
175
|
|
| |
176
|
|
| |
177
|
|
| |
178
|
|
| |
179
|
SIEMENS NIXDORF INFORMATIONSSYSTEME AG 1997. URL http://www.sni.de.
|
| |
180
|
|
| |
181
|
|
| |
182
|
SMITH, T. R. AND GAO, P. 1990. Experimental performance evaluations on spatial access methods. In Proceedings of the Fourth International Symposium on Spatial Data Handling (Zfirich), 991-1002.
|
| |
183
|
|
| |
184
|
STONEBRAKER, M., SELLIS, T., AND HANSON, E. 1986. An analysis of rule indexing implementations in data base systems. In Proceedings of the First International Conference on Expert Data Base Systems.
|
| |
185
|
STUCKEY, P. 1997. Constraint search trees. In Proceedings of the International Conference on Logic Programming (CLP'97), L. Naish, Ed., MIT Press, Cambridge, MA.
|
| |
186
|
|
| |
187
|
TAMMINEN, M. 1982. The extendible cell method for closest point problems. BIT 22, 27-41.
|
| |
188
|
TAMMINEN, M. 1983. Performance analysis of cell based geometric file organisations. Int. J. Cutup. Vis. Graph. Image Process. 24, 160- 181.
|
| |
189
|
|
| |
190
|
|
| |
191
|
TROPF, H. AND HERZOG, H. 1981. Multidimensional range search in dynamically balanced trees. Angewandte Informatik 2, 71-77.
|
| |
192
|
WHANG, K.-Y. AND KRISHNAMURTHY, R. 1985. Multilevel grid files. IBM Research Laboratory, Yorktown Heights, NY.
|
| |
193
|
WHITE, M. 1981. N-trees: Large ordered indexes for multi-dimensional space. Tech. Rep., Application Mathematics Research Staff, Statistical Research Division, US Bureau of the Census.
|
| |
194
|
WIDMAYER, P. 1991. Datenstrukturen ffir Geodatenbanken. In Entwicklungstendenzen bei Datenbank-Systemen, G. Vossen and K.-U. Witt, Eds., Oldenbourg-Verlag, Munich, Chapter 9, 317-361 (in German).
|
CITED BY 270
|
|
|
|
|
|
|
|
Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States
|
|
|
Christian Böhm , Bernhard Braunmüller , Markus Breunig , Hans-Peter Kriegel, High performance clustering based on the similarity join, Proceedings of the ninth international conference on Information and knowledge management, p.298-305, November 06-11, 2000, McLean, Virginia, United States
|
|
|
Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pankaj K. Agarwal , Mark de Berg , Joachim Gudmundsson , Mikael Hammar , Herman J. Haverkort, Box-trees and R-trees with near-optimal query time, Proceedings of the seventeenth annual symposium on Computational geometry, p.124-133, June 2001, Medford, Massachusetts, United States
|
|
|
Hakan Ferhatosmanoglu , Divyakant Agrawal , Amr El Abbadi, Clustering declustered data for efficient retrieval, Proceedings of the eighth international conference on Information and knowledge management, p.343-350, November 02-06, 1999, Kansas City, Missouri, United States
|
|
|
|
|
|
Kyoosang Cho , Yijie Han , Yugyung Lee , E. K. Park, Dynamic and hierarchical spatial access method using integer searching, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
|
|
|
|
|
|
|
|
|
Robert W.P. Luk , H. V. Leong , Tharam S. Dillon , Alvin T.S. Chan , W. Bruce Croft , James Allan, A survey in indexing and searching XML documents, Journal of the American Society for Information Science and Technology, v.53 n.6, p.415-437, May, 2002
|
|
|
|
|
|
Zu-Kuan Wei , Young-Hwan Oh , Jae-Dong Lee , Jae-Hong Kim , Dong-Sun Park , Young-Geol Lee , Hae-Young Bae, Efficient spatial data transmission in Web-based GIS, Proceedings of the 2nd international workshop on Web information and data management, p.38-42, November 02-06, 1999, Kansas City, Missouri, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Theodoros Tzouramanis , Michael Vassilakopoulos , Yannis Manolopoulos, Overlapping linear quadtrees: a spatio-temporal access method, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.1-7, November 02-07, 1998, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Caetano Traina, Jr. , Agma Traina , Roberto Santos Filho , Christos Faloutsos, How to improve the pruning ability of dynamic metric access methods, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
|
|
|
Byunggu Yu , Ratko Orlandic , Martha Evens, Simple QSF-trees: an efficient and scalable spatial access method, Proceedings of the eighth international conference on Information and knowledge management, p.5-14, November 02-06, 1999, Kansas City, Missouri, United States
|
|
|
|
|
|
|
|
|
|
|
|
Alexander Thomasian , Vittorio Castelli , Chung-Sheng Li, Clustering and singular value decomposition for approximate indexing in high dimensional spaces, Proceedings of the seventh international conference on Information and knowledge management, p.201-207, November 02-07, 1998, Bethesda, Maryland, United States
|
|
|
|
|
|
Kurt Stockinger , Kesheng Wu , Arie Shoshani, Strategies for processing ad hoc queries on large data warehouses, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.72-79, November 08-08, 2002, McLean, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hubert Ka Yau Leung , Ioana Burcea , Hans-Amo Jacobsen, Modeling location-based services with subject spaces, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.171-181, October 06-09, 2003, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
Fangyan Rao , Long Zhang , Xiu Lan Yu , Ying Li , Ying Chen, Spatial hierarchy and OLAP-favored search in spatial data warehouse, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
|
|
|
|
|
|
Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Vector approximation based indexing for non-uniform high dimensional data sets, Proceedings of the ninth international conference on Information and knowledge management, p.202-209, November 06-11, 2000, McLean, Virginia, United States
|
|
|
|
|
|
|
|
|
|
|
|
Il-dong Jung , Young-ho You , Jong-hwan Lee , Kyungsok Kim, Broadcasting and caching policies for location-dependent queries in urban areas, Proceedings of the 2nd international workshop on Mobile commerce, September 28-28, 2002, Atlanta, Georgia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bugra Gedik , Kun-Lung Wu , Philip Yu , Ling Liu, Motion adaptive indexing for moving continual queries over moving objects, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jun Feng , Yuelong Zhu , Naoto Mukai , Toyohide Watanabe, Search on transportation network for location-based service, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.657-666, June 22-24, 2005, Bari, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Caetano Traina, Jr. , Roberto F. Filho , Agma J. Traina , Marcos R. Vieira , Christos Faloutsos, The Omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.483-505, October 2007
|
|
|
|
|
|
|
|
|
Ning An , Sudhanva Gurumurthi , Anand Sivasubramaniam , Narayanan Vijaykrishnan , Mahmut Kandemir , Mary Jane Irwin, Energy-performance trade-offs for spatial access methods on memory-resident data, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.3, p.179-197, November 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
Delis Vasilis , Makris Christos , Sioutas Spiros, A provably efficient computational model for approximate spatiotemporal retrieval, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.40-46, November 02-06, 1999, Kansas City, Missouri, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Biswanath Panda , Mirek Riedewald , Stephen B. Pope , Johannes Gehrke , L. Paul Chew, Indexing for function approximation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Steven W. Schlosser , Jiri Schindler , Stratos Papadomanolakis , Minglong Shao , Anastassia Ailamaki , Christos Faloutsos , Gregory R. Ganger, On multidimensional data and modern disks, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.17-17, December 13-16, 2005, San Francisco, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xuemin Lin , Qing Liu , Yidong Yuan , Xiaofang Zhou, Multiscale histograms: summarizing topological relations in large spatial datasets, Proceedings of the 29th international conference on Very large data bases, p.814-825, September 09-12, 2003, Berlin, Germany
|
|
|
|
|
|
Nikos Karayannidis , Aris Tsois , Timos Sellis , Roland Pieringer , Volker Markl , Frank Ramsak , Robert Fenk , Klaus Elhardt , Rudolf Bayer, Processing star queries on hierarchically-clustered fact tables, Proceedings of the 28th international conference on Very Large Data Bases, p.730-741, August 20-23, 2002, Hong Kong, China
|
|
|
Young-Koo Lee , Kyu-Young Whang , Yang-Sae Moon , Il-Yeol Song, A one-pass aggregation algorithm with the optimal buffer size in multidimensional OLAP, Proceedings of the 28th international conference on Very Large Data Bases, p.790-801, August 20-23, 2002, Hong Kong, China
|
|
|
|
|
|
|
|
|
Ke Yang , Bingsheng He , Rui Fang , Mian Lu , Naga Govindaraju , Qiong Luo , Pedro Sander , Jiaoying Shi, In-memory grid files on graphics processors, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Khanh Vu , Kien A. Hua , Hao Cheng , Sheau-Dong Lang, A non-linear dimensionality-reduction technique for fast similarity search in large databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
|
|
|
Stratos Papadomanolakis , Anastassia Ailamaki , Julio C. Lopez , Tiankai Tu , David R. O'Hallaron , Gerd Heber, Efficient query processing on unstructured tetrahedral meshes, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ranga Raju Vatsavai , Thomas E. Burk , B. Tyler Wilson , Shashi Shekhar, A Web-based browsing and spatial analysis system for regional natural resource analysis and mapping, Proceedings of the 8th ACM international symposium on Advances in geographic information systems, p.95-101, November 06-11, 2000, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
Ning An , Anand Sivasubramaniam , Narayanan Vijaykrishnan , Mahmut T. Kandemir , Mary Jane Irwin , Sudhanva Gurumurthi, Analyzing energy behavior of spatial access methods for memory-resident data, Proceedings of the 27th International Conference on Very Large Data Bases, p.411-420, September 11-14, 2001
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Weidong Chen , Jyh-Herng Chow , You-Chin Fuh , Jean Grandbois , Michelle Jou , Nelson Mendonça Mattos , Brian T. Tran , Yun Wang, High Level Indexing of User-Defined Types, Proceedings of the 25th International Conference on Very Large Data Bases, p.554-564, September 07-10, 1999
|
|
|
Bruno Martins , Jose Borbinha , Gilberto Pedrosa , João Gil , Nuno Freire, Geographically-aware information retrieval for collections of digitized historical maps, Proceedings of the 4th ACM workshop on Geographical information retrieval, November 09-09, 2007, Lisbon, Portugal
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S. Sioutas , K. Tsakalidis , K. Tsichlas , C. Makris , Y. Manolopoulos, A new approach on indexing mobile objects on the plane, Data & Knowledge Engineering, v.67 n.3, p.362-380, December, 2008
|
|
|
|
|
|
Pradeep Mohan , Ronald E. Wilson , Shashi Shekhar , Betsy George , Ned Levine , Mete Celik, Should SDBMS support a join index?: a case study from CrimeStat, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
|
|
|
|
|
|
|
|
|
Tobias Scholl , Bernhard Bauer , Benjamin Gufler , Richard Kuntschke , Angelika Reiser , Alfons Kemper, Scalable community-driven data sharing in e-science grids, Future Generation Computer Systems, v.25 n.3, p.290-300, March, 2009
|
|
|
Zi Huang , Heng Tao Shen , Jie Shao , Stefan Rüger , Xiaofang Zhou, Locality condensation: a new dimensionality reduction method for image retrieval, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yufei Tao , Ke Yi , Cheng Sheng , Panos Kalnis, Quality and efficiency in high dimensional nearest neighbor search, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2