Optimal Dynamic Range Searching in Non-replicating Index Structures.

@inproceedings{DBLP:conf/icdt/KanthS99,
  author    = {Kothuri Venkata Ravi Kanth and
               Ambuj K. Singh},
  editor    = {Catriel Beeri and
               Peter Buneman},
  title     = {Optimal Dynamic Range Searching in Non-replicating Index Structures},
  booktitle = {Database Theory - ICDT '99, 7th International Conference, Jerusalem,
               Israel, January 10-12, 1999, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1540},
  year      = {1999},
  isbn      = {3-540-65452-6},
  pages     = {257-276},
  ee        = {db/conf/icdt/KanthS99.html, http://link.springer.de/link/service/series/0558/bibs/1540/15400257.htm},
  crossref  = {DBLP:conf/icdt/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Online Edition: Springer LINK

References

[Ben75]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX

[BKK96]

Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39 BibTeX

[BKSS90]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[Cha90]

Bernard Chazelle: Lower Bounds for Orthogonal Range Searching: I. The Reporting Case. J. ACM 37(2): 200-212(1990) BibTeX

[DRSS96]

Ajit A. Diwan, Sanjeeva Rane, S. Seshadri, S. Sudarshan: Clustering Techniques for Minimizing External Path Length. VLDB 1996: 342-353 BibTeX

[Fre87]

Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX

[Fre95]

Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91 BibTeX

[GI97]

Roberto Grossi, Giuseppe F. Italiano: Efficient Splitting and Merging Algorithms for Order Decomposable Problems (Extended Abstract). ICALP 1997: 605-615 BibTeX

[Gut84]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[HKP97]

Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256 BibTeX

[KS97]

Norio Katayama, Shin'ichi Satoh: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. SIGMOD Conference 1997: 369-380 BibTeX

[KT98]

Elias Koutsoupias, David Scot Taylor: Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998: 52-58 BibTeX

[LS90]

David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX

[Meh84]

...

[Ove83]

Mark H. Overmars: The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X
BibTeX

[OvL81]

Mark H. Overmars, Jan van Leeuwen: Worst-Case Optimal Insertion and Deletion Methods for Decomposable Searching Problems. Inf. Process. Lett. 12(4): 168-173(1981) BibTeX

[Rav98]

...

[Rob81]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[Sam89]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

[SM98]

Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51 BibTeX

[SR95]

Sairam Subramanian, Sridhar Ramaswamy: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. SODA 1995: 378-387 BibTeX

[Tar79]

Robert Endre Tarjan: A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets. J. Comput. Syst. Sci. 18(2): 110-127(1979) BibTeX

[Vai89]

Pravin M. Vaidya: Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract). STOC 1985: 169-174 BibTeX

[vKO91]

Marc J. van Kreveld, Mark H. Overmars: Divided k-d Trees. Algorithmica 6(6): 840-858(1991) BibTeX

[WJ96]

David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996: 516-523 BibTeX